© 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 duringinsertions 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 anInteger object© 2006 Pearson Addison-Wesley. All rights reserved 5 A-6Object References• When one reference variable is assigned toanother reference variable, both references thenrefer to the same objectInteger p, q;p = new Integer(6);q = p;• A reference variable that no longer references anyobject is marked for garbage collection© 2006 Pearson Addison-Wesley. All rights reserved 5 A-7Object ReferencesFigure 5-3a-dFigure 5-3a-da) Declaring referencevariables; b) allocating anobject; c) allocating anotherobject, with the dereferencedobject marked for garbagecollection© 2006 Pearson Addison-Wesley. All rights reserved 5 A-8Object ReferencesFigure 5-3e-gFigure 5-3e-ge) allocating an object; f)assigning null to areference variable; g)assigning a reference witha 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 theobjects that they reference• equals method– Compares objects field by field• When an object is passed to a method as anargument, the reference to the object is copied tothe method’s formal parameter• Reference-based ADT implementations and datastructures use Java references© 2006 Pearson Addison-Wesley. All rights reserved 5 A-11Resizable Arrays• The number of references in a Java array is offixed size• Resizable array– An array that grows and shrinks as the programexecutes– An illusion that is created by using an allocate and copystrategy with fixed-size arrays• java.util.Vector class– Uses a similar technique to implement a growable arrayof objects© 2006 Pearson Addison-Wesley. All rights reserved 5 A-12Reference-Based Linked Lists• Linked list– Contains nodes that are linked to oneanother– A node• Contains both data and a “link” to thenext 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 firstusing 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 aLinked 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 aLinked 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 aLinked 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 aLinked List• To delete node N which curr references– Set next in the node that precedes N to reference the node thatfollows Nprev.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 from aLinked List• Deleting the first node is a special casehead = head.getNext();Figure 5-12Figure 5-12Deleting the first node© 2006 Pearson Addison-Wesley. All rights reserved 5 A-21Deleting a Specified Node from aLinked List• To return a node that is no longer needed to thesystemcurr.setNext(null);curr = null;• Three steps to delete a node from a linked list– Locate the node that you want to delete– Disconnect this node from the linked list by changingreferences– Return the node to the system© 2006 Pearson Addison-Wesley. All rights reserved 5 A-22Inserting a Node into a SpecifiedPosition of a Linked List• To create a node for the new itemnewNode = new Node(item);• To insert a node between two nodesnewNode.setNext(curr);prev.setNext(newNode);Figure 5-13Figure 5-13Inserting a new node into a linked list© 2006 Pearson Addison-Wesley. All rights reserved 5 A-23Inserting a Node into a SpecifiedPosition of a Linked List• To insert a node at