Circular Singly Linked List

by

In this article, we are going to understand what a circular singly linked list is. We will also see insertions, deletions, and searches in a circular singly linked list. We will also implement a circular singly linked list in Java.

What is a Circular Singly Linked List?

A Circular Singly Linked List (DLL) is a slight variation of a singly or doubly linked list. In this variation, the last node of the list points to the first node of the list and therefore forms a circle. To know when the list has reached to where it will repeat the elements, we can either have a “last” pointer which will point to the last node or by hitting the same node again. None of the nodes will point to NULL in this case. We can create a circular singly as well as a circular doubly linked list. There isn’t much difference apart from a fact that circular doubly linked list will have a “previous” pointer as well.

In this article, we will focus only on the circular singly linked list, but you can create a circuit doubly linked easily by following this article.

1. Advantages of a Circular Singly Linked List

  • The major advantage is that we can start from any node and still we can traverse the entire list.
  • We can maintain one pointer “last” and get the first (head) node using the next pointer of the last node.
  • We no longer need a NULL assignment unless the list itself is empty.
  • It is very useful in CPU round robin scheduling.

2. Disadvantages of a Circular Singly Linked List

  • The biggest disadvantage of this list is that if it is not programmed correctly, you will end up in an infinite loop.
  • Implementing a circular linked list is complex compared to singly linked list.
  • Reversing a circular linked list is complex, it is complex compared to singly linked list.

3. Circular Singly Linked List Representation

A Circular Singly linked list is made of a sequence of nodes. Each node contains a value (data), a pointer to the next node, and the last node’s next points to the first node of the list.

Circular Singly Linked List

As per the above illustration, the following are the important points to be considered.

  • The Head (optional) pointer points to the first node of the list.
  • The Tail (Last) pointer points to the last node of the list.
  • Each node has a data field, and a pointer to the next node.
  • The last node’s next pointer points to the first node.

4. Basic Operations

We will go through the major operations of a linked list, and they are insertion, deletion, display, search, and size.

4.1. Insertion

In a circular singly linked list, we can insert a node in three different ways.

Insert the new node as the first node:

  1. The new node’s next will point to the first node or the last node’s next.
  2. The last node’s next will point to the new node.
Circular Singly Linked List in Java
public void insertAtFirst(int data) {
  Node newNode = new Node(data);
  //Checks if the list is empty.
  if (head == null) {
    //If list is empty, both head and tail would point to new node.
    head = newNode;
    tail = newNode;
    newNode.next = head;
  } else {
    //Store data into temporary node
    Node temp = head;
    //New node will point to temp as next node
    newNode.next = temp;
    //New node will be the head node
    head = newNode;
    //Since, it is circular linked list tail will point to head.
    tail.next = head;
  }
}

At a Given Index:

If we wish to insert a node at any index, we will first check if the index is less than the size of the list, we will then first traverse till the index. Next, we will do the following things:

  1. The new node next will point to the previous node’s next.
  2. The previous node’s next (index-1) will point to the new node.

As you can see below, we had a linked list 0->1->3->0 and we want to insert node 2 at index 2, so we will change the pointers as per the above steps and the linked list will become 0->1->2->3->0. 

public void insertAtIndex(int data, int position) {
  Node temp, newNode;
  int i, count;
  newNode = new Node();
  temp = head;
  count = size();
  if (temp == null || size() < position)
    System.out.println("Index is greater than size of the list");
  else {
    newNode.data = data;
    for (i = 1; i < position - 1; i++) {
      temp = temp.next;
    }
    newNode.next = temp.next;
    temp.next = newNode;
  }
}

At the End of the Linked List:

When we want to insert a node at the end of a circular linked list, we will traverse the circular linked list till the current’s next points to the first node (using head or last pointer). The current is the last node of the list. At this stage we will do the following 3 things:

  1. The new node next will point to the current last node’s next.
  2. The current node’s next will point to the new node.
  3. The last pointer will point to the new node.

As you can see below, we had a linked list 1->2->3->1 and we want to insert node 4 at last, so we will change the pointers as per the above steps and the linked list will become 1->2->3->4->1. 

public void insertAtLast(int data) {
  //Create new node
  Node newNode = new Node(data);
  //Checks if the list is empty.
  if (head == null) {
    //If list is empty, both head and tail would point to new node.
    head = newNode;
    tail = newNode;
    newNode.next = head;
  } else {
    //tail will point to new node.
    tail.next = newNode;
    //New node will become new tail.
    tail = newNode;
    //Since, it is circular linked list tail will point to head.
    tail.next = head;
  }
}

4.2. Deletion

Like insertion, we can delete a node from a circular linked list in 3 ways: To delete a node from the circular linked list, we need to do the following steps. 

Delete the First Node

To delete the first node from the circular linked list, point the last node’s next to the last node’s next’s next. You can see the illustration in the following diagram.

circular singly linked list in Java
public void deleteFirst() {
  if (head == null) {
    return;
  } else {
    if (head != tail) {
      head = head.next;
      tail.next = head;
    }
    //If the list contains only one element
    //then it will remove it and both head and tail will point to null
    else {
      head = tail = null;
    }
  }
}

