Doubly Linked Lists
by Jakub Brettl
This is a second post related to linked lists. The first post focuses on singly linked lists and a broad overview of linked lists.
There are many similarities between singly linked and doubly linked lists. In this post, I will focus on key specificities of doubly linked lists. If you would like more high level overview of linked lists please have a look at the first post.
Doubly linked lists look as follows:
The key distinguishing feature here is that each node has two pointers; one to the next node and the other to the previous node. The first and last node too have two pointers. In the case of the head the pointer to the "previous node points to "None". The last node, too, has a pointer to "None". It is the one pointing to the next node.
Doubly Linked List Operations
Like in the case of singly linked lists, there are three fundamental operations on linked lists. They are:
- Insert/delete new head
- Insert/delete new tail
- Insert/delete at specified position of the list
Doubly linked list Python instance
Initialisation of doubly linked list follows the exact principles as do singly link lists. First we initialise the node, then we initialise the list instance. The only difference with singly linked lists is that the node instance also has a pointer to the previous node of the list ('self.previous = previous').
class Node:
"""Initiate node instance of a list."""
def __init__(self, data=None, next=None, previous=None):
self.data = data
self.next = next
self.previous = previous
class DoublyLinkedList(object):
"""Initiate new instance of a doubly linked list."""
def __init__(self, head=None, next=None):
self.head = head
Inserting new nodes
First, lets examine a case where we want insert a new head node. The process works in the following way:
First create new node.
Then the "next" pointer of the new node is pointed to the existing head.
Finally, "previous" pointer of the old head is pointed to the new node and "head" pointer is moved to the new node.
Secondly, lets look at a case where we want to insert a new tail node:
First create new node.
Then the "previous" pointer of the new node is pointed to the existing tail.
Finally, "next" pointer of the old tail is pointed to the new node.
Lastly, inserting a new node at any intermediate position:
First create new node.
Finally pointers of the new node are pointed to the surrounding nodes and vice versa.
In Python, all of the above operations can be implemented using the simple code below.
def insert_head(self, data):
self.insert_anywhere(0, data)
def insert_tail(self,data):
self.insert_anywhere(len(self), data)
def insert_anywhere(self, position, data):
if not 0 <= position <= len(self):
raise IndexError('Index out of range.')
newNode = Node(data)
if self.head is None:
self.head = self.tail = newNode
elif position == 0:
self.head.previous = newNode
newNode.next = self.head
else:
temp = self.head
for i in range(0,position-1):
temp = temp.next
newNode.previous = temp
temp.next = newNode
newNode.next = None
Deleting nodes
Text
def delete_head(self):
self.delete_anywhere(0)
def delete_tail(self):
self.delete_anywhere(len(self)-1)
def delete_anywhere(self, position):
if not 0 <= position <= len(self)-1:
raise IndexError('Index out of range.')
delete_node = self.head
if len(self) == 1:
self.head = self.head.next
elif position == 0:
self.head = self.head.next
self.head.previous = None
elif position == len(self) - 1:
temp = self.head
for i in range(0, position):
temp = temp.next
temp.previous.next = None
else:
temp = self.head
for i in range(0, position-1):
temp = temp.next
temp.previous.next = temp.next
temp.next.previous = temp.previous
Concluding notes
I wrote other blog posts on the implementation of linked lists. Namely:
All code that used in the blog post can be found in this GitHub repo.