Transcription
Doubly-Linked Lists15-121 Fall 2020Margaret Reid-Miller
Today Exam 1: mean 86, high 98Amazing!! Hw6 will be posted tonight Change Hw due dates?Plan for Today Singly-linked list removed at index method Java's LinkedList class Doubly-linked listsFall 202015-121 (Reid-Miller)2
Singly-linked list Add at index 3 Insert node between nodes at index 2 and 3. Think add “after 2,” not “before 3,” as you canalways add AFTER a node. When do you need to consider a special case?When you add the first node (after head). Remove at index 3 Remove returns the value of the node removed. Like add, need to remove the node “after 2” Are there any special cases to consider?Fall 202015-121 (Reid-Miller)3
Exercise: Remove at given index// Removes the object at the given index.// Returns the object removedpublic E remove(int index) {if (index 0 index size())throw new IndexOutOfBoundsException();Fall 202015-121 (Reid-Miller)4
Remove at index 3 goalfirstnull2objFall 2020remove here(index 3)15-121 (Reid-Miller)5
Remove at given index// Removes the object at the given index.// Returns the object removedpublic E remove(int index) {if (index 0 index size())throw new IndexOutOfBoundsException();if (index 0) {return removeFirst();} // cont’dFall 202015-121 (Reid-Miller)6
Remove at given index (cont’d) Node nodeBefore first;for (int i 0;; i ) {nodeBefore nodeBefore.next;}// remove the node size--;return obj;}Fall 202015-121 (Reid-Miller)7
Remove at index 3firstcurrent1null2remove here(index 3)WRONG2obj1. current.next current.next.next;2. E obj current.next.data;Fall 202015-121 (Reid-Miller)8
Remove at index 3firstcurrent2null1obj2remove here(index 3)Correct1. E obj current.next.data;2. current.next current.next.next;Fall 202015-121 (Reid-Miller)9
Remove at given index (cont’d) Node nodeBefore first;for (int i 0; i index-1; i ) {nodeBefore nodeBefore.next;}// remove the nodeE obj nodeBefore.next.data;nodeBefore.next nodeBefore.next.next;size--;return obj;}Fall 202015-121 (Reid-Miller)10
Remove at given index (cont’d alternate) Node nodeBefore first;for (int i 0; i index-1; i ) {nodeBefore nodeBefore.next;}// remove the nodeNode nodeToRemove nodeBefore.next;nodeBefore.next nodeToRemove.next;size--;return nodeToRemove.data;}Fall 202015-121 (Reid-Miller)11
ComplexityOn a singly linked list with n nodes:Worst Average BestaddFirstO(1)removeFirstO(1)add(index, obj)O(n)O(n)O(1)remove(index)O(n)O(n)O(1)Fall 202015-121 (Reid-Miller)12
Disadvantages ofSingly-Linked Lists Insertion into a list is generally linear. In order to insert a node at an index greaterthan 0, we need a reference to the previousnode. In order to remove a node that is not the firstnode, we need a reference to the previousnode. We can only traverse the list in one direction.Fall 202015-121 (Reid-Miller)13
Java's LinkedList classJava's LinkedList add(E obj) method runtime is O(1).How?LinkedList has a field that refers to thelast node in the list.Java's LinkedList remove(int index) method runtimeis O(1). How is it possible even if your have the lastnode?The nodes inside LinkedList are doubly linked inorder to remove from the end of the list in O(1) time.Fall 202015-121 (Reid-Miller)14
Doubly-Linked Listslastfirstprev data nextnullFall 2020null15-121 (Reid-Miller)15
Doubly-Linked Lists Each data entry is stored in its own node Each node as two references: one reference is to thenext node and one is to the previous node (prev). A reference, often referred to as head, points to thefirst node in the list and one reference, often referredto as tail, points the the last node in the list. The head node’s prev reference is null and the tailnode’s next reference is null. An empty list would have head and tail referencesequal to nullFall 202015-121 (Reid-Miller)16
Node classprivate class Node {private E data;private Node prev;private Node next;private Node(E obj, Node previous, Node next){data obj;prev previous;this.next next;}Fall 202015-121 (Reid-Miller)17
1. To add a node at a given indexfind the node at index-1firstbeforelastnullnullnullnullnewNodeFall 202015-121 (Reid-Miller)18
4. Result of adding at given indexlastfirstnullFall 2020null15-121 (Reid-Miller)21
How would you implement addFirst?lastfirstnullnullHow would you implement addLast?Fall 202015-121 (Reid-Miller)22
How would you remove the nodereferenced by current?firstcurrentlastnullFall 2020null15-121 (Reid-Miller)23
How would you remove the node ifcurrent first?firstcurrentlastnullFall 2020null15-121 (Reid-Miller)24
How would you remove the node ifcurrent last?currentfirstnullFall 2020lastnull15-121 (Reid-Miller)25
How would you remove the nodecurrent if first tail?headnulltailnullcurrentFall 202015-121 (Reid-Miller)26
Doubly-linked list complexityint size()boolean add(E obj)void add(int index, E obj)E get(int index)E set(int index, E obj)boolean contains(Object obj)int indexOf(Object obj)E remove(int index)boolean remove(Object obj)Fall 202015-121 (Reid-Miller)Worst Average n)O(n)O(1)O(n)O(n)O(1)O(n)O(n)O(1)O(n)O(n)O(1)27
A reference, often referred to as head, points to the first node in the list and one reference, often referred to as tail, points the the last node in the list. The head node’s prevreference is null and the tail node’s next reference is null. An empty list would have head and
