Doubly Linked Lists
Linked lists come in a number of different flavors. The linked list we’ve discussed until this point is the classic linked list, but with some slight modifications we can grant linked lists additional superpowers.
One variant form of the linked list is the doubly linked list.
A doubly linked list is like a linked list except that each node has two links—one that points to the next node and another that points to the previous node. In addition, the doubly linked list always keeps track of both the head and tail nodes, instead of just the head.
Here’s what a doubly linked list looks like:
We can implement the core of a doubly linked list in Python like this. First, we must create a new kind of “double-ended” node:
| | class Node: |
| | |
| | def __init__(self, data): |
| | self.data = data |
| | self.next_node = None |
| | self.previous_node = None |
You’ll notice how each node now contains not just a next_node attribute but a previous_node attribute as well.
Once we have that in place, we can now implement our doubly linked list:
| | import double_ended_node |
| | |
| | |
| | class DoublyLinkedList: |
| | |
| | def __init__(self, first_node=None, last_node=None): |
| | self.first_node = first_node |
| | self.last_node = last_node |
Since a doubly linked list always knows where both its head and tail are, we can access each of them in a single step, or O(1). So just as we can read, insert, or delete from the beginning of the list in O(1), we can do the same from the end of the list in O(1) as well.
Here’s a depiction of inserting at the end of a doubly linked list:
As you can see, we create a new node ("Sue") and have its previous_node point to what used to be the last_node ("Greg") of the linked list. Then we change the next_node of the last_node ("Greg") to point to this new node ("Sue"). Finally, we declare the new node ("Sue") to be the last_node of the linked list.
Code Implementation: Doubly Linked List Insertion
We’ll look next at the implementation of a new append method that we can add to our DoublyLinkedList class. Instead of inserting a value anywhere in the list, the append method simply adds a new value at the end of the list. We’re focusing on appending, rather than classical inserting, simply to highlight how easy and fast it is to append to a doubly linked list. Here’s the append method:
| | def append(self, value): |
| | new_node = double_ended_node.Node(value) |
| | |
| | if not self.first_node: |
| | self.first_node = new_node |
| | self.last_node = new_node |
| | else: |
| | new_node.previous_node = self.last_node |
| | self.last_node.next_node = new_node |
| | self.last_node = new_node |
Let’s highlight the most important parts of this method.
First, we create the new node:
| | new_node = double_ended_node.Node(value) |
At first, our code handles the case where the list doesn’t contain any nodes yet. But let’s jump to the case where we append to an existing list.
We set the previous_node link of the new_node to point to what until this point was the last node:
| | new_node.previous_node = self.last_node |
Then we change the last node’s link (which was None until this point) and have it point to our new_node:
| | self.last_node.next_node = new_node |
Last, we tell our instance of the DoublyLinkedList that its last node is our new_node:
| | self.last_node = new_node |
Moving Forward and Backward
With a classic linked list, we can only move forward through the list; that is, we can access the first node and follow the links to find all the other nodes of the list. But we’re not able to move backward, as no node is aware of what the previous node is.
A doubly linked list allows for a lot more flexibility, as we can move both forward and backward through the list. In fact, we can even start with the tail and work our way backward to the head.
