Circular linked list is a linked list, in which the last inserted node links back to head. All nodes form a circle. There is no node pointing to null or None. We define a pointer “curr” to the “last inserted node.” It is the entry point for insertion.

You can make both a singly linked list and a doubly linked list into a circular linked list. In this post, we use singly linked list.

linked list diagram

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


Map of linked list implementations

Part 1 – Linked list implementation
Part 2 – Doubly linked list implementation

you are here

Part 3 – Circular linked list implementation


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 in circular linked list

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


Free download

Download circular linked list implementation in Java, JavaScript and Python
Download combined Data Structures implementations in Python

What is the time complexity of insert-last in a circular linked list?

insert circular linked list

If you keep a head pointer to the first node, and a last pointer to the last inserted node, there is no difference between insert-first and insert-last in a circular linked list. The time complexity of both insert-first and insert-last is O(1).