New version page

VASSAR CMPU 102 - Linked Lists

Upgrade to remove ads
Upgrade to remove ads
Unformatted text preview:

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


View Full Document
Download Linked Lists
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Linked Lists and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Linked Lists 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?