# Doubly Linked List: C++, Python (Code Example)

## What is a doubly linked list?

In a doubly linked list, each node has links to both the previous and next node. Each node consists of three elements: one holds the data, and another two are the next and the previous node’s pointers. These two pointers help us to go forward or backward from a particular node.

Here’s the basic structure of the doubly linked list.

Every linked list has a head and tail node. The Head node has no “prev” (previous pointer) node, and the tail node has no “next” node.

Here’re some important terms for a doubly linked list:

• Prev: Each node is linked to its previous node. It is used as a pointer or link.
• Next: Each node is linked to its next node. It is used as a pointer or link.
• Data: This is used to store data in a node. “Data” can hold other Data Structures inside it. For example, string, dictionary, set, hashmap, etc can be stored in the “Data”.

Here is the basic structure of a single node in the doubly linked list:

## Operations of Doubly Linked List

The operations of a doubly linked list include adding and deleting nodes, inserting and removing nodes, and traversing the linked list from the top to the bottom.

Here’s the list of operations we can implement using the doubly linked list:

• Insertion in front
• Insertion in the tail or last node
• Insertion after a node
• Insertion before a node
• Deletion from front
• Deletion from tail
• Search and delete a node

We’ll see the implementation and pseudocode for all the operations above.

## Insertion in front of Doubly Linked List

Insertion in front means we need to create a node in the linked list and place it at the beginning of the linked list.

For example, there’s a given node “15”. We need to add this to the head node.

Here’re two important conditions while doing this operation:

1. The new node will be the head node if there’s no node in the Doubly Linked List.
2. If there’s already a head node, the previous head will be replaced by the new node.

Here’s the pseudo-code for this operation:

```function insertAtFront (ListHead, value):
newNode = Node()
newNode.value = value
newNode.prev = NULL
```

## Insertion at the end of Doubly Linked List

“Insertion at the end” means we will create a node in the linked list and place it at the end.

To perform this, we can use two methods:

• Method 1: Start traversing from the head of the Doubly Linked List until the “next” becomes null. Then link the new node with the “next”.
• Method 2: Take the last node of the Doubly Linked List. Then, the “next” node of the last node will link to the new node. Now, the new node will be the tail node.

Here’s the pseudo-code for insertion at the tail node:

```function insertAtTail(ListHead, value):
newNode = Node()
newNode.value = value
newNode.next = NULL
```

## Insertion after a node

Let’s say we have an existing doubly linked list like the following:

We want to insert a given node that will be linked after the node, which has the value of “12”.

Here’re the steps for this:

Step 1) Traverse from the head to the last node. Check which node has the value of “12”.

Step 2) Create a new node and assign it as the next pointer of node “12”. The “next” node of the new node will be 15.

Here’s the pseudo-code for inserting a node after a node in doubly linked list:

```function insertAfter(ListHead, searchItem, value):
NewNode = Node()
NewNode.value = value
while List.value is not equal searchItem
List = List.next
NewNode.next = List.next
NewNode.prev = List
List.next = NewNode
```

## Insertion before a node

This operation is more similar to the “insertion after a node”. We need to search for a specific node’s value to perform this. Then we will create a new node and insert it before the searched node.

Let’s say we want to insert a given node “15” before the node “12”. Then here’re the steps for doing it:

Step 1) Traverse the linked list from the head node to the tail node.

Step 2) Check whether the next pointer of the current node has the value of “12” or not.

Step 3) Insert the new node as the “next” node of the current node.

Here’s the pseudo-code for inserting a node before a node in doubly Linked List:

```function insertBefore(ListHead, searchItem, value):
NewNode = Node()
NewNode.value = value
while List.next.value is not equal searchItem
NewNode.next = List.next
NewNode.prev = List
List.next = NewNode
```

The head node in the doubly linked list that doesn’t have any previous node. So, the next pointer will be the new head node if we want to delete the head node. We also need to free the memory occupied by a node while deleting a node.

Here’re the steps for deleting the head node:

Step 1) Assign a variable to the current head node.

Step 2) Visit the “next” node of the current head node and make the “prev” (previous pointer) node as ‘’NULL”. This means we are disconnecting the second node from the first node.

Step 3) Free the occupied memory by the previous head node.

Here’s the pseudo-code for deleting the head from a doubly linked list:

