Java Data Structures - Circular Singly Linked List Other Related Topics

Java - Circular Singly Linked List



A circular singly linked list is a linear data structure, in which the elements are stored in the form of a node. Each node contains two sub-elements. A data part that stores the value of the element and the next part that stores the link to the next node as shown in the below image:

Linked List Node

The first node also known as HEAD is always used as a reference to traverse the list. The last node points to HEAD. A circular singly linked list can be visualized as a chain of nodes, where every node points to the next node. Along with this, next of the last node is linked to the head node.

Linked List

Implementation of Circular Singly Linked List

Representation:

In Java, circular doubly linked list can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.

//node structure
class Node {
    int data;
    Node next;
};

class LinkedList {
  Node head;
  //constructor to create an empty LinkedList
  LinkedList(){
    head = null;
  }
};

Create a Circular Singly Linked List

Let us create a simple circular singly linked list which contains three data nodes.

//node structure
class Node {
    int data;
    Node next;
};

class LinkedList {
  Node head;
  //constructor to create an empty LinkedList
  LinkedList(){
    head = null;
  }  
};

// test the code 
public class Implementation { 
  public static void main(String[] args) {
    //create an empty LinkedList
    LinkedList MyList = new LinkedList();

    //Add first node.
    Node first = new Node();
    first.data = 10;
    //linking with head node
    MyList.head = first;
    //linking next of the node with head
    first.next = MyList.head; 

    //Add second node.
    Node second = new Node();
    second.data = 20;
    //linking with first node
    first.next = second;
    //linking next of the node with head
    second.next = MyList.head; 

    //Add third node.
    Node third = new Node();
    third.data = 30;
    //linking with second node
    second.next = third;
    //linking next of the node with head
    third.next = MyList.head; 
  }
}

Traverse a Circular Singly Linked List

A circular singly linked list can be traversed from any node of the list using a temp node. Keep on moving the temp node to the next one and displaying its content. Stop the traversal, after reaching the starting node.

//node structure
class Node {
    int data;
    Node next;
};

class LinkedList {
  Node head;
  //constructor to create an empty LinkedList
  LinkedList(){
    head = null;
  }

  //display the content of the list
  void PrintList() {
    Node temp = new Node();
    temp = this.head;
    if(temp != null) {
      System.out.print("The list contains: ");
      while(true) {
        System.out.print(temp.data + " ");
        temp = temp.next;
        if(temp == this.head)
          break;
      }
      System.out.println();
    } else {
      System.out.println("The list is empty.");
    }
  }     
};

// test the code 
public class Implementation { 
  public static void main(String[] args) {
    //create an empty LinkedList
    LinkedList MyList = new LinkedList();

    //Add first node.
    Node first = new Node();
    first.data = 10;
    //linking with head node
    MyList.head = first;
    //linking next of the node with head
    first.next = MyList.head; 

    //Add second node.
    Node second = new Node();
    second.data = 20;
    //linking with first node
    first.next = second;
    //linking next of the node with head
    second.next = MyList.head; 

    //Add third node.
    Node third = new Node();
    third.data = 30;
    //linking with second node
    second.next = third;
    //linking next of the node with head
    third.next = MyList.head; 

    //print the content of list
    MyList.PrintList();    
  }
}

The above code will give the following output:

The list contains: 10 20 30