13-Doubly Linked List data structure.pdf

13-Doubly Linked List data structure.pdf

1. Doubly-Linked Lists
15-121 Fall 2020
Margaret Reid-Miller

2. Today
•Exam 1: mean 86, high 98
Amazing!!
•Hw6willbepostedtonight
•Change Hwdue dates?
PlanforToday
•Singly-linked list removed at index method
•Java's LinkedList class
•Doubly-linked lists
Fall 202015-121 (Reid-Miller)2

3. 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 can
always 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

4. Exercise: Remove at given index
// Removes the object at the given index.
// Returns the object removed
public E remove(intindex) {
if (index < 0 || index > size())
throw new IndexOutOfBoundsException();
Fall 202015-121 (Reid-Miller)4

5. Remove at index 3 goal
Fall 202015-121 (Reid-Miller)5
first
remove here
(index = 3)
null
2
obj

6. Remove at given index
// Removes the object at the given index.
// Returns the object removed
public E remove(intindex) {
if (index < 0 || index > size())
throw new IndexOutOfBoundsException();
if (index == 0) {
return removeFirst();
}
…
// cont’d
Fall 202015-121 (Reid-Miller)6

7. Remove at given index (cont’d)
…
Node nodeBefore= first;
for (inti= 0; ; i++) {
nodeBefore= nodeBefore.next;
}
// remove the node
…
size--;
return obj;
}
Fall 202015-121 (Reid-Miller)7

8. Remove at index 3
Fall 202015-121 (Reid-Miller)8
first
remove here
(index = 3)
current
WRONG
1. current.next= current.next.next;
2. E obj= current.next.data;
null
2
2
obj
1

9. Remove at index 3
Fall 202015-121 (Reid-Miller)9
first
remove here
(index = 3)
current
Correct
1. E obj= current.next.data;
2. current.next= current.next.next;
null
21
obj
2

10. Remove at given index (cont’d)
…
Node nodeBefore= first;
for (inti= 0; i< index-1; i++) {
nodeBefore= nodeBefore.next;
}
// remove the node
E obj= nodeBefore.next.data;
nodeBefore.next= nodeBefore.next.next;
size--;
return obj;
}
Fall 202015-121 (Reid-Miller)10

11. Remove at given index (cont’d alternate)
…
Node nodeBefore= first;
for (inti= 0; i< index-1; i++) {
nodeBefore= nodeBefore.next;
}
// remove the node
Node nodeToRemove= nodeBefore.next;
nodeBefore.next= nodeToRemove.next;
size--;
return nodeToRemove.data;
}
Fall 202015-121 (Reid-Miller)11

12. Complexity
On a singly linked list with n nodes:
WorstAverageBest
addFirst__________________
removeFirst__________________
add(index, obj)__________________
remove(index)__________________
Fall 202015-121 (Reid-Miller)12
O(n) O(n) O(1)
O(n) O(n) O(1)
O(1)
O(1)

13. Disadvantages of
Singly-Linked Lists
•Insertion into a list is generally linear.
•In order to insert a node at an index greater
than 0, we need a reference to the previous
node.
•In order to remove a node that is not the first
node, we need a reference to the previous
node.
•We can only traverse the list in one direction.
Fall 202015-121 (Reid-Miller)13

14. Java's LinkedList class
Java's LinkedList add(E obj)method runtime is O(1).
How?
LinkedList has a field that refers to the
last node in the list.
Java's LinkedList remove(intindex)method runtime
is O(1). How is it possible even if your have the last
node?
The nodes inside LinkedList are doubly linked in
order to remove from the end of the list in O(1) time.
Fall 202015-121 (Reid-Miller)14

15. Doubly-Linked Lists
Fall 202015-121 (Reid-Miller)15
prevdata next
null
last
null
first

16. Doubly-Linked Lists
•Each dataentry is stored in its own node
•Each node as two references: one reference is to the
nextnode and one is to the previous node (prev).
•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 tail references
equal to null
Fall 202015-121 (Reid-Miller)16

17. Node class
private 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

18. 1. To add a node at agivenindex
find the node at index-1
Fall 202015-121 (Reid-Miller)18
null
last
null
first
nullnull
before
newNode

19. 4. Result of adding at given index
Fall 202015-121 (Reid-Miller)21
null
last
null
first

20. How would you implement addFirst?
Fall 202015-121 (Reid-Miller)22
null
last
null
first
How would you implement addLast?

21. How would you remove the node
referenced by current?
Fall 202015-121 (Reid-Miller)23
null
last
null
firstcurrent

22. How would you remove the node if
current == first?
Fall 202015-121 (Reid-Miller)24
null
last
null
firstcurrent

23. How would you remove the node if
current == last?
Fall 202015-121 (Reid-Miller)25
null
last
null
firstcurrent

24. How would you remove the node
currentif first == tail?
Fall 202015-121 (Reid-Miller)26
tail
null
head
null
current

25. Doubly-linked list complexity
intsize()
booleanadd(E obj)
void add(intindex, E obj)
E get(intindex)
E set(intindex, E obj)
booleancontains(Object obj)
intindexOf(Object obj)
E remove(intindex)
booleanremove(Object obj)
Fall 202015-121 (Reid-Miller)27
WorstAverageBest
O(1)
O(1)
O(n) O(n) O(1)
O(n)O(n)O(1)
O(n) O(n)O(1)
O(n) O(n) O(1)
O(n) O(n) O(1)
O(n) O(n) O(1)
O(n) O(n) O(1)