Circular Linked List Implementation in Ruby

1. Introduction

A Circular Linked List is a variation of the standard linked list where the last node of the list points back to the first node, forming a closed loop. It doesn't have a null at the end. This looped configuration provides certain advantages, like navigating the list infinitely in a loop and having a reference to any node, which allows us to traverse the full list.

2. Implementation Steps

1. Define a Node class with two attributes: value and next_node.

2. Initialize the CircularLinkedList class with a head node set to nil.

3. Implement the append method to add nodes to the list.

4. Implement the prepend method to add nodes at the beginning of the list.

5. Implement the size method to count the number of nodes in the list.

6. Implement the delete method to remove nodes from the list.

7. Implement a method to check if the linked list is circular, named is_circular?.

3. Implementation in Ruby Programming

class Node
    attr_accessor :value, :next_node
    def initialize(value)
        @value = value
        @next_node = self
    end
end
class CircularLinkedList
    def initialize
        @head = nil
    end
    # Add element at the end
    def append(value)
        new_node = Node.new(value)
        if @head.nil?
            @head = new_node
        else
            tail = @head
            tail = tail.next_node while tail.next_node != @head
            tail.next_node = new_node
            new_node.next_node = @head
        end
    end
    # Add element at the beginning
    def prepend(value)
        new_node = Node.new(value)
        new_node.next_node = @head
        tail = @head
        tail = tail.next_node while tail.next_node != @head
        tail.next_node = new_node
        @head = new_node
    end
    # Count nodes in the list
    def size
        return 0 if @head.nil?
        count = 1
        current = @head
        while current.next_node != @head
            count += 1
            current = current.next_node
        end
        count
    end
    # Delete a node by value
    def delete(value)
        return if @head.nil?
        if @head.value == value
            @head = @head.next_node
        end
        current = @head
        while current.next_node != @head && current.next_node.value != value
            current = current.next_node
        end
        current.next_node = current.next_node.next_node if current.next_node.value == value
    end
    # Check if list is circular
    def is_circular?
        return false if @head.nil?
        current = @head.next_node
        until current.nil? || current == @head
            current = current.next_node
        end
        current == @head
    end
end
# Client code
circular_list = CircularLinkedList.new
circular_list.append("A")
circular_list.append("B")
circular_list.prepend("C")
puts "Size after adding three elements: #{circular_list.size}"  # Output: 3
circular_list.delete("A")
puts "Size after deleting an element: #{circular_list.size}"  # Output: 2
puts "Is circular: #{circular_list.is_circular?}"  # Output: true

Output:

Size after adding three elements: 3
Size after deleting an element: 2
Is circular: true

Explanation:

1. The Node class represents each element in the circular linked list. Each node has a value and a next_node pointer. Initially, a node points to itself.

2. The CircularLinkedList initializes with a head set to nil.

3. The append method adds a new node at the end. If the list is empty, the new node becomes the head. Otherwise, the method finds the tail, adjusts its pointer to the new node, and then makes the new node point back to the head.

4. The prepend method adds a node at the beginning of the list. It makes the new node point to the old head, finds the tail of the list, and adjusts the tail's next_node to the new node. The new node then becomes the head.

5. The size method counts and returns the number of nodes in the list.

6. The delete method searches for a node with the specified value and removes it from the list.

7. The is_circular? method checks if the list is circular by traversing nodes until it either finds the head node again or reaches a null reference.