Doubly-Linked List in Python

A linked-list is a type of data structure that is made up of elements called  nodes. Unlike an array, where elements are stored in contagious memory locations, the nodes in a linked-list are scattered in memory. The nodes are connected through the use of pointers, each node contains a reference to the location of the next node in the list.

There are various types of linked lists. In this article we will focus on doubly-linked lists.

In a doubly linked list, each node contains a reference to both the next node and the previous node. This allows  for efficient traversal of the list in both forward and backward directions.

In most practical cases, doubly-linked lists are used for implementing  other data structures such as queues. In the next parts we will learn how to implement a double-ended queue using doubly-linked list.

The Node class 

To represent a node in a doubly linked lists, we will create a non-public class called _Node with the following attributes:

The implementation of the _Node class is as shown below

class _Node:
    def __init__(self, e, prev, next):
        self._element = e #The value stored by the node
        self._prev = prev #The prev node in the list
        self._next = next #The next node in the list
 Visualize 

[Finished in 0.010511231841519475s]

Linked double-ended Queue

A double-ended queue, popularly known as deque(pronounced as "deck"),  is a type of queue in which elements can be added or removed from either side. These makes it more versatile than a regular queue in which elements can only be added in one end and removed from the other.

A Double ended queue typically supports the following operations.

In the following parts we will go on to implement the LinkedDeque class to represent a double-ended queue using doubly-linked list.

Implement the basic structure

In this part we will implement the basic structure of the LinkedDeque class. The _Node class will be implemented as a non-public subclass.

We will use sentinel/dummy nodes, _head and _tail at the front and the back of the list respectively, doing this simplifies the insertion and removal operations, as we will see in a while. The front sentinel will always point to the beginning of the list, and the back sentinel will always point to the end of the list.

class LinkedDeque:
    #the _Node subclass
    class _Node:
       def __init__(self, e, prev, next):
           self._element = e
           self._prev = prev
           self._next = next

    #The constructor
    def __init__(self):
        self._head = LinkedDeque._Node(None, None, None) #The front sentinel node.
        self._tail = LinkedDeque._Node(None, self._head, None) #The back sentinel node, with the _head as its previous node
        self._head._next = self._tail #update the _head sentinel so that _tail becomes the next node

        self._size = 0 # The number of non-sentinel nodes
 
    def __len__(self):
        return self._size # The number of elements in the deque

    def is_empty(self):
        return len(self) == 0 
 Visualize 

[Finished in 0.010085163172334433s]

Implementing the __len__() method makes it possible to use the builtin len() function to check the number of elements in the deque. 

Implement front() and back()

In this part we will implement front() and back() methods. The methods will raise an error if the deque is empty.

#an exception to be raised if the deque is empty
class Empty(Exception):
    pass

class LinkedDeque:
    #this part is ommitted refer to the previous snippet
    def front(self):
        if self.is_empty():
            raise Empty("Deque is empty")
        return self._head._next._element # Return the element of the next node after the sentinel _head

    def back(self):
        if self.is_empty():
            raise Empty("Deque is empty")
        return self._tail._prev._element # Return the element of the previous node before the sentinel _tail.
 Visualize 

[Finished in 0.009859454119578004s]

Implement insert_front() and insert_back()

In this section we will implement the insert_front() and insert_back() methods. However to prevent redundancy, we will implement a more generic non-public method, _insert_between() which we will call within the insert_front() and insert_back() methods. 

class LinkedDeque:
    #this part is ommitted refer to the previous sections
    def _insert_between(self, e, node1, node2):
        newnode = LinkedDeque._Node(e, node1, node2) #create a node with node1 and node2 as previous and next, respectively
        node1._next = newnode
        node2._prev = newnode
        self._size += 1

    def insert_front(self, e):
        self._insert_between(e, self._head, self._head._next) # Call the _insert_between method

    def insert_back(self, e):
        self._insert_between(e, self._tail._prev, self._tail)
 Visualize 

[Finished in 0.011052093002945185s]

The _insert_between() method in the above example, helps us to avoid repetition when implementing the  insert_front() and insert_back() methods. By using _insert_between(), we are able to pass in the correct parameters to specify where the new node should be inserted without having to duplicate the code for creating and updating the pointers.

The implementation and usefulness of the _insert_between() method above illustrates the importance of using sentinel nodes.

Implement remove_front() and remove_back()

In this final step we will implement the remove_front() and remove_back() methods. Like in previous section, we will use a non-public methods _remove_node() that will be called by the two public methods.

class LinkedDeque:
    #this part is ommitted refer to the previous sections
    def _remove_node(self, node):
        prev = node._prev
        next = node._next
        
        #relink the remaining nodes
        prev._next = next 
        next._prev = prev

        self._size -= 1

        element = node._element

        #deprecate the removed node
        node._element = node._prev = node._next = None
        return element


    def remove_front(self):
        if self.is_empty():
            raise Empty("The deque is empty")

        return self._remove_node(self._head._next)

    def remove_back(self):
        if self.is_empty():
            raise Empty("The deque is empty")

        return self._remove_node(self._tail._prev)
 Visualize 

[Finished in 0.010710202855989337s]

Combining all the LinkedDeque segments

After Combining all the previous segments we get:

class Empty(Exception):
    pass

class LinkedDeque:
    class _Node:
       def __init__(self, e, prev, next):
           self._element = e
           self._prev = prev
           self._next = next
    
    def __init__(self):
        self._head = LinkedDeque._Node(None, None, None) 
        self._tail = LinkedDeque._Node(None, self._head, None) 
        self._head._next = self._tail 

        self._size = 0
 
    def __len__(self):
        return self._size 

    def is_empty(self):
        return len(self) == 0

    def front(self):
        if self.is_empty():
            raise Empty("Deque is empty")
        return self._head._next._element 

    def back(self):
        if self.is_empty():
            raise Empty("Deque is empty")
        return self._tail._prev._element 

    def _insert_between(self, e, node1, node2):
        newnode = LinkedDeque._Node(e, node1, node2)
        node1._next = newnode
        node2._prev = newnode
        self._size += 1

    def insert_front(self, e):
        self._insert_between(e, self._head, self._head._next) 

    def insert_back(self, e):
        self._insert_between(e, self._tail._prev, self._tail)

    def _remove_node(self, node):
        prev = node._prev
        next = node._next
        
        #relink the remaining nodes
        prev._next = next 
        next._prev = prev
        self._size -= 1

        element = node._element

        node._element = node._prev = node._next = None
        return element

    def remove_front(self):
        if self.is_empty():
            raise Empty("The deque is empty")

        return self._remove_node(self._head._next)

    def remove_back(self):
        if self.is_empty():
            raise Empty("The deque is empty")

        return self._remove_node(self._tail._prev)
 Visualize 

Using the class

d = LinkedDeque()
d.insert_front("Python")
d.insert_front("Java")
d.insert_back("C++")
d.insert_back("PHP")
d.insert_front("Javascript")

print("front: ", d.front())
print("back: ", d.back())
print("Removing from back:")

while not d.is_empty():
    print(d.remove_back())
 Visualize 

You can experiment with the class more on your own.