Doubly Linked List
In a singly linked list, each node maintains a reference to the node that is immediately after it. But recall that we are unable to delete a node at the tail of a list efficiently.
![](image/alg-sll-removelast.png)
To boost the efficiency, we define a linked list in which each node keeps an explicit reference to the node before it and a reference to the node after it. Such ADT is known as a doubly link list, and it allows a greater variety of \(O(1)\) update operations. We continue to use the term next
for the reference to the node that follows another, and we introduce the term prev
for the preference to the node that precedes it.
Head and Trailer sentinels
As we can see, we need to address some special cases (e.g., the size is 0/1) when implementing an API for linked lists. In order to avoid such boundaries checking, it helps to add special nodes at both ends of the list:
- A
header
node at the beginning of the list - A
trailer
node at the end of the list.
These dummy nodes are referred to sentinels (or guards), and they do not store elements of the primary sequence.
![](image/dummy.png)
Although we could implement a doubly linked list without sentinel nodes (just as we did with the singly linked list), the slight extra memory devoted to the sentinels greatly simplifies the logic of our operations for the simple reason that both header and trailer always exist, and they will never be changed.
Let's see an example to show the convenience brought by header
sentinel in a singly linked list for addLast()
method.
![](image/alg-sll-addlast3.png)
Because there would always be an existing header
, the code becomes succinct because we do not have to handle the case when its head
is null
.
A few notes for an empty list
Suppose Node
has a constructor Node(Item item, Node<Item> prev, Node<Item> next)
. Initially, the empty list is constructed using the following code:
header = new Node<>(null, null, null);
trailer = new Node<>(null, header, null); // trailer is preceded by header
header.next = trailer; // header is followed by trailer
Common Operations
In what follows, we will present how to implement a doubly linked list by showing its common operations. To save the space, only update operations (add/remove) are discussed. The complete code can be found at DoublyLinkedList.java and doubly_linked_list.py.
add
First, we present a helper method to add an element between predecessor
and successor
.
![](image/alg-dll-add.png)
Therefore, addFirst(e)
and addLast(e)
can be respectively described as:
addBetween(header, header.next, e)
addBetween(trailer.prev, trailer, e)
remove
We also prepare a helper method to remove a specific node from the list.
![](image/alg-dll-remove.png)
Therefore, removeFirst()
and removeLast()
can be respectively described as1:
remove(header.next)
remove(trailer.prev)
A few notes on Python's exceptions
For simplicity, we did not pass messages to exceptions when implementing the removing operations. For example,
def remove_first(self):
if self.is_empty():
raise NoElement
self._remove(self._header.next)
Note that raise NoElement
and raise NoElement()
do the same thing. See more at Is there a difference between "raise exception()" and "raise exception" without parenthesis?.
1 As for removing, it is still required to check whether it is empty.