CREATE OWN LIBRARY
Circular Linked List
Back to ProgrammingDescription
Introduction
Linked list is a linear data structure, which is used to store elements (i.e. data) in a memory. However, the elements are not stored at contiguous memory locations. Linked lists are a collection of nodes, which has two parts - data field which is used to store the data and a link field which points to the next node in the list. In a single linked list, every node in the list points to the next node in the list except for the last node which points to nothing.
Circular linked lists are a variation to the single link lists where the last node also points to the first node. In circular linked lists all the nodes are connected to form a circle. It is a much more complicated data structure as compared to a singly linked list.
Algorithm
Algorithm:
Input:
head which points to the first node in the circular linked list.
Output:
Various operations on a Circular Linked List.
Algo:
Step 1: Start
Step 2: Defining the insertAtBeginning(value,head) function
l + Set newNode[data] <= value.
l Set newNode[next] <= NULL.
l If head = NULL then,
(a) Set head <= newNode.
(b) Set newNode[next] <= head.
l Else then,
(a) Set temp <= head
(b) Repeat the substeps while temp[next] != head
Set temp <= temp[next].
(c)
Set newNode[next] <= head.
(d) Set head <= newNode.
(e) Set temp[next] <= head.
l Display “Insertion Successfull”
Step 3: Defining the insertAtEnd(value,head) function
l Set newNode[data] <= value.
l Set newNode[next] <= NULL.
l If head = NULL then,
(a) Set head <= newNode.
(b) Set newNode[next] <= head.
l Else then,
(a) Set temp <= head
(b) Repeat the substeps while temp[next] != head
Set temp <= temp[next].
(c) Set temp[next] <= newNode.
(d) Set newNode[next] < = head.
l Display “Insertion Successfull”
Step 4: Defining the insertInBetween(pos,value,head) function
l If head = NULL or pos = 1 then,
(a)
Set head <= insertAtBeginning(value,head)
l Else then,
(a)
Set temp1 <= head.
(b)
Set count <= 1.
(c) Repeat substeps while (temp1[next]!=head and count!=pos)
Set temp <= temp1.
Set temp1 <= temp1[next].
Set count <= count + 1 .
(d) If count < pos then
Display “Postion greater than length of the list.”
(e) Else then,
Set newNode[data] <= value.
Set newNode[next] <= temp1.
Set temp2[next] <= newNode.
l Display “Insertion Successfull”
Step 5: Defining the deleteAtBeginning(head) function
l If head = NULL then,
(a) Display “List is empty.”
l Else then,
(a) Set temp <= head.
(b) If temp[next] = head then,
Set head <= NULL.
(c) Else then,
Repeat substeps while temp[next]!=head
Set temp <= temp[next].
Set head <= head[next].
Set temp[next] <= head.
(d) Display “Deletion Successfull.”
Step 6: Defining the deleteAtEnd(head) function
l If head = NULL then,
(a) Display “List is empty.”
l Else then,
(a) Set temp1 <= head.
(b) If head[next] = head then,
Set head <= NULL.
(c) Else then,
Repeat substeps while temp1[next] !=head
Set temp2 <= temp1.
Set temp1 <= temp1[next].
Set temp2[next] <= head.
(d) Display “Deletion Successfull.”
Step 7: Defining the deleteInBetween(pos,head) function
l If head = NULL then,
(a) Display “List is empty.”
(b) Return.
l If pos = 1 then,
(a) Set head <= deleteAtBeginning(head).
(b) Return.
Step 8: Defining the create(head) function
l Display “Enter the number of elements.”
l Repeat i for 0 to N-1.
(a) Enter ith value.
(b) Call insertAtEnd(value,head).
l Display “Circular linked list has been created.”
Step 9: Defining the display(head) function
l Set temp <= head.
l If head = NULL then
(a) Display”List is empty.”
(b) Return.
l Repeat while temp[next] ! = head
(a) Display temp[data].
(b) Set temp <= temp[next]
l Display temp[data].
Step 10: Stop
Code
Application:
Circular linked list has a lot of applications. Some of the most common applications are -
l In round robin scheduling, all the running applications are kept in a circular linked list and the operating system provides each with a fixed time slot for running. The operating system keeps on iterating over the circular linked list untill all the active applications have finished their execution.
l Operating systems use circular linked list to share time for different users, in a multiple user system.
l In multi-player games circular linked lists are used to swap players in a loop.
Advantages:
The circular linked list has many advantages -
l The entire linked list can be traversed from any node.
l Circular linked lists are used in a variety of applications which require looping around a list.
l Circular linked lists are used for implementation of advanced data structures like Fibonacci heap.
Disadvantages:
The circular linked list has many disadvantages -
l Circular linked list is complex as compared to single linked list.
l If not traversed carefully, it could get end up in an infinite loop.
l Like any other linked lists, circular linked lists also do not support direct accessing of elements in the list.
Complexity:
Time Complexity:
Let us assume there are ‘n’ number of elements in a circular linked list. To perform any operation - insertion or deletion, we need to traverse the entire circular linked list, thus the time complexity of any operation on Circular Linked List is O(n).
Space Complexity:
If there are ‘n’ number of elements in a circular linked list, then the space complexity of Circular Linked List is O(n).
