Linked List — Circular

The circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or a doubly circular linked list.

Advantages of Circular Linked Lists:

• Any node can be a starting point. We can traverse the whole list by starting from any point. We just need to stop when the first visited node is visited again.
• Useful for implementation of a queue. We don’t need to maintain two pointers for the front and rear if we use a circular linked list. We can maintain a pointer to the last inserted node and the front can always be obtained as next of last.
• Circular Doubly Linked Lists are used for the implementation of advanced data structures like Fibonacci Heap.

Read

• Time complexity is O(n)
• Space complexity is O(1)

public void printlist(Node head)
{
    Node node = head;
    if (head != null){
        do
        {
            System.out.print(temp.data + " ");
            node = node.next;
        } while (node != head);
    }
}

Insertion

A node can be added in three ways:

• Insertion in an empty list
• Insertion at the beginning of the list
• Insertion at the end of the list
• Insertion in between the nodes

Insertion in an empty list

• Time complexity is O(1)
• Space complexity is O(1)

static Node addToEmpty(Node last, int data)
{
    if (last != null)
      return last;
      
    Node newNode = new Node();
    newNode.data = data;
    
    last = newNode;
    newNode.next = last;
 
    return last;
}

Insertion at the beginning of the list

• Time complexity is O(1)
• Space complexity is O(1)

static Node addBegin(Node last, int data) {
    if (last == null)
        return addToEmpty(last, data);
        
    Node newNode = new Node();
    newNode.data = data;
​
    newNode.next = last.next;
    last.next = newNode;
​
    return last;
}

Insertion at the end of the list

• Time complexity is O(1)
• Space complexity is O(1)

static Node addEnd(Node last, int data) {
    if (last == null)
        return addToEmpty(last, data);
        
    Node newNode = new Node();
    newNode.data = data;
​
    newNode.next = last.next;
    last.next = newNode;
    last = newNode;
​
    return last;
}

Insertion in between the nodes

• Time complexity is O(N)
• Space complexity is O(1)

static Node addAfter(Node last, int data, int item) {
    if (last == null)
        return null;
 
    Node newNode, prevNode;
    prevNode = last.next;
    do
    {
        if (prevNode.data == item)
        {
            newNode = new Node();
            newNode.data = data;
            newNode.next = prevNode.next;
            prevNode.next = newNode;
 
            if (prevNode == last)
                last = newNode;
            return last;
        }
        prevNode = prevNode.next;
    } while(prevNode != last.next);
 
    return last;
}

Thanks….

I Am…..

I am a Software Engineer having experience in mobile app development with expertise in Java, Android and Flutter. Interested people can contact me through LinkedIn and Instagram.