Circular linked list is a linked list, in which the last inserted node links back to the first inserted node. All nodes form a circle. We always insert at one position – we call it “current”, not “head” or “tail” as in linked list. The links can be in one direction as singly linked list, or two way directions as doubly linked list. In this post, we use singly linked list.

Comparing with circular array, circular linked list is flexible to expand and shrink, while circular array has fixed size. We can also use circular linked list to implement circular queue, by changing insert method to “enqueue”, and delete method changes to deleteFirst, aks “dequeue”.

Table of Content


Define classes

The same as linked list implementation, we define Node class first. Node class has two fields: data and next. The data stores the value. The next is the reference to the next node. CircularLinkList class has three variable head, curr and length. The head always points to the first insert node. Its initial value is null. The curr node is the “current” position to insert new node. Its next node links to the head. The length is to keep track the number of elements in the list.

Java

Javascript

Python


Insert

To insert an element, we create a new node first. It the list is empty, we points head and curr to the new node. Otherwise, we link the curr’s next to the new node. Then move curr pointing to the new node. Last link the curr‘s next to the head.

Java

Javascript

Python

Doodle

circular linked list insert


Delete by key

To delete a node by key, first we call search method to see whether the key exists in the list. If it doesn’t exist, the method can return. If it exists, we declare two pointers pre and p to points to the head and the head’s next respectively. Use a while loop to compare each element’s value with the key. When we find the node with the key, we can simply pointing pre‘s next to p‘s next.

There are two edge cases need to consider. When there is only one node left, we reset the head to be null. This means the list is empty after this deletion. Another case is when the head‘s value matches with the key. Then we need point the head to its next node.

Java

Javascript

Python

Doodle

circular linked list delete


Search by key

To search by key, declare p node reference to the head. Then we use a do while loop. First compare the node’s data with the key. If they are equal, the method can return the node. If not equal, move the reference to the next node. Repeat until we find the node with value the same as the key. If no node is found when reach the head node, return null.

Since Python doesn’t support do while loop, we use while loop. At the end of each iteration, we check whether the p node reaches the head.

Java

Javascript

Python


Print

Print is similar to search. First declare p node reference to the head. Then we use a do while loop to get the value of each element and print out.

Java

Javascript

Python

Download Java, JavaScript and Python code
Circular linked list animated visual
Data structures and Java collections