In this article, we will see how to implement a doubly linked list. A linked list is a data structure that contains a sequence of nodes. A node usually contains value(s) and pointer(s) to node(s). If a node in the linked list contains a pointer to the next node only, then it is a singly linked list. If it contains two pointers, i.e., reference to the next node and the previous one, then that linked list is called a doubly linked list. We only need to access the first node to traverse the complete linked list since each node contains a reference to the next node. The first node is usually known as the head. Moreover, the head’s previous pointer is NULL as there is no node before it, and the last node points to NULL since there are no more nodes after it.

Implementation of a Doubly Linked List

Now that we know what a doubly-linked list is, let’s see how we can implement its basic functionalities.

Insert

It takes a value and adds it at the end of the list. Initially, when the list is empty, the head pointer points to NULL. Therefore, we create a node with the given value and make the head pointer to refer to it. Its next and previous will both be NULL since it is the only node.

If the list already contains nodes, then we need to reach the last node. We do that using the while loop. We create a temp variable that is initially equal to the head, and at each iteration, we advance it to refer to its next node. We continue doing so until temp.next is equal to NULL, i.e., we get the last node. Once we get it, we create a new node with the given value and the prev pointer equal to temp. Then, we assign that node to temp.next.

Delete

It takes a value and removes its first occurrence from the list. If the value does not exist, it throws an error. Similar to insertion, we create a temp pointer that is initially equal to the head. A while loop runs till temp becomes NULL. At each iteration, we compare the current node’s value with the given one. If they are not equal, we advance the temp pointer to refer to its next node. Otherwise, the node to be deleted is found. Now, we need to adjust the values of temp.prev.next and temp.next.prev. If our target node is not the first node, then we set temp.prev.next to temp.next. If it is the first node, then we need to make the head pointer to point to head.next or temp.next. Then, we need to set temp.next.prev to temp.prev if the node is not the last one. Finally, we delete the temp node to free up space and return.

Search

The input is the value to be found, and the output is its index. If it does not exist, an error gets thrown. To keep track of the index, we create a variable i = 0. Then, similar to deletion, we iterate over the list using the temp variable. At each iteration, we compare the current node’s value with the given one. If they are not equal, we advance the temp pointer to refer to its next node and increment i. Otherwise, the node to be deleted is found, and we return i.

Traverse

This method iterates over the whole list and prints values. To do that, we create a temp node that is initially equal to the head node. Then, we iterate over the list using a while loop and print each node’s value. At each iteration, we set temp to point to its next node to move forward. The loop runs till temp is equal to NULL, i.e., when we have gone through all list elements.

Code to Implement a Doubly Linked List

The code is given below.

#node for the doubly linked list
class Node:
  def __init__(self, value=None, next=None, prev=None):
    self.value = value
    self.next = next  #reference to the next node
    self.prev =  prev #reference to the previous node

#implementation of doubly linked list
class DoublyLinkedList:
  def __init__(self):
    self.head = None
  
  #add a node at the end of the list
  def insert(self, value):
    
    if self.head == None: #if list is empty insert a node at the start
      self.head = Node(value)
    else:
      temp = self.head
      #iterate through the list till last node is found
      while temp.next: 
          temp = temp.next
      temp.next = Node(value, prev=temp) #adding a new node
  
  #find the position of the given value in the list
  def search(self, value):
    temp = self.head
    #iterate through the list
    i = 0
    while temp:
      if temp.value == value:
        return i
      temp = temp.next
      i += 1
    
    raise KeyError(f'Item with the value {value} does not exist')
  
  #remove the node with the given value from the list or throw an error
  def delete(self, value):
    if self.head: #if the list is not empty
      temp = self.head
      #iterate through the list
      while temp:
          if temp.value == value: #node found
            if temp.prev:
              temp.prev.next = temp.next
            else:  #node to be deleted is the first node
              self.head = temp.next
            if temp.next:
              temp.next.prev = temp.prev
            del temp
            return 
          else:
            temp = temp.next
    
    raise KeyError(f'Item with the value {value} does not exist')

  #traverse the complete list and print node values
  def traverse(self):
    temp = self.head
    while temp:
      print(temp.value, end="\t")
      temp = temp.next
    print("")


ll = DoublyLinkedList() #create list_1

#insert values
ll.insert(1)
ll.insert(8)
ll.insert(6)
ll.insert(2)

print("Linked list:")
ll.traverse()

#search operation
print("The value 2 is found at position", ll.search(2))
print("The value 1 is found at position", ll.search(1))

#delete operation
ll.delete(2)
ll.delete(8)
print("Linked list:")
ll.traverse()

Output

Linked list:
1	8	6	2	
The value 2 is found at position 3
The value 1 is found at position 0
Linked list:
1	6

ll = DoublyLinkedList() #create list_1

#insert values
ll.insert(1)
ll.insert(8)
ll.insert(6)

print("Linked list:")
ll.traverse()

#search operation
print("The value 2 is found at position", ll.search(2))

Output