Unformatted text preview:

Linked ListsReferenceReferences as LinksSlide 4Slide 5Declarations for Linked ListsSlide 7Slide 8Inserting an Node at the FrontSlide 10Slide 11Slide 12Slide 13Linked List – Constructor ImplementationInserting a Node at the FrontSlide 16Slide 17Slide 18Slide 19Inserting Nodes (anywhere)Slide 21Slide 22Slide 23Slide 24Removing the Head NodeSlide 26Slide 27Slide 28Removing a Node (anywhere)Linked ListsReferenceA reference is a variable that stores the address of an objectA reference is also called a pointerclass Student {String name; String ID;float gpa;}studentJohn Smith407253.57References as LinksReferences can be used to create links between objectsclass Student {String name; String ID;float gpa;Student next;}John Smith407253.57Jane Jones588213.72Student object contains a reference to another Student objectHow to access these objects?Linked ListsA Linked List is a sequence of elements, with each element connected to the next element by a link Need a special reference that points to the first node, called the headheadLinked ListsIt might be useful to also have a reference to the last node, tailheadTailWhat if we have access to the tail but not the head?Each node in the linked list is an instance of class, e.g., Node<T>datanext10datanext15datanext7nullpublic class Node<T>{ private T data; private Node<T> next; ...}Declarations for Linked ListsDeclarations for Linked ListsWe need to keep track of the front node, using headdatanext10datanext15datanext7nullheadDeclarations for Linked ListsIf (head == null), then the list is emptyheadnullInserting an Node at the FrontLet’s add a new entry, 13, to the front of the linked list10157nullheadInserting an Node at the FrontCreate a new node...101577nullheadInserting an Node at the FrontCreate a new node...Place the data in the new node's data field.10157nullhead13Inserting an Node at the Front10157nullhead13Create a new node...Place the data in the new node's data field.... Connect the new node to the front of the list.Inserting an Node at the Front10157nullhead13Create a new node...Place the data in the new node's data field.... Connect the new node to the front of the list.Make the head refer to the new nodeclass Node<T> {private T value;private Node<T> next;public Node(T value, Node<T> next) {this.value = value;this.next = next;}Linked List – Constructor Implementationpublic Node(T value, Node<T> next) {this.value = value;this.next = next;}Inserting a Node at the FrontDoes the constructor workcorrectly for the first node on a new list ?public Node(T value, Node<T> next) {this.value = value;this.next = next;}Inserting an Node at the FrontSuppose head is nulland we execute theassignment shown here:Node<Integer> head = null;head = new Node<>(13, head);headnullpublic Node(T value, Node<T> next) {this.value = value;this.next = next;}Inserting an Node at the Frontheadnull13nullNode<Integer> head = null;head = new Node<>(13, head);public Node(T value, Node<T> next) {this.value = value;this.next = next;}Inserting an Node at the Fronthead13nullNode<Integer> head = null;head = new Node<>(13, head);public Node(T value, Node<T> next) {this.value = value;this.next = next;}…SomeType item1 = new SomeType(100);SomeType item2 = new SomeType(200);SomeType item3 = new SomeType(300);Node<SomeType> head = null;head = new Node<>(item1, head); // head -> 100 -> nullhead = new Node<>(item2, head); // head -> 200 -> 100 -> nullhead = new Node<>(item3, head); // head -> 300 -> 200 -> 100 -> nullInserting a Node at the FrontInserting Nodes (anywhere)Otherwise, identify previous to refer to the node which is just before the new node's position.If in the front:head = new Node<>(newEntry, head);15107nullheadIn this example, thenew node will bethe second nodeIn this example, thenew node will bethe second nodepreviousInserting Nodes (anywhere)15107nullheadprevious.nextrefers to the headof a small linkedlist, with 10 and 7previous.nextrefers to the headof a small linkedlist, with 10 and 7previousInserting Nodes (anywhere)15107nullheadThe new node mustbe inserted at thefront of this smalllinked list.The new node mustbe inserted at thefront of this smalllinked list.13previousInserting Nodes (anywhere)Adding at the front of a list: Adding at the front of this new small list:•head’ = new Node<>(newEntry, head’); // head’ = whatever previous is pointing tohead = new Node<>(newEntry, head);previous.next = new Node<>(newEntry, previous.next);Inserting Nodes (anywhere)Locate ‘previous’ and call previous.addNodeAfter(13 ) public void addNodeAfter(T value) { next = new Node<T>(value, next);}Removing the Head Node10157nullhead13Removing the Head Node10157nullhead13Removing the Head Node•head = ?•head = head.next;10157nullhead13Removing the Head Node10157nullheadRemoving a Node (anywhere)Locate ‘previous’ and call previous. removeNodeAfter( )previous = node before the one that needs to be removedpublic void removeNodeAfter( ) { next = next.next;} Precondition: This node must not be the tail node of the


View Full Document

MASON CS 310 - Linked Lists

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?