```function deleteHead(ListHead):
```

It is necessary to delete the allocated memory after performing any kind of deletion operation. Otherwise, during the entire runtime of the program, the memory for the deleted block will remain occupied. No other application can use that memory segment.

## Delete the tail of the doubly linked list.

This operation is kind of the same as the deletion of the head. Here, instead of the head, we need to delete the tail. To identify a node as a tail node, we should check if the next pointer or next node is null or not. After deleting the tail, we need to free the memory.

This operation is also known as the “deletion from the back”.

Here’re the steps to do this:

Step 1) Traverse until the tail node of the doubly linked list.

Step 2) Assign a variable or pointer to the tail node.

Step 3) Make the “next” node as NULL and free the memory of the tail node.

Here’s the pseudo-code for deleting the tail node:

```function DeleteTail( ListHead ):
free memory( Tail )
```

## Search and delete a node from Doubly Linked List

This operation allows us to search for a specific node data and delete that node. We need to perform a linear search as the linked list is a linear data structure. After deleting, we also need to free the memory.

Here’re the steps for searching and deleting a node in the doubly linked list:

Step 1) Traverse the linked list from the head until the node’s value equals the search item.

Step 2) Assign a variable “deleteNode” to the matched node.

Step 3) Assign the previous node of the “deleteNode” to the next node.

Step 4) Free the memory of the “deleteNode”

Here’s the pseudocode for searching and deleting a node from a linked list:

```function SearchAndDelete(ListHead, searchItem):
deleteNode.next, deleteNode.next = NULL
free memory(deleteNode)
```

## Traverse a doubly linked list from forward

To traverse from the head node and iterate over the next node until we find “NULL”. While traversing each node, we can print the value of the node. Here are the steps for traversing from the front (forward direction):

Step 1) Assign a pointer or variable to the current head node.

Step 2) Iterate to the next node of the head until getting “NULL”

Step 3) Print the node’s data in each iteration.

Step 4) Return the head node.

Here’s the pseudo-code for traversing a Doubly Linked List from the front:

```function traverseFromFront(ListHead):
while head not equals to NULL:
```

Here, the return is not mandatory. But it’s a good practice to return the head node after the operations.

## Traverse a doubly linked list from the backward

This operation is the inverse of the traverse from the front. The approach is the same with a little difference. We must traverse to the end node and then traverse from the end node to the front node.

Here’re the steps for traversing a doubly linked list from the back:

Step 1) Traverse until we reach the tail node.

Step 2) From the tail node, we will traverse until we get the previous node as “NULL”. The “prev” (previous pointer) will be null for the head node

Step 3) At each iteration, we will print the node data.

Here’s the pseudo-code for traversing from back:

```function traverseFromBack(ListHead):
while tail not equal to NULL:
print tail.value
tail = tail.prev
```

## Difference between Singly and Doubly linked list

The main difference between Singly and the Doubly Linked list is the number of links.

Here’s the difference between the nodes of a Singly Linked list and the Doubly Linked List’s node structure:

Structure Singly Linked List has one data field and one link to the next node. Doubly Linked List has one data field and two links. One for the previous node and another for the next node.
Traversal It can only traverse from head to tail. It can traverse both forward and backward.
Memory Occupies less memory. It occupies more memory than a singly linked list.
Accessibility Singly Linked Lists are less efficient as they use only one link to the next node. There’s no link for the previous node. Doubly Linked Lists are more efficient than the Singly Linked Lists.

## Doubly Linked List in C++

```#include<iostream>
using namespace std;
struct node{
int data;
struct node *next;
struct node *prev;
};
node* newNode = new node();
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
{
}

}
void insertEnd(node * &listHead, int value){
{
}
node* newNode = new node();
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
}
}
void insertAfter(node * &listHead, int searchValue,int value){
node* newNode = new node();
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
}
if(newNode->next !=NULL){
newNode->next->prev = newNode;
}
cout<<"Inserted "<<value<<" after node "<<searchValue<<endl;
}
void insertBefore(node * &listHead, int searchValue,int value){
node* newNode = new node();
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
}
if(newNode->next !=NULL){
newNode->next->prev = newNode;
}
cout<<"Inserted "<<value<<" before node "<<searchValue<<endl;
}
}
cout<<endl;
}
}
while(tail!=NULL){
cout<<tail->data<<"\t";
tail = tail->prev;
}
cout<<endl;
}
}
}
}

}
cout<<"Deleted Node\t"<<searchItem<<endl;
return;
}
int main(){
}
```

