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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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
  1. Node Class: Create a Node class to store val and next references.
  2. 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

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

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;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

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)