Circular Linked List Complete Implementation

Problem

Implement a circular linked list. A circular linked list is a variation of a linked list in which the last element is linked back to the first element, forming a circle. The list should support the following operations:

insert(int val): Insert an element into the circular linked list.
delete(int val): Delete an element from the circular linked list.
search(int val): Search for an element in the circular linked list.
display(): Display all the elements in the circular linked list

Examples

Example 1:

Input: 
["insert(1)", "insert(2)", "insert(3)", "display()", "search(2)", "delete(2)", "display()"]
Output:
[null, null, null, [1, 2, 3], true, null, [1, 3]]
Explanation:
1. Insert 1: The list becomes [1].
2. Insert 2: The list becomes [1, 2].
3. Insert 3: The list becomes [1, 2, 3].
4. Display: Displays the list [1, 2, 3].
5. Search 2: Returns true as 2 is found in the list.
6. Delete 2: The list becomes [1, 3].
7. Display: Displays the list [1, 3].

Solution

Method 1 - Using Linkedlist

A circular linked list connects the last node back to the first node. Maintaining both a head and a tail pointer allows efficient insertion at both the head and the tail. The tail pointer helps to avoid traversing the entire list when inserting a new element at the end.

Approach

We can use singly linked list - Singly Linked List Implementation. Here is how a linked list look:

graph LR
    head --> N1[1]
    N1 --> N2[2]
    N2 --> N3[3]
    N3 --> null((null))

But in circular linked list, we connect the last node to the first node.

graph LR
    head --> N1[1]
    N1 --> N2[2]
    N2 --> N3[3]
    N3 --> N1

Node Class: Create a Node class to store val and next references.
CircularLinkedList Class:
- Initialization: Initialize head and tail pointers.
- Insert at Head: Insert a new node at the beginning and adjust the head and tail pointers.
- Insert at End: Insert a new node at the end using the tail pointer.
- Delete: Find the node to delete and update the links accordingly.
- Search: Traverse the list to find the target value.
- Get: Traverse the list to get the value at the specified index.
- Display: Traverse the list starting from the head and collect all elements.

Code

Java

class ListNode {
	int val;
	ListNode next;

	ListNode(int val) {
		this.val = val;
		this.next = null;
	}
}

class CircularLinkedList {
	private ListNode head;
	private ListNode tail;

	public CircularLinkedList() {
		head = null;
		tail = null;
	}

	// Insert at the head of the circular linked list
	public void insertAtHead(int val) {
		ListNode newNode = new ListNode(val);
		if (head == null) {
			head = newNode;
			tail = newNode;
			newNode.next = head;
		} else {
			newNode.next = head;
			head = newNode;
			tail.next = head;
		}
	}

	// Insert at the end of the circular linked list
	public void insertAtEnd(int val) {
		ListNode newNode = new ListNode(val);
		if (head == null) {
			head = newNode;
			tail = newNode;
			newNode.next = head;
		} else {
			tail.next = newNode;
			tail = newNode;
			tail.next = head;
		}
	}

	// Delete an element from the circular linked list
	public void delete(int val) {
		if (head == null) {
			return;
		}

		ListNode current = head;
		ListNode prev = null;

		while (current.val != val) {
			if (current.next == head) {
				return; // Value not found
			}
			prev = current;
			current = current.next;
		}

		if (current == head) {
			if (head == tail) {
				head = null;
				tail = null;
			} else {
				head = head.next;
				tail.next = head;
			}
		} else if (current == tail) {
			tail = prev;
			tail.next = head;
		} else {
			prev.next = current.next;
		}
	}

	// Search for an element in the circular linked list
	public boolean search(int val) {
		if (head == null) {
			return false;
		}

		ListNode current = head;
		do {
			if (current.val == val) {
				return true;
			}
			current = current.next;
		} while (current != head);

		return false;
	}

	// Get the element at the specified index
	public int get(int index) {
		if (head == null) {
			throw new IndexOutOfBoundsException();
		}

		ListNode current = head;
		int count = 0;

		do {
			if (count == index) {
				return current.val;
			}
			count++;
			current = current.next;
		} while (current != head);

		throw new IndexOutOfBoundsException();
	}

	// Display all elements in the circular linked list
	public List<Integer> display() {
		List<Integer> ans = new ArrayList<>();
		if (head == null) {
			return ans;
		}

		ListNode current = head;
		do {
			ans.add(current.val);
			current = current.next;
		} while (current != head);

		return ans;
	}
}

Python

class CircularLinkedList:
    def __init__(self):
        self.head: Optional['Solution.ListNode'] = None
        self.tail: Optional['Solution.ListNode'] = None

    def insertAtHead(self, val: int) -> None:
        new_node = Solution.ListNode(val)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
            new_node.next = self.head
        else:
            new_node.next = self.head
            self.head = new_node
            self.tail.next = self.head

    def insertAtEnd(self, val: int) -> None:
        new_node = Solution.ListNode(val)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
            new_node.next = self.head
        else:
            self.tail.next = new_node
            self.tail = new_node
            self.tail.next = self.head

    def delete(self, val: int) -> None:
        if self.head is None:
            return

        current = self.head
        prev: Optional['Solution.ListNode'] = None

        while current.val != val:
            if current.next == self.head:
                return  # Value not found
            prev = current
            current = current.next

        if current == self.head:
            if self.head == self.tail:
                self.head = None
                self.tail = None
            else:
                self.head = self.head.next
                self.tail.next = self.head
        elif current == self.tail:
            self.tail = prev
            self.tail.next = self.head
        else:
            if prev:
                prev.next = current.next

    def search(self, val: int) -> bool:
        if not self.head:
            return False

        current = self.head
        while True:
            if current.val == val:
                return True
            current = current.next
            if current == self.head:
                break

        return False

    def get(self, index: int) -> int:
        if not self.head:
            raise IndexError("Index out of bounds")

        current = self.head
        count = 0

        while True:
            if count == index:
                return current.val
            count += 1
            current = current.next
            if current == self.head:
                break

        raise IndexError("Index out of bounds")

    def display(self) -> List[int]:
        ans: List[int] = []
        if not self.head:
            return ans

        current = self.head
        while True:
            ans.append(current.val)
            current = current.next
            if current == self.head:
                break

        return ans

Complexity

⏰ Time complexity
- insertAtHead, insertAtEnd: O(1)
- delete: O(n)
- search: O(n)
- get: O(n)
- display: O(n)
🧺 Space complexity: O(n)

Problem#

Examples#

Solution#

Method 1 - Using Linkedlist#

Approach#

Code#

Java#

Python#

Complexity#