Ring List

data-structures

Definition

Ring List

A ring list is a variation of a linked list in which the last node points back to the first node, forming a closed loop. Consequently, there is no null termination, and any node can be reached from any other node by traversing the list.

Complexity

The time complexity of operations on a circular linked list is generally the same as a singly linked list, with the added benefit of easier circular traversal:

Operation	Time Complexity
Insertion (at beginning)	$O(1)$
Insertion (at end)	$O(1)$ (with tail pointer)
Deletion (at beginning)	$O(1)$
Search	$O(n)$

Implementations

Java Implementation

The following implementation utilises a “nil” sentinel node to simplify boundary conditions during insertion and deletion.

public class RingList<T> {
    private class Node {
        T data;
        Node next;
 
        private Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
 
    private Node nil = new Node(null, null);
 
    public RingList() {
        this.nil.next = this.nil;
    }
 
    public T poll() {
        Node n = nil.next;
        this.nil.next = n.next;
        return n.data;
    }
 
    public void add(T data) {
        nil.data = data;
        nil.next = (nil = new Node(null, nil.next));
    }
 
    public void print() {
        Node n = nil.next;
        while (n != nil) {
            System.out.print(n.data + " ");
            n = n.next;
        }
        System.out.println();
    }
}