# Doubly Linked List | Representation and Basic Operations

Unlike a Singly Linked List, in a Doubly Linked List, there is an extra pointer, the `previous` pointer along with the `next` pointer as shown below. The previous pointer points to the previous node in the list and the next pointer points to the next node in the list. So, in a doubly linked list, a node contains a reference both to its previous node and to its next node.

## Representation

`/* Structure for node in doubly LL */`struct` n`ode { ``    ``int` `data; ``    ``struct` n`ode* next; ``// Pointer to next node ``    ``struct` n`ode* prev; ``// Pointer to previous node`};`

## Basic operations

The following are the basic operations supported by this Linked List.

• Insertion − Inserts an element at a specified position in the list.
• Deletion − Deletes an element at a specified position in the list.
• Search − Searches an element using the given value.
• Update − Updates/modifies an element in the list with the given value.
• Reverse − Reverses the entire Linked list.
• Traverse  −  Displays all the elements in the linked list.

• Traversal can be done in both directions (from the start node to the end node as well as from the end node to the start node) in a Doubly Linked list. But this is not possible in a Singly Linked List and it can only be traversed only in one direction.
• Deletion and insertion operations are easy to implement in a Doubly LL than a Singly LL. For example, in a singly linked list, to delete a node, the pointer to the previous node is needed for which the list is to be traversed. In a Doubly LL, we just need to know the pointer of the node to be deleted.
• Memory has to be allocated for both the next and previous pointers in a node. Hence, the occupation of memory is higher in Doubly LL.
• Both the pointers will have to be modified if any kind of operation is performed like insertion, deletion, etc in case of Doubly LL.

## Applications

• The browser cache which allows you to hit the BACK buttons or navigate through previous pages.
• Applications that have a Most Recently Used (MRU) lists.
• A stack, hash table, and binary tree can be implemented using a doubly linked list.
• Undo features in publishing or editing applications like Photoshop and Word.
• A great way to represent a deck of cards in a game where removing items from anywhere in the deck is essential.

### Relevant exercises

POST A NEW COMMENT

• Input (stdin)

Output (stdout)

Input (stdin)

Expected Output

Compiler Message

Input (stdin)

`2    3`

`5`
`5`
`5`