A double linked list is a two-way list in which all nodes will have two links. This helps in accessing both successor node and predecessor node from the given node position. It provides bi-directional traversing. Each node contains three fields:
- Left link.
- Data.
- Right link.
The left link points to the predecessor node and the right link points to the successor node. The data field stores the required data.
Many applications require searching forward and backward thru nodes of a list. For example searching for a name in a telephone directory would need forward and backward scanning thru a region of the whole list.
The basic operations in a double linked list are:
- Creation.
- Insertion.
- Deletion.
- Traversing.
The beginning of the double linked list is stored in a “start” pointer which points to the first node. The first node’s left link and last node’s right link is set to NULL.
The following code gives the structure definition:
