# Implement a Doubly Linked List

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

def __init__(self):

#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
else:
#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):
#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
#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
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):
while temp:
print(temp.value, end="\t")
temp = temp.next
print("")

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

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)
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
1	6
```
```ll = DoublyLinkedList() #create list_1

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