Double Linked List

A double linked list is a linked list in which a node is divided into three parts - previous, data and next. The data part contains the data to be stored, while the previous and next part contain the address of the previous and next node respectively.

A double linked list is different from a single linked list in the following ways:

1.  A node in a single linked list keeps track only of the next node, while a double linked list node not only stores the address of the next node but also of the previous node. The first and the last nodes of the list contains a "NULL" in their previous and next part since there is no node to which they can point.
2. In a single list a pointer called "start" or "head" points to the first node, but in a double linked list apart from "start", there is one more pointer called "end" which points to the last node of the list.
3. A double linked list can be read both ways - from start to end and from end to start.

Advantages
The primary advantage of a doubly linked list is that given a node in the list, one can navigate easily in either direction. This can be very useful, for example, if the list is storing strings, where the strings are lines in a text file (e.g., a text editor). One might store the "current line'' that the user is on with a pointer to the appropriate node; if the user moves the cursor to the next or previous line, a single pointer operation can restore the current line to its proper value. Or, if the user moves back 10 lines, for example, one can perform 10 pointer operations (follow the chain) to get to the right line. For either of these operations, if the list is singly linked, one must start at the head of the list and traverse until the proper point is reached. This can be very inefficient for large lists.

Disadvantages

The disadvantage of doubly linked lists are

1. Each node requires an extra pointer, therefore more memory is required.
2. The insertion or deletion of a node takes a bit longer since there are more pointers to update.

 This is how a double linked list looks like.

Double Linked List

Operations on a double linked list.

Operations that can be performed on a double linked list are similar to those of single linked list. The only additional task that can be performed on a double linked list is that a double linked list can be traveresed both ways.

1. Insertion (At the beginning, end or middle)
2. Deletion
3. Traversal (From start to end)
4. Reverse Traversal (From end to start)
5. Search