Insertion in circular doubly linked list at end

There are two scenario of inserting a node in circular doubly linked list at the end. 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 become false, therefore node will be added as the last node in the list. For this purpose, we need to make a few pointer adjustments in the list at the end. Since, the new node will contain the address of the first node of the list therefore we need to make the next pointer of the last node point to the head node of the list. Similarly, the previous pointer of the head node will also point to the new last node of the list.

Now, we also need to make the next pointer of the existing last node of the list (temp) point to the new last node of the list, similarly, the new last node will also contain the previous pointer to the temp. this will be done by using the following statements.

In this way, the new node ptr has been inserted as the last node of the list. The algorithm and its C implementation has been described as follows.

Algorithm

• Step 1: IF PTR = NULL

Write OVERFLOW
Go to Step 12
[END OF IF]

• Step 2: SET NEW_NODE = PTR
• Step 3: SET PTR = PTR -> NEXT
• Step 4: SET NEW_NODE -> DATA = VAL
• Step 5: SET NEW_NODE -> NEXT = HEAD
• Step 6: SET TEMP = HEAD
• Step 7: Repeat Step 8 while TEMP -> NEXT != HEAD
• Step 8: SET TEMP = TEMP -> NEXT

[END OF LOOP]

• Step 9: SET TEMP -> NEXT = NEW_NODE
• Step 10: SET NEW_NODE -> PREV = TEMP
• Step 11: SET HEAD -> PREV = NEW_NODE
• Step 12: EXIT

C Function

Output

Enter the item which you want to insert?  123    Node Inserted    Press 0 to insert more ?  12