FOR FREE CONTENT
Single linked list to circular linked list conversion
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.
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 insert(head) function
l Set newNode[data] <= value.
l Set newNode[next] <= NULL.
l If head = NULL then,
(a) Set head <= newNode.
l Else then,
(a) Set temp <= head
(b) Repeat the substeps while temp[next] != NULL
Set temp < temp[next].
(c) Set temp[next] <= newNode.
(d)
Step 3: 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)
head insert(value,head).
l Display “Linked List has been created.”
l
Step 4: Defining the circular(head) function
l
Set start <= head.
l Repeat substeps while head[next] !=NULL
(a) Set head <= head[next]
l
Set head[next] <= start.
l
Step 5: Defining the display 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].
l
Step 6: 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 single linked list. To convert it into a circular linked list with ‘n’ nodes, every node has to be traversed and then the last node is made to point to the head.
Space Complexity:
If there are ‘n’ number of elements in a single linked list, then the space complexity of converting it into a circular linked list is O(n).
