Page 131 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes

Task Write a program for printing the contents of a circular list.

8.3.3 Circular Linked List Insertion

Inserting a Node at the End of a Circular Linked List

Let us add a node containing data, at the end of a list (circular list) headed by head.

Notes The new node will be placed just after the tail node (which is the last node of the
list), which means it will have to be inserted in between the tail node and the first node.

Example: The example given below shows the steps for inserting a Node at the End of a
Circular Linked List.
Create a new node and initially keep its next pointer points to itself.

Figure 8.27: Create a New Node

Source: http://www.csie.ntu.edu.tw/~hsinmu/courses/lib/exe/fetch.php?media=dsa_12spring:
dsame_chap3.pdf

Update the next pointer of new node with head node and also traverse the list until the tail.
That means in circular list we should stop at a node whose next node is head.

Figure 8.28: Update the Next Pointer

Source: http://www.csie.ntu.edu.tw/~hsinmu/courses/lib/exe/fetch.php?media=dsa_12spring:
dsame_chap3.pdf
Update the next pointer of previous node to point to new node and we get the list as shown
below.

124 LOVELY PROFESSIONAL UNIVERSITY