Page 130 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 8: Operations on Linked List

8.3 Basic Operations on Circular Linked Lists Notes

The operations on Circular linked lists include counting, printing, inserting, deleting.

8.3.1 Counting Nodes in a Circular List

The circular list is accessible through the node marked head. To count the nodes, the list has to
be traversed from node marked head, with the help of a dummy node current and stop the
counting when current reaches the starting node head. If the list is empty, head will be NULL,
and in that case set count = O. Otherwise, set the current pointer to the first node, and keep on
counting till the current pointer reaches the starting node.

Figure 8.26: Counting Nodes

Source: http://www.csie.ntu.edu.tw/~hsinmu/courses/lib/exe/fetch.php?media=dsa_12spring:
dsame_chap3.pdf
int CircularListLength(struct CLLNode *head) {
struct CLLNode *current = head;
int count = 0;
if(head== NULL) return 0;
do { current = current—> next;
count++;
} while (current != head);
return count;
}

8.3.2 Printing the Contents of a Circular List

We assume here that the list is being accessed by its head node. Since all the nodes are arranged
in a circular fashion, the tail node of the list will be the node next to the head node. Let us assume
we want to print the contents of the nodes starting with the head node. Print its contents, move
to the next node and continue printing till we reach the head node again.
void PrintCircularListData(struct CLLNode *head) {
struct CLLNode *current = head;
if(head == NULL) return;
do { printf (“%d”, current—> data);
current = current—>next;
}
while (current != head);
}

LOVELY PROFESSIONAL UNIVERSITY 123