Table of Contents

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**