Page 108 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 7: Linked Lists

Notes

Task Compare and contrast doubly linked lists and multilinked lists.

7.2.4 Circular Linked List

Another important type of a linked list is called a circular linked list where last node of the list
points back to the first node (or the head) of the list. Circular linked list is a more complicated
linked data structure. In singly linked lists and doubly linked lists the end of lists are indicated
with NULL value. But circular linked lists do not have ends.

!

Caution While traversing the circular linked lists we should be careful otherwise we will
be traversing the list infinitely.
In circular linked lists each node has a successor. Note that unlike singly linked lists, there is no
node with NULL pointer in a circularly linked list. In some situations, circular linked lists are
useful.

Example: when several processes are using the same computer resource (CPU) for the
same amount of time, and we have to assure that no process accesses the resource before all
other processes did (round robin algorithm).
The elements can be placed anywhere in the heap memory unlike array which uses contiguous
locations. Nodes in a linked list are linked together using a next field, which stores the address
of the next node in the next field of the previous node, i.e. each node of the list refers to its
successor and the last node points back to the first node unlike singly linked list. It has a dynamic
size, which can be determined only at run time.

Figure 7.9: Circular Lists

The advantage is that we no longer need both a head and tail variable to keep track of the list.
Even if only a single variable is used, both the first and the last list elements can be found in
constant time.

Notes For implementing queues we will only need one pointer namely tail, to locate both
head and tail.

The disadvantage is that the algorithms have become more complicated.
Following is a type declaration for a circular linked list of integers:
Typedef struct CLLNode {
int data;
struct ListNode *next;
}

LOVELY PROFESSIONAL UNIVERSITY 101