Circularly Linked Lists in Java: Creation & Uses

Instructor: Martin Gibbs

Martin has 16 years experience in Human Resources Information Systems and has a PhD in Information Technology Management. He is an adunct professor of computer science and computer programming.

In this lesson, we explore the circularly linked list or a list that resembles a closed circle more than a single string of nodes. We will discuss its uses and provide examples.

Circularly Linked Lists

Unlike a single- or double-linked list, a circularly linked list is a list that curves back around and connects to itself. It is like a child's toy train where the engine is connected to the caboose.


Linked Lists vs Circularly Linked Lists
Circularly Linked Lists


Circularly linked lists are used when you need to go around the list again. This is most often used in operating systems that use a round-robin scheduling algorithm. This method will allocate CPU resources for a time period, then move the first node to the end so that all processes have a fair shot at the CPU.

Implementing in Java

Let's take a look at how to create a circularly linked list in Java and apply the round-robin method to the list.

Create the Java File

The code for this lesson was compiled and tested using NetBeans IDE 8.2.

First, create a Java file called CircularLinkedList. This creates a package called circularlinkedlist and an initial class file called CircularLinkedList.java.

In the CircularLinkedList.java file, update the code to include the Java utility package, set up the initial variables, and create the first lines of the main function to create a new instance of the CircularLinkedList class and create the calls to the methods (which we will construct shortly):

package circularlinkedlist;
import java.util.*;
public class CircularLinkedList {
  public int size = 0;
  public Node head = null;
  public Node tail = null;
  public static void main(String[] args) {
  }
//this is the closing bracket of the CircularLinkedList class
//all methods will be placed BEFORE this bracket!
}

We now have a list like this: 25, 50, 75, because we added each one to the Head in order. The Tail element is 75. Imagine that each of these numbers represents a process or thread in an operating system. Because the circularly linked list is used in round-robin scheduling, we will eventually rotate the elements in the list.

The Node Class

Next, create a Node class that will do the heavy lifting for adding nodes to the list. For the Node class, it is recommended to create a Java class file in the main package (circularlinkedlist) since this class is used by all methods in the CircularLinkedList class. The code for the Node class is:

package circularlinkedlist;
class Node{
  int element;
  Node next;
  public Node(int element){
   this.element = element;
  }
}

Print

This function loops through the list and displays each element. Note that you can't use an enhanced for loop here because the list is circular it will result in an infinite loop! Instead, the loop checks to be sure it's been all the way through.

public void print(){
  System.out.print("The List So Far: ");
  Node temp = head;
  do {
   System.out.print(" " + temp.element);
   temp = temp.next;
  }
  while(temp != head);
  }
  System.out.println();
}

Add Node to Head

This method adds a node to the head of the list, taking an integer value. We create a new instance of the Node class and then add a new element to the head of the list.

//add a new node at the start of the linked list
public void addNodeToHead(int element){
  Node n = new Node(element);
  if(size==0){
   head = n;
    tail = n;
   n.next = head;
  }else{
   Node temp = head;
   n.next = temp;
   head = n;
   tail.next = head;
  }
  size++;
}

After the class creation in the main method, add the following lines to insert three of the processes and display your results.

   CircularLinkedList myList = new CircularLinkedList();
   myList.addNodeToHead(75);
   myList.addNodeToHead(50);
   myList.addNodeToHead(25);
   myList.print();

Compile and run the program. The output should look like this:


Java Circular List Output


Add Node to Tail

If you try to add a node to the tail of an empty list, you're actually adding it to the head. This method checks to see if the list is empty. If not, then it adds a new node to the tail.

Because the list is circular, the tail actually points to the head. Therefore, the next element past the tail is the head. After setting the next element to the head, increase the size of the list by 1.

public void addNodeToTail(int element){
  if(size==0){
   addNodeToHead(element);
  }else{
   Node n = new Node(element);
   tail.next = n;
   tail = n;
   tail.next = head;
   size++;
  }
}

Back in the main method, add the following line after the print method call. This will add element 100 to the tail of the list.

To unlock this lesson you must be a Study.com Member.
Create your account

Register for a free trial

Are you a student or a teacher?
I am a teacher

Unlock Your Education

See for yourself why 30 million people use Study.com

Become a Study.com member and start learning now.
Become a Member  Back

Earning College Credit

Did you know… We have over 160 college courses that prepare you to earn credit by exam that is accepted by over 2,000 colleges and universities. You can test out of the first two years of college and save thousands off your degree. Anyone can earn credit-by-exam regardless of age or education level.

To learn more, visit our Earning Credit Page

Transferring credit to the school of your choice

Not sure what college you want to attend yet? Study.com has thousands of articles about every imaginable degree, area of study and career path that can help you find the school that's right for you.

Create an account to start this course today
Try it free for 5 days!
Create An Account
Support