# Doubly Linked Lists (With Code in C, C++, Java, and Python)

## Introduction

A doubly linked list is a linear data structure where each node has a link to the next node as well as to the previous node. Each component of a doubly linked list has three components.

1. prev: It is a pointer that points to the previous node in the list.
2. data: It holds the actual data.
3. next: It is a pointer that points to the next node in the list.

Since each node has pointers in both the direction, doubly linked list can be traversed in both forward and backward directions. Figure 1 shows an example of a doubly linked list containing 2 items.

The first node is pointed by a pointer called head and the last node is pointed by a pointer called tail. The first node does not have a previous pointer and the last node does not have the next pointer.

## Operations on a doubly linked list

1. Create a new node with the item to be inserted. Initially set both prev and next pointer to null.
2. Set next pointer of the new node to head.
3. Set the prev pointer of head to the new node.
4. Set head pointer to the new node.

### Insert at the tail

1. Create a new node with the item to be inserted. Initially set both prev and next pointer to null.
2. Set next pointer of tail to the new node.
3. Set prev pointer of the new node to tail.
4. Set tail pointer to the new node.

### Insert at the middle

1. Create a new node with the item to be inserted. Initially set both prev and next pointer to null.
2. Seek through the list until you find a node after which you want to insert the new node. Call this node D and node next to it N.
3. Set D’s next pointer to the new node and new node’s prev pointer to D.
4. Set the new node’s next pointer to N and N’s prev pointer to the new node.

### Find the item in the list

2. If curr has the item you are looking for, return the item.
3. Proceeds to the next node. If you started with head use the next pointer to go to the next item otherwise use prev pointer.
4. Repeat step 2 and 3 until you get null pointer. In case you get to the null pointer, you have come to the end and item is not on the list.

### Remove the item at the head

(Note: for all the delete operations, the node needs to be destroyed in order to free the memory. Some languages like Java, Python, etc has a garbage collector that handles this automatically while other languages like C, C++ does not have such a mechanism and programmer has to destroy it explicitly).

1. Find the next node of the head and call it N.
2. Set the prev pointer of N to null.
3. Set both the pointers of the head to null.
4. Destroy the node pointed by head and set the head pointer to N.

### Remove the item at the tail

1. Find the previous node of the tail and call it N.
2. Set the next pointer of N to null.
3. Set both the pointers of the tail to null.
4. Destroy the node pointed by tail and set the tail pointer to N.

### Remove item anywhere in the list

1. Seek through the list until you found the desired node. Call it D.
2. Set D’s previous node’s next pointer to D’s next node and set D’s next node’s prev pointer to D’s previous node.
3. Set both the pointers of D to null.
4. Destroy the node pointed by D.

## Complexities

The table below shows the operation and corresponding complexity of all the operations discussed above.

OperationComplexity