Delete at an index:

To delete an element at the index from the circular linked list, we first check if the index is less than the size of the list. We then traverse till the index (using the last pointer and by keeping track of the current and previous nodes) and change the previous node’s next to the current node’s next. You can see the illustration in the following diagram.

circular linked list
public void deleteNode(int data) {
  if (head == null)
    System.out.println("List is empty");
  // Find the required node
  Node currentNode = head;
  Node previousNode = new Node();
  while (currentNode.data != data) {
    if (currentNode.next == head) {
      System.out.println("Given node with data " + data + " is not found in the circular linked list.");
      break;
    }
    previousNode = currentNode;
    currentNode = currentNode.next;
  }

  // Check if node is only node
  if (currentNode == head && currentNode.next == head) {
    head = null;
  }

  // If more than one node, check if
  // it is first node
  if (currentNode == head) {
    previousNode = head;
    while (previousNode.next != head) {
      previousNode = previousNode.next;
    }
    head = currentNode.next;
    previousNode.next = head;
  }

  // check if node is last node
  else if (currentNode.next == head) {
    previousNode.next = head;
  } else {
    previousNode.next = currentNode.next;
  }
}

Delete the last element

To delete the last element from the circular linked list, traverse till the second last element and change the previous node’s next to the last node’s next (effectively, the second last element will now point to the first node of the list). You can see the illustration in the following diagram.

circular linked list data structure
public void deleteLast() {
  if (head == null) {
    return;
  } else {
    if (head != tail) {
      Node current = head;
      //Loop will iterate till the second last element as current.next is pointing to tail
      while (current.next != tail) {
        current = current.next;
      }
      //Second last element will be new tail
      tail = current;
      //Tail will point to head as it is a circular linked list
      tail.next = head;
    }
    //If the list contains only one element
    //Then it will remove it and both head and tail will point to null
    else {
      head = tail = null;
    }
  }
}

4.3. Display

To display the nodes of the circular linked list, we will need to start from the head and print the node’s data. We will continue doing this until the current node’s next is not equal to the first node, and that means the end of the list. 

public void display() {
  Node temp = head;
  if (head != null) {
    do {
      System.out.printf("%d ", temp.data);
      temp = temp.next;
    } while (temp != head);
  }
  System.out.printf("\n");
}

4.4. Search

To search for a node of the linked list, we will need to start from the head and check if the current node’s data is equal to the data, or else we will move to the next node in the list. We will continue to go to the next node until the current node’s next is not equal to the first node and in that case, the data is not present in our linked list, or better, we don’t have a node that has the data. 

public void searchNode(int data) {
   System.out.println("Searching for data:" + data);
   //Node current will point to head
   Node current = head;
   int i = 1;
   boolean flag = false;
   //Checks whether list is empty
   if (head == null) {
      System.out.println("List is empty");
   } else {
      do {
         //Compares element to be found with each node present in the list
         if (current.data == data) {
            flag = true;
            break;
         }
         current = current.next;
         i++;
      } while (current != head);
      if (flag)
         System.out.println("Element is present in the list at the position : " + i);
      else
         System.out.println("Element is not present in the list");
   }
}

4.5. Size

To calculate the size of a doubly linked list, we will set a counter at 0 and keep incremented by 1 once we visit a node. We will start with the head and continue to go to the next node until the current node’s next is not equal to the first node. As said, we will increment the counter for each node we traverse. At the end, we will have the size of the list in the counter variable.You can see the code for this below. In our example, we are updating the size variable at every insert and delete, so we can directly use that variable. 

public int size() {
   int size = 0;
   if (head != null) {
      Node temp = head;
      while (temp.next != head) {
         temp = temp.next;
         size++;
      }
      size++;
   }
   return size;
}

5. Time and Space Complexity:

time and space complexity for circular singly linked list

6. Java Example

We have seen the all use cases for circular singly linked list. Let’s see how to implement a circular singly linked list in Java.

package DS.list;

public class CircularLinkedList {

  static class Node {
    int data;
    Node next;
    Node() {}
    Node(int data) {
      this.data = data;
    }
  }

  private Node head;
  private Node tail;

  // constructor   
  public CircularLinkedList() {
    this.head = null;
    this.tail = null;
  }

  public boolean isEmpty() {
    return head == null;
  }

  /**
   * insertAtFirst
   * @param data
   */
  public void insertAtFirst(int data) {
    Node newNode = new Node(data);
    //Checks if the list is empty.   
    if (head == null) {
      //If list is empty, both head and tail would point to new node.   
      head = newNode;
      tail = newNode;
      newNode.next = head;
    } else {
      //Store data into temporary node   
      Node temp = head;
      //New node will point to temp as next node   
      newNode.next = temp;
      //New node will be the head node   
      head = newNode;
      //Since, it is circular linked list tail will point to head.   
      tail.next = head;
    }
  }

