Linked List
Table of Contents
Concept
A linked list is a data structure that consists of a collection of nodes whose order is not related to their physical placement in memory.
Each node contains data and pointers which refer to different nodes in the sequence.
The first node in the list is called Head, and the last is called Tail.
There are many different variations for a linked list according to what each node points to sequentially.
Singly Linked List
There is only one pointer in a node that refers to the next node in the sequence.
The tail node in a singly linked list has no pointer to the next node because the next node does not exist. In addition, the singly linked list does not provide access to previous nodes from every node.
Head Tail
| +--------+ +--------+ +--------+ +--------+ |
+--> | 21 | +-+--> | 42 | +-+--> | 19 | +-+--> | 37 | + | <--+
+--------+ +--------+ +--------+ +--------+
But, its implementation is straightforward and uses less memory.
Doubly Linked List
A node has two pointers which refer to the previous and next nodes, respectively.
In a doubly linked list, the tail node has no next node, and the head has no previous node.
Head Tail
| +------------+ +------------+ +------------+ +------------+ |
+--> | | 21 | +-+--> | | 42 | +-+--> | | 19 | +-+--> | | 37 | + | <--+
| + | | | <--+-+ | | | <--+-+ | | | <--+-+ | | |
+------------+ +------------+ +------------+ +------------+
It takes twice as much memory as a singly linked list because of two pointers of each node, but it can be traversed backward.
Circular Linked List
Both ends of the linked list are connected.
In a singly linked list, the tail node refers to the head node.
Head Tail
| +--------+ +--------+ +--------+ +--------+ |
+--> | 21 | +-+--> | 42 | +-+--> | 19 | +-+--> | 37 | + | <--+
+--------+ +--------+ +--------+ +------|-+
^ |
| |
+----------------------------------------------+
In a doubly linked list, the head and tail nodes refer to each other.
+--------------------------------------------------------------+
| |
Head | v Tail
| +-|----------+ +------------+ +------------+ +------------+ |
+--> | | | 21 | +-+--> | | 42 | +-+--> | | 19 | +-+--> | | 37 | + | <--+
| + | | | <--+-+ | | | <--+-+ | | | <--+-+ | | | |
+------------+ +------------+ +------------+ +----------|-+
^ |
| |
+--------------------------------------------------------------+
So, it can be traversed forward and backward from anywhere.
When to use
- Used to implement some other common abstract data types: List, Queue, Stack, and Associative Arrays (Often used in the implementation of adjacency lists for graphs)
- Easy to create a circular list
- Easy to model real world objects, such as trains, that are sequential
- Used in separate chaining of certain Hash Table implementations to deal with hashing collisions
Complexity
| Operation | Singly Linked List | Doubly Linked List |
|---|---|---|
| Search | $O(n)$ | $O(n)$ |
| Insert at head | $O(1)$ | $O(1)$ |
| Insert at tail | $O(1)$ | $O(1)$ |
| Insert in the middle | $O(n)$ | $O(n)$ |
| Delete at head | $O(1)$ | $O(1)$ |
| Delete at tail | $O(n)$ | $O(1)$ |
| Delete in the middle | $O(n)$ | $O(n)$ |
- $n$ is the number of nodes.
- Peeking(=getting an index) from a linked list takes linear time as it traverses from head to tail.
- Deleting a node in the middle of a linked list requires finding the node’s previous node.
- It is why deletion at the tail in a singly linked list takes linear time since it should traverse from head to tail to find the previous node.
- But, a doubly linked list does not have to do that where the tail node has the pointer to its previous node, so it is possible to access the previous node in constant time.
Implementation
The two classes have a common interface but perform slightly different operations depending on the class.
Singly Linked List
Search
It is simple to traverse a linked list from the first to the last node just by following the next pointer of each node.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class SinglyLinkedList(LinkedList):
def __init__(self) -> None:
self._size = 0
self.head = None
self.tail = None
def search(self, data: object) -> ListNode:
node = self.head
while node:
if node.data == data:
return node
node = node.next
return None
# Must guarantee to return None if a given index is outside the boundary.
def search_by_index(self, at: int) -> ListNode:
node = self.head
for i in range(self._size):
if i == at:
return node
node = node.next
return None
Insertion
Notice that we should update the pointers of the two nodes.
- A new node
- The previous node of the node at position we want to add
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class SinglyLinkedList(LinkedList):
# ...
def insert(self, at: int, data: object) -> None:
if at > self._size:
raise Exception(f"cannot insert at index {at}.")
node = SllNode(data)
if at == 0:
# Insert at head.
if self.head is None:
self.head, self.tail = node, node
else:
node.next = self.head
self.head = node
elif at == self._size:
# Insert at tail.
self.tail.next = node
self.tail = node
else:
# Insert in the middle.
prev_node = self.search_by_index(at - 1)
node.next = prev_node.next
prev_node.next = node
self._size += 1
return None
Deletion
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class SinglyLinkedList(LinkedList):
# ...
def delete(self, at: int) -> ListNode:
if at >= self._size:
raise Exception(f"cannot delete at index {at}.")
deleted = None
if at == 0:
# Delete at head.
if self.head == self.tail:
self.tail = None
deleted = self.head
self.head = deleted.next
else:
# Delete at tail or in the middle.
prev_node = self.search_by_index(at - 1)
deleted = prev_node.next
prev_node.next = deleted.next
if deleted == self.tail:
self.tail = prev_node
deleted.reset()
self._size -= 1
return deleted
Doubly Linked List
Search
Finding a specific node more quickly than in a singly linked list is interesting because a doubly linked list can traverse nodes backward.
- If a given index is less than half the number of nodes, then iterate over nodes from the head node.
- Otherwise, iterate over nodes from the tail node reversely.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class DoublyLinkedList(LinkedList):
def __init__(self) -> None:
self._size = 0
self.head = None
self.tail = None
def search_by_index(self, at: int) -> ListNode:
if at < self._size // 2:
node = self.head
for i in range(self._size):
if i == at:
return node
node = node.next
elif at < self._size:
node = self.tail
for i in range(self._size - 1, 0, -1):
if i == at:
return node
node = node.prev
return None
# Same as a singly linked list.
def search(self, data: object) -> ListNode:
node = self.head
while node:
if node.data == data:
return node
node = node.next
return None
Insertion
To insert a new node, we should change the pointers of the three nodes below.
- The node at position we want to add
- The previous node of the node
- A new node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class DoublyLinkedList(LinkedList):
# ...
def insert(self, at: int, data: object) -> None:
if at > self._size:
raise Exception(f"cannot insert at index {at}.")
node = DllNode(data)
if at == 0:
# Insert at head.
if self.head is None:
self.head, self.tail = node, node
else:
self.head.prev = node
node.next = self.head
self.head = node
elif at == self._size:
# Insert at tail.
self.tail.next = node
node.prev = self.tail
self.tail = node
else:
# Insert in the middle.
prev_node = self.search_by_index(at - 1)
node.next = prev_node.next
node.prev = prev_node
prev_node.next.prev = node
prev_node.next = node
self._size += 1
return None
Deletion
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class DoublyLinkedList(LinkedList):
# ...
def delete(self, at: int) -> ListNode:
if at > self._size:
raise Exception(f"cannot insert at index {at}.")
deleted = None
if at == 0:
deleted = self.head
if self.head == self.tail:
self.tail = None
self.head = deleted.next
if self.head:
self.head.prev = None
elif at == self._size - 1:
deleted = self.tail
self.tail = deleted.prev
if self.tail:
self.tail.next = None
else:
# Delete in the middle.
deleted = self.search_by_index(at)
deleted.prev.next = deleted.next
deleted.next.prev = deleted.prev
deleted.reset()
self._size -= 1
return deleted
Application
Linked List vs. Dynamic Array
A dynamic array is a data structure that allocates all elements contiguously in memory, and keeps a count of the current number of elements. If the space reserved for the array is exceeded, a new greater space is reallocated and elements in an old space are copied, which is a highly expensive operation.
Note that a number $n$ is the number of entities (elements or nodes) in a data structure.
Time Complexity
| Operation | Dynamic Array | Doubly Linked List |
|---|---|---|
| Construction | $O(n)$ | $O(1)$ |
| Peek(Indexing) at the beginning | $O(1)$ | $O(1)$ |
| Peek(Indexing) at the end | $O(1)$ | $O(1)$ |
| Peek(Indexing) in the middle | $O(1)$ | $O(n)$ |
| Insert/Delete at the beginning | $O(n)$ | $O(1)$ |
| Insert/Delete at the end | $O(n)$ | $O(1)$ |
| Insert/Delete in the middle | $O(n)$ | $O(n)$ |
- For construction, it is natural to assign a fixed-size of array at first while a linked list starts with the head and tail node.
- For peeking, random access in the array is possible due to indices, which are different from a linked list that does not have an index.
- For insertion and deletion, moving elements behind the inserted or deleted element in the array is inevitable. However, the linked list does not have to do that; it just needs the change of pointers. Nevertheless, in the linked list, we first need to search for the previous node of the node at the position we insert or delete, which takes linear time.
Space Complexity
Both take $O(n)$ space, but its storing ways are different.
In terms of memory space, it’s good to read the comparison between array and list in Python.
Leetcode
- See my list.