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.
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
- Define classes
- Insert
- Delete by key
- Search by key
- Free download
Map of linked list implementations
Part 1 – Linked list implementation
Part 2 – Doubly linked list implementation
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
public class CircularLinkList<T> { static class LinkNode<T> { T data; LinkNode<T> next = null; //Constructor, Time O(1), Space O(1) public LinkNode(T value) { this.data = value; } //Override, Time O(1), Space O(1) public String toString() { return String.valueOf(data); } } private LinkNode<T> head = null; private LinkNode<T> curr = null; //current insert position, also tail private int length = 0; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class LinkNode { //Constructor, Time O(1), Space O(1) constructor(value) { this.data = value; this.next = null; } //convert to printable, Time O(1), Space O(1) toString() { return this.data; } } class CircularLinkList{ //Constructor, Time O(1), Space O(1) constructor () { this.head = null; this.curr = null; //current insert position, also tail this.length = 0; } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class LinkNode : #Constructor, Time O(1), Space O(1) def __init__(self, value) : self.data = value self.next = None # Time O(1), Space O(1) def __str__(self): return str(self.data) class CircularLinkList : #Constructor, Time O(1), Space O(1) def __init__ (self) : self.head = None self.curr = None #the last inserted node, also tail self.length = 0 |
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
|
1 2 3 4 5 6 7 8 9 10 11 |
//Insert at current position, Time O(1), Space O(1) public void insert(T value) { LinkNode<T> newNode = new LinkNode<>(value); if (head == null) { head = newNode; } else curr.next = newNode; curr = newNode; curr.next = head; length++; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 |
//Insert at current position, Time O(1), Space O(1) insert(value) { var newNode = new LinkNode(value); if (this.head == null) { this.head = newNode; } else this.curr.next = newNode; this.curr = newNode; this.curr.next = this.head; this.length++; } |
Python
|
1 2 3 4 5 6 7 8 9 10 |
#Insert at current position, Time O(1), Space O(1) def insert_last(self, value) : newNode = LinkNode(value) if (self.head == None) : self.head = newNode else : self.curr.next = newNode self.curr = newNode self.curr.next = self.head self.length += 1 |
Doodle
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
//Delete by the first found key, Time O(n), Space O(1), n is number of nodes in list public void delete(T key) { LinkNode<T> node =search(key); if (node == null) { System.out.println("not found "+ key); return; } LinkNode<T> prev = head; LinkNode<T> p = head.next; while (p.data != key) { prev = p; p = p.next; } if (length == 1) //only one left head = null; else if (p == head) { //delete head prev.next = p.next; head = p.next; } else prev.next = p.next; length --; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
//Delete first node found by key, Time O(n), Space O(1), n is number of nodes in list delete (key) { var node = this.search(key); if (node == null) { console.log("not found "+ key); return; } var prev = this.head; var p = this.head.next; while (p.data !== key) { prev = p; p = p.next; } if (this.length == 1) //only one left this.head = null; else if (p == this.head) { //delete head prev.next = p.next; this.head = p.next; } else prev.next = p.next; this.length --; } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#Delete first node found by key, Time O(n), Space O(1), n is number of nodes in list def delete (self, key) : node = self.search(key) if node == None: print("not found") return prev = self.head p = self.head.next while p.data != key: prev = p p = p.next if self.length == 1: #only one left self.head = None elif p == self.head: #delete head prev.next = p.next self.head = p.next else : prev.next = p.next self.length -= 1 |
Doodle
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
|
1 2 3 4 5 6 7 8 9 10 11 12 |
//Search by key, return the first found, Time O(n), Space O(1) public LinkNode<T> search(T key) { if (head == null) return null; LinkNode<T> p = head; do { if (p.data == key) return p; p = p.next; } while (p != head); return null; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 |
//Search by key, return the first found, Time O(n), Space O(1) search(key) { if (this.head == null) return null; var p = this.head; do { if (p.data == key) return p; p = p.next; } while (p != this.head); return null; } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 |
#Search by key, return the first found, Time O(n), Space O(1) def search(self, key) : if self.head == None: return None p = self.head while True: if p.data == key: return p p = p.next if p == self.head: break return None |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 |
//Print the list, Time O(n), Space O(1) public void print() { if (head == null) return ; System.out.print("Circular list: "); LinkNode<T> p = head; do { System.out.print(p + " "); p = p.next; } while (p != head); System.out.println(); } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 |
//Print the list, Time O(n), Space O(1) print() { if (this.head == null) return ; var line = "Circular list: "; var p = this.head; do { line += p.data + " "; p = p.next; } while(p != this.head); console.log(line); } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 |
#Print the list, Time O(n), Space O(1) def print(self) : if self.head == None: return line = "Circular list: " p = self.head while True: line += str(p.data) + " " p = p.next if p == self.head: break print(line) |
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?
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).