## 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.

`prev`

: It is a pointer that points to the previous node in the list.`data`

: It holds the actual data.`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

### Insert at the head

- Create a new node with the item to be inserted. Initially set both
`prev`

and`next`

pointer to`null`

. - Set
`next`

pointer of the new node to`head`

. - Set the
`prev`

pointer of`head`

to the new node. - Set
`head`

pointer to the new node.

### Insert at the tail

- Create a new node with the item to be inserted. Initially set both
`prev`

and`next`

pointer to`null`

. - Set
`next`

pointer of`tail`

to the new node. - Set
`prev`

pointer of the new node to`tail`

. - Set
`tail`

pointer to the new node.

### Insert at the middle

- Create a new node with the item to be inserted. Initially set both
`prev`

and`next`

pointer to`null`

. - 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.
- Set D’s
`next`

pointer to the new node and new node’s`prev`

pointer to D. - Set the new node’s
`next`

pointer to N and N’s`prev`

pointer to the new node.

### Find the item in the list

- Start with
`head`

or`tail`

. Call it`curr`

. - If
`curr`

has the item you are looking for, return the item. - Proceeds to the next node. If you started with
`head`

use the`next`

pointer to go to the next item otherwise use`prev`

pointer. - 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)*.

- Find the next node of the
`head`

and call it N. - Set the
`prev`

pointer of N to`null`

. - Set both the pointers of the head to
`null`

. - Destroy the node pointed by
`head`

and set the`head`

pointer to N.

### Remove the item at the tail

- Find the previous node of the
`tail`

and call it N. - Set the
`next`

pointer of N to`null`

. - Set both the pointers of the tail to
`null`

. - Destroy the node pointed by
`tail`

and set the`tail`

pointer to N.

### Remove item anywhere in the list

- Seek through the list until you found the desired node. Call it D.
- 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. - Set both the pointers of D to
`null`

. - Destroy the node pointed by D.

## Complexities

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

Operation | Complexity |
---|---|

Insert at the head | O(1) |

Insert at the tail | O(1) |

Insert at the middle | O(n) |

Delete at the head | O(1) |

Delete at the tail | O(1) |

Delete at the middle | O(n) |

Search the list | O(n) |

## Implementation in C, C++, Java, and Python

1 | // C implementation of doubly linked list |

1 | // C++ implementation of doubly linked list |

1 | // Java implementation of Doubly linked list |

1 | # Python implementation of Doubly linked list |