A circular linked list is a linked list, in which the last inserted node links back to the 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 a singly linked list.

linked list diagram

Compared with a circular array, a circular linked list is flexible to expand and shrink, while a circular array has a fixed size. We can also use a circular linked list to implement a circular queue, by changing the insert method to “enqueue”, and the 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 the linked list implementation, we define the 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. The CircularLinkList class has three variables 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 a new node. Its next node links to the head. The length is to keep track of 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. If the list is empty, we point the 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 the 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 point 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 point pre‘s next to p‘s next.

There are two edge cases that need to be considered. 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 to point the head to its next node.

Java

Javascript

Python

Doodle

circular linked list delete


Search by key

To search by key, declare the 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 a value the same as the key. If no node is found when reaches the head node, return null.

Since Python doesn’t support a do-while loop, we use a 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 the p node reference to the head. Then we use a do-while loop to get the value of each element and print it 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).