COMP 250
INTRODUCTION TO COMPUTER SCIENCE
Week 5-3 : Doubly Linked Lists
Giulia Alberini, Fall 2020
WHAT ARE WE GOING TO DO IN THIS VIDEO?
Doubly Linked Lists
LINKED LISTS
IMPLEMENTATIONS
There are different implementations of a list:
Array list
Singly linked list Doubly linked list
Idea: the elements in the list are linked using pointers
DOUBLY LINKED LIST
next prev element
null
Each node has a reference to the next node and to the previous node.
head tail
size
4
null
DOUBLY LINKED LIST NODE
class DNode { Shape element; DNode next; DNode prev;
}
next prev element
null
null
myNode
DNode myNode = new DNode();
n.element = new Shape( );
DOUBLY LINKED LIST
public class DLinkedList {
private DNode head;
private DNode tail;
private int size;
:
private class DNode {
Shape element;
DNode next;
DNode prev;
} }
next prev
element
null
4
list
head
tail
size
null
DLinkedList list = new DLinkedList();
:
DOUBLY LINKED LIST – removeLast()
tail = tail.prev;
tail.next.prev = null; // not necessary
tail.next = null;
size = size – 1;
next prev
element
null
5
// to return the element,
// you need to do a bit more work
list
head
tail
size
// edge cases for size = 0 and 1 to be added
null
DOUBLY LINKED LIST – removeLast()
tail = tail.prev;
tail.next.prev = null; // not necessary
tail.next = null;
size = size – 1;
next prev
element
null
4
// to return the element,
// you need to do a bit more work
list
head
tail
size
// edge cases for size = 0 and 1 to be added
null
For a doubly linked list, removing the last element is much faster.
null
null
WORSE CASE TIME COMPLEXITY (N = LIST SIZE)
addFirst() removeFirst() addLast() removeLast()
array list O( N ) O( N )
O( 1 ) O( 1 )
SLinkedList
O( 1 ) O(1) O( 1 ) O(1)
O(1) O(1)
DLinkedList
O(N) O(1)
OTHER LIST OPERATIONS
Many list operations require access to a specific node i get(i)
set(i, e)
add(i, e)
remove(i) :
LINKED LISTS
Suppose we want to access general node i in a linked list. Two issues arise:
• Edge cases (i = 0, i = size – 1) require extra code. This is a pain and can lead to coding errors.
• How long does it take to access node i?
AVOID EDGE CASES WITH “DUMMY NODES”
public class DLinkedList {
private DNode dummyHead;
private DNode dummyTail;
private int size;
:
public DLinkedList(){
dummyHead = new DNode(); dummyTail = new DNode(); dummyHead.next = dummyTail; dummyTail.prev = dummyHead; size =0;
} }
// empty list
DLinkedList list = new DLinkedList();
next prev element
null
null
0
list
dummyHead dummyTail
size
null
null
AVOID EDGE CASES WITH “DUMMY NODES”
DLinkedList list = new DLinkedList(); // add 2 elements…
public class DLinkedList {
private DNode dummyHead;
private DNode dummyTail;
private int size;
:
public DLinkedList(){
dummyHead = new DNode(); dummyTail = new DNode(); dummyHead.next = dummyTail; dummyTail.prev = dummyHead; size =0;
} }
next prev element
null
null
2
list
dummyHead
dummyTail
size
null
null
HOW DO WE ACCESS A NODE? – get()
public Shape get(int i) {
DNode node = getNode(i);
return node.element;
}
next prev element
null
null
private DNode getNode(int i) { // verify that 0<=i
node = node.prev;
}
return node;
}
next prev element
null
null
2
list
dummyHead
dummyTail
size
null
null
JAVA LINKEDLIST CLASS
https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html
It uses a doubly linked list as the underlying data structure.
It has some methods that ArrayList doesn’t have e.g.: addFirst()
removeFirst() addLast()
removeLast()
Why ?
Q: What is the time complexity of the following ?
DLinkedList list = new DLinkedList( ) ;
for (k = 0; k < N; k ++) // N is some constant
list.addFirst(...);
Q: What is the time complexity of the following ?
DLinkedList list = new DLinkedList( ) ;
for (k = 0; k < N; k ++) // N is some constant
list.addFirst(...);
A: 𝟏+𝟏+𝟏+ .... 𝟏 =𝑵 ⇒ 𝑶(𝑵) where ‘1′ means constant.
Q: What is the time complexity of the following ?
for (k = 0; k < list.size(); k ++) // size == N list.get( k );
Assuming here that getNode(i) always starts at the head.
Q: What is the time complexity of the following ?
for (k = 0; k < list.size(); k ++) // size == N list.get( k );
Assuming here that getNode(i) always starts at the head. A: 𝟏+𝟐+𝟑+....𝐍
= 𝑵 𝑵+𝟏 ⇒ 𝑶(𝑵𝟐) 𝟐
In 3 weeks we’ll talk about a more efficient way to iterate through elements in a (Java) LinkedList!
WHAT ABOUT “SPACE COMPLEXITY” ?
null
null
null
null
null
null
null
All three data structures use space O(N) for a list of size N. But linked lists use 2x (single) or 3x (double).
ARRAYLISTVERSUSLINKEDLIST ?
Array lists and linked lists both take O(N) time to add or remove from an arbitrary position in the list.
In practice and when N is large, array lists are faster. But the reasons are subtle and have to do with how computer memory works, in particular, how caches exploit contiguous memory allocation. You will learn about that topic in COMP 273.
DO YOU EVER NEED LINKED LISTS ?
Yes. Even if you prefer ArrayLists, you still need to understand LinkedLists. Linked lists are special cases of a general and widely used data structure called a tree which we will be discussing extensively.
In the next videos:
Quadratic sorting algorithms Asymptotic notations