Circular Linked List
Welcome!! In this article, we will learn about Circular Linked List
Circular Linked List is a type of Linked List where all the nodes are connected to form a circle. There is no NULL at the end as the last node is connected to the first node of the Linked List. Both Singly Linked List and Doubly Linked List can be made into a Circular Linked List.
Read this to know more about Singly Linked List and Doubly Linked List
Singly Linked List as Circular
Doubly Linked List as Circular
Key takeaways
- The last node’s next pointer points to the first node of the list in both singly as well as doubly Linked List.
- The previous of first node points to the last node of the list lin case of doubly Linked List.
Advantages of Circular Linked List
- Any node can be a starting point. We can traverse the whole list by starting from any point. We just need to stop when the first visited node is visited again.
- Useful for implementation of queue. We don’t need to maintain two pointers for front and rear if we use circular linked list. We can maintain a pointer to the last inserted node and front can always be obtained as next of last.
- Circular lists are useful in applications to repeatedly go around the list. For example, when multiple applications are running on a PC, it is common for the operating system to put the running applications on a list and then to cycle through them, giving each of them a slice of time to execute, and then making them wait while the CPU is given to another application. It is convenient for the operating system to use a circular list so that when it reaches the end of the list it can cycle around to the front of the list.
Basic Operations
- Traverse — Traverse through whole list and display it.
- Insert — Inserts an element.
- Delete — Delete an element.
Traverse Operation
In a conventional linked list, we traverse the list from the head node and stop the traversal when we reach NULL. In a circular linked list, we stop traversal when we reach the first node again. Following is the Java code for the linked list traversal.
class LinkedList{ // node static class Node
{
int data;
Node next;
}; / * Function to insert a node at the beginning of a Circular linked list */ static Node push(Node head_ref, int data)
{ Node ptr1 = new Node(); Node temp = head_ref; ptr1.data = data; ptr1.next = head_ref; /* If linked list is not null then set the next of last node */ if (head_ref != null)
{
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
} else
ptr1.next = ptr1;
head_ref = ptr1;
return head_ref; } /* Function to print nodes in a given Circular linked list */ static void printList(Node head)
{ Node temp = head; if (head != null)
{
do
{
System.out.print(temp.data + " ");
temp = temp.next;
}
while (temp != head); } }// Driver Codepublic static void main(String args[]){ /* Initialize lists as empty */ Node head = null; /* Created linked list will be 11.2.56.12 */ head = push(head, 12); head = push(head, 56); head = push(head, 2); head = push(head, 11); System.out.println("Contents of Circular " + "Linked List:"); printList(head);}}
Conclusion
In this blog, we have seen about Circular Linked List and how a circular linked list is made in both Singly and Doubly Linked List. We have also seen the advantages of circular LinkedList and a sample Java program to traverse through the lst and display the data.
