Insertion in circular doubly linked list at beginning
There are two scenario of inserting a node in circular doubly linked list at beginning. Either the list is empty or it contains more than one element in the list.
Allocate the memory space for the new node ptr by using the following statement.
In the first case, the condition head == NULL becomes true therefore, the node will be added as the first node in the list. The next and the previous pointer of this newly added node will point to itself only. This can be done by using the following statement.
In the second scenario, the condition head == NULL becomes false. In this case, we need to make a few pointer adjustments at the end of the list. For this purpose, we need to reach the last node of the list through traversing the list. Traversing the list can be done by using the following statements.
At the end of loop, the pointer temp would point to the last node of the list. Since the node which is to be inserted will be the first node of the list therefore, temp must contain the address of the new node ptr into its next part. All the pointer adjustments can be done by using the following statements.
In this way, the new node is inserted into the list at the beginning. The algorithm and its C implementation is given as follows.
- Step 1: IF PTR = NULL
- Step 2: SET NEW_NODE = PTR
- Step 3: SET PTR = PTR -> NEXT
- Step 4: SET NEW_NODE -> DATA = VAL
- Step 5: SET TEMP = HEAD
- Step 6: Repeat Step 7 while TEMP -> NEXT != HEAD
- Step 7: SET TEMP = TEMP -> NEXT
- Step 8: SET TEMP -> NEXT = NEW_NODE
- Step 9: SET NEW_NODE -> PREV = TEMP
- Step 1 : SET NEW_NODE -> NEXT = HEAD
- Step 11: SET HEAD -> PREV = NEW_NODE
- Step 12: SET HEAD = NEW_NODE
- Step 13: EXIT
Go to Step 13
[END OF IF]
[END OF LOOP]
Enter the item which you want to insert? 12 Node Inserted Press 0 to insert more ? 0 Enter the item which you want to insert? 23 Node Inserted Press 0 to insert more ? 1