Circular linked list

A circular linked list is an ordinary linked list, except that the last element holds the reference to the first element as its next element. This, of course, justifies its name. It would be useful when, for example, you are holding a list of players in a list and they play in turn in a round robin fashion. The implementation is simplified if you use a circular linked list and just keep rotating as the players complete their turn:

Figure 14: A circular linked list

The basic structure of a circular linked list is the same as that of a simple linked list; no more fields or methods are required:

public class CircularLinkedList<E> extends LinkedList<E>{ 
}

Insertion

This is the same as the insertion for a simple linked list, except that you assign the last references next to the first:

    @Override 
    public Node<E> appendFirst(E value) { 
        Node<E> newNode = super.appendFirst(value); 
        last.next = first; 
        return newNode; 
    }

From this, it is not hard to guess how it would be to append at the end:

    @Override 
    public Node<E> appendLast(E value) { 
        Node<E> newNode =  super.appendLast(value); 
        last.next = first; 
        return newNode; 
    } 

Insertion at any other index, of course, remains the same as that for a simple linked list; no more changes are required. This means the complexity of the insertion stays the same as with that for a simple linked list.

Removal

Removal also only changes when you remove the first or the last element. In any case, just updating the last element's next reference solves the purpose. The only place where we need to change this is when we remove the first element. This is because the same operation we used for a simple linked list does not update the previous element's next reference, which we need to do:

    @Override 
    public Node<E> removeFirst() { 
        Node<E> newNode =  super.removeFirst(); 
        last.next = first; 
        return newNode; 
    }

Nothing else needs to be done in removal.

Rotation

What we are doing here is just bringing the next element of the first element to the first position. This is exactly what the name "rotation" would imply:

    public void rotate(){ 
        last = first; 
        first = first.next; 
    }

Figure 15: Rotation of a circular linked list

Doing the same with a simple linked list would require no more than assigning one more reference. You should be able to figure out how to do this with a simple linked list. But this operation looks more natural for a circular linked list, as conceptually, there is no first element.

The real power of a circular linked list is the iterator, which never ends. If the list is non-empty, the iterator will have hasNext(), which always returns true. This means you can simply keep calling the next() method on the iterator and keep processing the elements in a round robin fashion. The following code should make it clear what I mean:

        for(int i=0;i<30;i++){ 
            System.out.print(" "+ linkedList.first); 
            linkedList.rotate(); 
        }

Note

Note that if you try to use the enhanced for loop with a circular linked list, you will run into an infinite loop.