A Doubly Linked List is a collection of zero or many nodes where each node is composed of three parts. These parts are Data part, Next Pointer and Prev (Previous) Pointer.
As we can see in the above figure, this exemplary list consists of three nodes. The start variable points to the Node A. The prev pointer part of the Node A is null. It means that Node A is the first node of the doubly linked list. The next pointer part of the Node A contains the reference of Node B. Similarly, the Node B points backward to Node A and points forward to Node C. The prev pointer of the Node C points to the Node B, however the next pointer of the Node C is null, indicating that it is the last node of the list.
Insertion in Doubly Linked List
An insertion in a doubly linked list can be performed easily, just by changing the appropriate pointers. To understand how to insert a node in the list, let us consider the following figure: –
While inserting a new node in the list, we need the location before which the new node is to be inserted. Suppose that new node to be inserted is with value D and it is to be inserted before node B. For this first we need the location of the preceding node of Node B, that is Node A. After finding the location of the preceding node (Node A), we change the pointers as follows: –
- The next pointer of Node A is pointed to the new node.
- The prev pointer of the new node is pointed to Node A.
- The next pointer of the new node is pointed to the Node B.
- The prev pointer of Node B is pointed to the new node.
Similarly, we can insert a new node in the list anywhere between its elements. It can be inserted as the first node and also as the last node. When we need to insert the new node as the first node of the list, we point start to the new node. Changes prev pointer of the new node to null and next pointer of the new node to the previous first node of the list.