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.
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.
Node<E> temp = tail.getNext( ); // head node is assigned to a node
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 --
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( );
}
}
