Circular Linked Lists - Data Structures

There are some times data can be efficiently stored in a linked list like data structure but in a circular fashion. Just like a wheel. That is when circular linked lists come to play.

Basics about RR algorithm 

Round-robin (RR) is one of the algorithms employed by process and network schedulers in computing. As the term is generally used, time slices are assigned to each process in equal portions and in circular order, handling all processes without priority (also known as cyclic executive).  - Wikipedia

What happens basically in RR is to schedule processes in an OS or a packets in a network. Each process is given a time slice to execute (ie: a certain time period ). When time slice is for a process is over it is being interrupted no matter the process is completed or not. Inactive processes are removed. Each active process is given a time slice.

RR can be implemented using linked list as well.

process p = Linked List.removeFirst( )       // remove process from first
Give a time slice to process p
Linked List.addLast(p)         // add process to last

Although this is possible with a singly linked list there are inefficiencies. This is because the same node removed from the first and inserted at the last end. Plus additional computations with regard to this (ex: numberOfNodes --, numberOfNodes ++ ) have to be executed redundantly.

Circular linked list

What is different with circular LL and singly LL ?

-- singly LL's tail node'next refers to null

-- circular LL's tail node'next refers to head node

In circular ll it is enough to maintain head or tale reference because head can be located by tale.next reference.

Image obtained from :https://en.wikipedia.org/wiki/Linked_list

Implementation of Circular Linked List (CCL) ( except node implementation)

public class CircularlyLinkedList<E> {

private Node<E> tail = null;    // tail is referred to null initially

private int size = 0;                  // initial size is is 0

public CircularlyLinkedList( ) { }     // If needed tail and size could be initialized here

public int size( ) { return size; }     // gives number of nodes in CLL

public boolean isEmpty( ) { return size == 0; }       // Checks if CCL is empty

public E first( ) {

  if (isEmpty( )) return null;

  return tail.getNext( ).getElement( );       // return tail.next. which means the first node

}

public E last( ) {

  if (isEmpty( )) return null;

  return tail.getElement( );                  // returns tail node

}

public void rotate( ) {

  if (tail != null)

  tail = tail.getNext( );                      // tail reference is passed to next node

}                                                     // number of nodes doescnt change except for tail position

public void addFirst(E e) {

  if (size == 0) {

    tail = new Node<>(e, null);       // at first the tail is the new node. new node is also the first node

    tail.setNext(tail);

  } 

 else {

    Node<E> newest = new Node<>(e, tail.getNext( ));     // newly added node refers to previous head

    tail.setNext(newest);                                           // tail stays the same because insertion is at front. new tail.next that means head refers to the newly added node

 }

 size++;

}

public void addLast(E e) {

   addFirst(e);                           // add a node to front

   tail = tail.getNext( );            // set tail to front added node

}

public E removeFirst( ) {

  if (isEmpty( )) return null;                   // cant remove nodes from an empty list

 Node<E> temp = tail.getNext( );              // head node is assigned to a node

 if (head == tail) tail = null;                    // When there is only one node left

 else {

   tail.setNext(head.getNext( ));           // tail stays the same. tail.next is referred to temp.next

   size−−;

   return head.getElement( );

 }

}