### Output

```Added 5 at the front
Inserted 11 after node 5
Inserted 20 before node 5
Traversal from head:    7        6       20      5       11      9       10
Traversal from head:    10      9       11      5       20      6       7
Deleted Node    7
Traversal from head:    6        20      5       11      9       10
Traversal from head:    10      9       11      5       20      6
```

## Doubly Linked List in Python

```class node:
def __init__(self,data = None, prev=None, next = None):
self.data = data
self.next = next
self.prev = prev
def __init__(self):

def insertFront(self, val):
newNode = node(data=val)

def insertEnd(self,val):
newNode = node(data=val)
self.insertFront(val)

while temp.next is not None:
temp = temp.next
temp.next = newNode
newNode.prev = temp

def traverseFromFront(self):
while temp:
print("{}\t".format(temp.data),end="")
temp = temp.next
print()

def traverseFromEnd(self):
print("Traversing from Tail:\t",end="")
while temp.next is not None:
temp = temp.next
tail = temp
while tail is not None:
print("{}\t".format(tail.data),end="")
tail = tail.prev
print()

def insertAfter(self,searchItem, value):
newNode = node(data=value)

while temp.next is not None and temp.data is not searchItem:
temp = temp.next

newNode.next = temp.next
temp.next = newNode
newNode.prev = temp

if newNode.next is not None:
newNode.next.prev = newNode
print("Inserted {} after node {}".format(value,searchItem))

def insertBefore(self,searchItem, value):
newNode = node(data=value)

while temp.next is not None and temp.next.data is not searchItem:
temp = temp.next

newNode.next = temp.next
temp.next = newNode
newNode.prev = temp

if newNode.next is not None:
newNode.next.prev = newNode
print("Inserted {} before node {}".format(value,searchItem))

def searchAndDelete(self,searchItem):

while temp.next is not None and temp.data is not searchItem:
temp = temp.next

if self.head is None or temp is None:
return

if temp.next is not None:
temp.next.prev = temp.prev

if temp.prev is not None:
temp.prev.next = temp.next

print("Deleted Node\t{}".format(searchItem))
return

```

### Output

```Added 5 at the front
Inserted 11 after node 5
Inserted 20 before node 5
Traversing from head:   7       6       20      5       11      9       10
Traversing from Tail:   10      9       11      5       20      6       7
Deleted Node    7
Traversing from head:   6       20      5       11      9       10
Traversing from Tail:   10      9       11      5       20      6
```

## Complexity of Doubly Linked List

Generally, time complexity is divided in three types.

They are:

1. Best Case
2. Average Case
3. Worst Case

Time complexity in the best case for Doubly Linked List:

1. Insertion in head or tail will cost O(1). Because we don’t need to traverse inside the linked list. The head and the tail pointer can give us access to the head and tail node with O(1) time complexity.
2. Deletion at the head or tail will cost O(1).
3. Searching a node will have the time complexity of O(1). Because the target node can be the head node.

Time complexity in the average case for Doubly Linked List:

1. Insertion at the head or tail will have the time complexity of cost O(1).
2. Deletion at the head or tail will have the time complexity of cost O(1).
3. Searching a node will have the time complexity of O(n). Because the search item can reside anywhere between the linked list. Here, “n” is the total node present in the linked list.

The worst-case time complexity of the doubly linked list will be the same as the average case.

Memory complexity of Doubly Linked List

Memory complexity is O(n), where “n” is the total number of nodes. While implementing the linked list we must free the memory that we used. Otherwise, for a larger linked list, it will cause memory leakages.

## Summary

• A linked list is a kind of linear data structure, a collection of data represented in a linear manner.
• A doubly linked list is a type of linked list where a node has links with both the previous and next node.
• Doubly linked list contains all the operations like adding a node, deleting a node, inserting a node after or before another node, and traversing the linked list from head to tail.
• Doubly Linked List has one data field and two links. One for the previous node and another for the next node.
• Complexity of Doubly Linked List Best Case, Average Case
• And Worst Case.