  /**
   * insertAtLast
   * @param data
   */
  public void insertAtLast(int data) {
    //Create new node   
    Node newNode = new Node(data);
    //Checks if the list is empty.   
    if (head == null) {
      //If list is empty, both head and tail would point to new node.   
      head = newNode;
      tail = newNode;
      newNode.next = head;
    } else {
      //tail will point to new node.   
      tail.next = newNode;
      //New node will become new tail.   
      tail = newNode;
      //Since, it is circular linked list tail will point to head.   
      tail.next = head;
    }
  }

  /**
   *
   * @param data
   * @param position
   */
  public void insertAtIndex(int data, int position) {
    Node temp, newNode;
    int i, count;
    newNode = new Node();
    temp = head;
    count = size();
    if (temp == null || size() < position)
      System.out.println("Index is greater than size of the list");
    else {
      newNode.data = data;
      for (i = 1; i < position - 1; i++) {
        temp = temp.next;
      }
      newNode.next = temp.next;
      temp.next = newNode;
    }
  }

  /**
   * delete the first node.
   */
  public void deleteFirst() {
    if (head == null) {
      return;
    } else {
      if (head != tail) {
        head = head.next;
        tail.next = head;
      }
      //If the list contains only one element   
      //then it will remove it and both head and tail will point to null   
      else {
        head = tail = null;
      }
    }
  }

  /**
   *
   */
  public void deleteLast() {
    if (head == null) {
      return;
    } else {
      if (head != tail) {
        Node current = head;
        //Loop will iterate till the second last element as current.next is pointing to tail   
        while (current.next != tail) {
          current = current.next;
        }
        //Second last element will be new tail   
        tail = current;
        //Tail will point to head as it is a circular linked list   
        tail.next = head;
      }
      //If the list contains only one element   
      //Then it will remove it and both head and tail will point to null   
      else {
        head = tail = null;
      }
    }
  }

  /**
   *
   * @param data
   * @return
   */
  public void deleteNode(int data) {
    if (head == null)
      System.out.println("List is empty");
    // Find the required node   
    Node currentNode = head;
    Node previousNode = new Node();
    while (currentNode.data != data) {
      if (currentNode.next == head) {
        System.out.println("Given node with data " + data + " is not found in the circular linked list.");
        break;
      }
      previousNode = currentNode;
      currentNode = currentNode.next;
    }

    // Check if node is only node   
    if (currentNode == head && currentNode.next == head) {
      head = null;
    }

    // If more than one node, check if   
    // it is first node   
    if (currentNode == head) {
      previousNode = head;
      while (previousNode.next != head) {
        previousNode = previousNode.next;
      }
      head = currentNode.next;
      previousNode.next = head;
    }

    // check if node is last node   
    else if (currentNode.next == head) {
      previousNode.next = head;
    } else {
      previousNode.next = currentNode.next;
    }
  }

  /**
   * Display forward
   */
  public void display() {
    Node temp = head;
    if (head != null) {
      do {
        System.out.printf("%d ", temp.data);
        temp = temp.next;
      } while (temp != head);
    }
    System.out.printf("\n");
  }

  public int size() {
    int size = 0;
    if (head != null) {
      Node temp = head;
      while (temp.next != head) {
        temp = temp.next;
        size++;
      }
      size++;
    }
    return size;
  }

  /**
   * Search the given node in doubly linked list
   * @param data
   */
  public void searchNode(int data) {
    System.out.println("Searching for data:" + data);
    //Node current will point to head   
    Node current = head;
    int i = 1;
    boolean flag = false;
    //Checks whether list is empty   
    if (head == null) {
      System.out.println("List is empty");
    } else {
      do {
        //Compares element to be found with each node present in the list   
        if (current.data == data) {
          flag = true;
          break;
        }
        current = current.next;
        i++;
      } while (current != head);
      if (flag)
        System.out.println("Element is present in the list at the position : " + i);
      else
        System.out.println("Element is not present in the list");
    }
  }

  public static void main(String[] args) {
    CircularLinkedList list = new CircularLinkedList();
    list.insertAtFirst(1);
    list.display();
    System.out.println("size :" + list.size());
    list.insertAtFirst(2);
    list.display();
    System.out.println("size :" + list.size());
    list.insertAtLast(3);
    list.display();
    System.out.println("size :" + list.size());
    list.display();
    list.insertAtLast(4);
    System.out.println("size :" + list.size());
    list.display();
    list.insertAtIndex(5, 3);
    System.out.println("size :" + list.size());
    list.display();

    list.deleteNode(8);
    System.out.println("size :" + list.size());
    list.display();

    list.deleteNode(2);
    System.out.println("Node with data 2 has been deleted");
    System.out.println("size :" + list.size());
    list.display();

    list.searchNode(5);
    list.display();
  }
}

The Output:

Summary

In this article, we have learnt:

  1. The basics of Circular Linked List.
  2. The usage of a Circular Linked List.
  3. The benefits of a Circular Linked List.
  4. The limitations of a Circular Linked List.
  5. The insertion and deletion in a Circular Linked List
  6. The search and size of a Circular Linked List
  7. The Java program to create a Circular Linked List and perform all the operations.
  8. The test class and program output.

You can find the source code for this example at our GitHub repository.