Chapter 5PreliminariesSlide 3Object ReferencesSlide 5Slide 6Slide 7Slide 8Slide 9Slide 10Resizable ArraysReference-Based Linked ListsSlide 13Slide 14Slide 15Programming with Linked Lists: Displaying the Contents of a Linked ListDisplaying the Contents of a Linked ListSlide 18Deleting a Specified Node from a Linked ListSlide 20Slide 21Inserting a Node into a Specified Position of a Linked ListSlide 23Slide 24Slide 25Determining curr and prevA Reference-Based Implementation of the ADT ListSlide 28Comparing Array-Based and Referenced-Based ImplementationsSlide 30Slide 31Slide 32Passing a Linked List to a MethodProcessing Linked Lists RecursivelySlide 35Variations of the Linked List: Tail ReferencesCircular Linked ListSlide 38Dummy Head NodesDoubly Linked ListSlide 41Slide 42Slide 43Slide 44Application: Maintaining an InventoryThe Java Collections FrameworkGenericsIteratorsSlide 49The Java Collection’s Framework List InterfaceSlide 51Slide 52SummarySlide 54Slide 55Slide 56Summary© 2006 Pearson Addison-Wesley. All rights reserved 5 A-1 Chapter 5Linked ListsCS102 Sections 51 and 52Marc Smith and Jim Ten EyckSpring 2008© 2006 Pearson Addison-Wesley. All rights reserved 5 A-2Preliminaries•Options for implementing an ADT–Array•Has a fixed size•Data must be shifted during insertions and deletions–Linked list•Is able to grow in size as needed•Does not require the shifting of items during insertions and deletions© 2006 Pearson Addison-Wesley. All rights reserved 5 A-3PreliminariesFigure 5-1Figure 5-1a) A linked list of integers; b) insertion; c) deletion© 2006 Pearson Addison-Wesley. All rights reserved 5 A-4Object References•A reference variable–Contains the location of an object–ExampleInteger intRef;intRef = new Integer(5);–As a data field of a class•Has the default value null–A local reference variable to a method•Does not have a default value© 2006 Pearson Addison-Wesley. All rights reserved 5 A-5Object ReferencesFigure 5-2Figure 5-2A reference to an Integer object© 2006 Pearson Addison-Wesley. All rights reserved 5 A-6Object References•When one reference variable is assigned to another reference variable, both references then refer to the same objectInteger p, q;p = new Integer(6);q = p;•A reference variable that no longer references any object is marked for garbage collection© 2006 Pearson Addison-Wesley. All rights reserved 5 A-7Object ReferencesFigure 5-3a-dFigure 5-3a-da) Declaring reference variables; b) allocating an object; c) allocating another object, with the dereferenced object marked for garbage collection© 2006 Pearson Addison-Wesley. All rights reserved 5 A-8Object ReferencesFigure 5-3e-gFigure 5-3e-ge) allocating an object; f) assigning null to a reference variable; g) assigning a reference with a null value© 2006 Pearson Addison-Wesley. All rights reserved 5 A-9Object References•An array of objects–Is actually an array of references to the objects–ExampleInteger[] scores = new Integer[30];–Instantiating Integer objects for each array referencescores[0] = new Integer(7);scores[1] = new Integer(9); // and so on …© 2006 Pearson Addison-Wesley. All rights reserved 5 A-10Object References•Equality operators (== and !=)–Compare the values of the reference variables, not the objects that they reference•equals method–Compares objects field by field•When an object is passed to a method as an argument, the reference to the object is copied to the method’s formal parameter•Reference-based ADT implementations and data structures use Java references© 2006 Pearson Addison-Wesley. All rights reserved 5 A-11Resizable Arrays•The number of references in a Java array is of fixed size•Resizable array–An array that grows and shrinks as the program executes–An illusion that is created by using an allocate and copy strategy with fixed-size arrays•java.util.Vector class–Uses a similar technique to implement a growable array of objects© 2006 Pearson Addison-Wesley. All rights reserved 5 A-12Reference-Based Linked Lists•Linked list–Contains nodes that are linked to one another–A node•Contains both data and a “link” to the next item•Can be implemented as an objectpublic class Node { private Object item; private Node next; // constructors, accessors, // and mutators …} // end class NodeFigure 5-5Figure 5-5A node© 2006 Pearson Addison-Wesley. All rights reserved 5 A-13Reference-Based Linked Lists•Using the Node classNode n = new Node (new Integer(6));Node first = new Node (new Integer(9), n);Figure 5-7Figure 5-7Using the Node constructor to initialize a data field and a link value© 2006 Pearson Addison-Wesley. All rights reserved 5 A-14Reference-Based Linked Lists•Data field next in the last node is set to null•head reference variable–References the list’s first node–Always exists even when the list is emptyFigure 5-8Figure 5-8A head reference to a linked list© 2006 Pearson Addison-Wesley. All rights reserved 5 A-15Reference-Based Linked Lists•head reference variable can be assigned null without first using new–Following sequence results in a lost nodehead = new Node(); // Don’t really need to use new herehead = null; // since we lose the new Node object hereFigure 5-9Figure 5-9A lost node© 2006 Pearson Addison-Wesley. All rights reserved 5 A-16Programming with Linked Lists:Displaying the Contents of a Linked List•curr reference variable–References the current node–Initially references the first node•To display the data portion of the current nodeSystem.out.println(curr.getItem());•To advance the current position to the next nodecurr = curr.getNext();© 2006 Pearson Addison-Wesley. All rights reserved 5 A-17Displaying the Contents of a Linked ListFigure 5-10Figure 5-10The effect of the assignment curr = curr.getNext( )© 2006 Pearson Addison-Wesley. All rights reserved 5 A-18Displaying the Contents of a Linked List•To display all the data items in a linked listfor (Node curr = head; curr != null; curr = curr.getNext()) {System.out.println(curr.getItem());} // end for© 2006 Pearson Addison-Wesley. All rights reserved 5 A-19Deleting a Specified Node from a Linked List•To delete node N which curr references–Set next in the node that precedes N to reference the node that follows N prev.setNext(curr.getNext());Figure 5-11Figure 5-11Deleting a node from a linked list© 2006 Pearson Addison-Wesley. All rights reserved 5 A-20Deleting a Specified Node