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”.
Part 1 – Linked list implementation
Part 2 – Doubly linked list implementation
Part 3 – Ciucular linked list implementation
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
|
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
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
|
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(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 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
|
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 "+ key) 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 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
|
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 p node reference to the head. Then we use a do while loop to get the value of each element and print 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) |
Download Java, JavaScript and Python code
Circular linked list animated visual
Last men standing with circular linked list