LEARN WITH ME

Singly Circular Linked List

Overview

A singly circular linked list is a variation of a linked list where the last node's next pointer points back to the first node, forming a circular structure. Each node contains two components:

• A data field to store the value.
• A pointer to the next node in the sequence (next pointer).

This structure allows for continuous traversal through the list.

Key Operations on a Singly Circular Linked List

• Insertion:
• At the Beginning: To insert a new node at the beginning, create a new node and set its next pointer to the current head. Then traverse to the last node and set its next pointer to the new node. Update the head to point to this new node.
  Time Complexity: O(1).
• At the End: To insert a new node at the end, create a new node and traverse to the last node. Set the last node's next pointer to the new node and the new node's next pointer to the head.
  Time Complexity: O(n).
• At a Specific Position: To insert a new node at a specific position, traverse to the node before the desired position and adjust the pointers to insert the new node.
  Time Complexity: O(n).

Insertion Operation

Insertion Code

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class SinglyCircularLinkedList {
    Node head;

    // Insert at the beginning
    public void insertAtBeginning(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            newNode.next = head;
        } else {
            Node temp = head;
            while (temp.next != head) {
                temp = temp.next;
            }
            temp.next = newNode;
            newNode.next = head;
            head = newNode;
        }
    }

    // Insert at the end
    public void insertAtEnd(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            newNode.next = head;
        } else {
            Node temp = head;
            while (temp.next != head) {
                temp = temp.next;
            }
            temp.next = newNode;
            newNode.next = head;
        }
    }

    // Insert at a specific position
    public void insertAtPosition(int data, int position) {
        Node newNode = new Node(data);
        if (position == 0) {
            insertAtBeginning(data);
        } else {
            Node temp = head;
            for (int i = 0; i < position - 1; i++) {
                if (temp.next == head) {
                    System.out.println("Position out of bounds");
                    return;
                }
                temp = temp.next;
            }
            newNode.next = temp.next;
            temp.next = newNode;
        }
    }
}
                    

• Deletion:
• At the Beginning: To delete the first node, set the head to the next node of the current head. Traverse to the last node and update its next pointer to the new head.
  Time Complexity: O(1).
• By Key: To delete a node by its key, traverse the list to find the node, then adjust the pointers of the previous node and the next node.
  Time Complexity: O(n).
• At a Specific Position: To delete a node at a specific position, traverse to the node before the desired position, then adjust pointers to remove the node.
  Time Complexity: O(n).

Deletion Operation

Deletion Code

class SinglyCircularLinkedList {
    Node head;

    // Delete at the beginning
    public void deleteAtBeginning() {
        if (head == null) {
            return;
        }
        if (head.next == head) {
            head = null;
        } else {
            Node temp = head;
            while (temp.next != head) {
                temp = temp.next;
            }
            head = head.next;
            temp.next = head;
        }
    }

    // Delete by key
    public void deleteByKey(int key) {
        if (head == null) {
            return;
        }
        Node temp = head;
        Node prev = null;
        while (temp.next != head && temp.data != key) {
            prev = temp;
            temp = temp.next;
        }
        if (temp.data == key) {
            if (prev == null) {
                deleteAtBeginning();
            } else {
                prev.next = temp.next;
            }
        }
    }

    // Delete at a specific position
    public void deleteAtPosition(int position) {
        if (head == null) {
            return;
        }
        if (position == 0) {
            deleteAtBeginning();
        } else {
            Node temp = head;
            Node prev = null;
            for (int i = 0; i < position; i++) {
                if (temp.next == head) {
                    System.out.println("Position out of bounds");
                    return;
                }
                prev = temp;
                temp = temp.next;
            }
            if (prev != null) {
                prev.next = temp.next;
            }
        }
    }
}
                    

• Displaying the List: To display the elements of the singly circular linked list, traverse the list starting from the head until you reach the head again.

Displaying Code

class SinglyCircularLinkedList {
    Node head;

    // Print the list
    public void printList() {
        if (head == null) {
            System.out.println("List is empty");
            return;
        }
        Node temp = head;
        do {
            System.out.print(temp.data + " ");
            temp = temp.next;
        } while (temp != head);
        System.out.println();
    }
}
                    

Applications of Singly Circular Linked Lists

Singly circular linked lists are useful in scenarios where continuous traversal is needed, such as:

• Implementing round-robin scheduling algorithms.
• Creating circular queues and buffers.
• In multimedia applications for managing playlists where the last song loops back to the first.
• In certain memory management systems where continuous data structures are beneficial.

Advantages and Disadvantages

Advantages:

• Efficient for circular traversal without needing to check for the end of the list.
• Simpler implementation of certain algorithms like round-robin scheduling.

Disadvantages:

• Potentially complex for certain operations like finding specific nodes.
• Not suitable for scenarios where non-circular traversal is needed.