Insert in doubly linked list
In last few posts : Linked List Problems., we learned about singly linked list. Singly linked list has only one pointer per node which points to next node. There is only one way in which list can be traverse, that is forward. We cannot traverse it backward. In this post, we will discuss insert in doubly linked list.
Doubly linked list solves problem the problem to traversing both ways, it can be traversed backwards and forwards. Doubly linked list nodes contain two pointers each, one points to next node and other points to previous node of current node. To move forward, use next pointer and to move backward, use previous pointer.
Insertion in Doubly linked list
There are four place a new node can be inserted into DLL.
1. Head of list
2. Tail of list
3. Before a given node
4. After a given node
1. Insert in doubly linked list : At front
To insert a node at head, make sure that head pointer is change after insertion. Also in DLL, previous pointer of last head node points to new node, next of new node points to last head node and previous of new node points to NULL. Below these steps are clarified:
1. Create a new node 2. Make next of new node to point to old head 3. Make previous of old head to point to new node 4. Change headRef to point to new node 5. Make previous of new node as NULL
Below figure explains the insert operation at head
Code to insert at node at front of DLL
2. Insert in doubly linked list : At end
To insert at end, we obviously need to traverse to end of list. There is special case that needs to be handle, that is if this is first node of doubly linked list. Extra thing to do is point previous of first node to NULL.
1. Create new node with data 2. Check if this is first node, make previous to point to NULL, change headRef 3. Else traverse till last node of list. 4. Make next of last node point to new node. 5. Make previous of new node point to last node. 6. Make next of new node point to NULL
3. Insert in doubly linked list : After a given node
This is very similar case to insert at the end. Only thing not to be done is to check if this is first node.Rest all remains same.
1. Create new node with data 2. Save next of givenNode (nextNode) 3. Make next of givenNode point to new node. 4. Make previous of nextNode to point new node 5. Make previous of new node point to givenNode. 6. Make next of new node point to nextNode
4. Insert in doubly linked list : Before a given node
Again similar case to 3, only next and previous pointers to point to correct nodes.
1. Create new node with data 2. Save previous of givenNode (prevNode) 3. Make next of new Node point to givenNode 4. Make previous of givenNode point to new node. 4. Make next of prevNode point to new node. 6. Make previous of new node to point to prevNode
Below figure explains insert operation before a given node
Complexity of insertion is at start, before or after a given node is O(1) where for insertion at end is O(n).
Please share if there is something wrong or missing. If you are interested in contributing to website or share interview experience, please contact us.