Linked List Implementation in Ruby

1. Introduction

A Linked List is a foundational data structure composed of nodes that together represent a sequence. Each node contains data and a reference (or link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. Linked Lists find their applications in various scenarios, including the foundation of many other data structures like stacks and queues.

2. Implementation Steps

1. Define the Node class that will represent each element in the linked list.

2. Initialize the LinkedList class with a head node set to nil (indicating an empty list).

3. Implement the append method to add elements to the end of the list.

4. Implement the prepend method to add elements to the beginning of the list.

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

6. Implement the at method to return the node at a given index.

7. Implement the pop method to remove the last element from the list.

8. Implement the contains? method to check if a value exists in the list.

3. Implementation in Ruby Programming

class Node
    attr_accessor :value, :next_node
    def initialize(value)
        @value = value
        @next_node = nil
    end
end
class LinkedList
    def initialize
        @head = nil
    end
    # Append an element to the end of the list
    def append(value)
        new_node = Node.new(value)
        if @head.nil?
            @head = new_node
        else
            current = @head
            current = current.next_node while current.next_node
            current.next_node = new_node
        end
    end
    # Prepend an element to the beginning of the list
    def prepend(value)
        new_node = Node.new(value)
        new_node.next_node = @head
        @head = new_node
    end
    # Return the size of the list
    def size
        count = 0
        current = @head
        while current
            count += 1
            current = current.next_node
        end
        count
    end
    # Return the node at the given index
    def at(index)
        current = @head
        index.times do
            return nil unless current.next_node
            current = current.next_node
        end
        current
    end
    # Remove the last element from the list
    def pop
        return nil if @head.nil?
        if @head.next_node.nil?
            @head = nil
        else
            current = @head
            current = current.next_node while current.next_node.next_node
            current.next_node = nil
        end
    end
    # Check if the given value exists in the list
    def contains?(value)
        current = @head
        while current
            return true if current.value == value
            current = current.next_node
        end
        false
    end
end
# Client code
ll = LinkedList.new
ll.append("A")
ll.append("B")
ll.prepend("C")
puts "Size of linked list after adding three elements: #{ll.size}"  # Output: 3
puts "Element at index 1: #{ll.at(1).value}"  # Output: A
ll.pop
puts "Size of linked list after popping an element: #{ll.size}"  # Output: 2
puts "Does the linked list contain 'B'? #{ll.contains?('B')}"  # Output: false

Output:

Size of linked list after adding three elements: 3
Element at index 1: A
Size of linked list after popping an element: 2
Does the linked list contain 'B'? false

Explanation:

1. The Node class represents each element in the linked list. It has two attributes - value that stores the actual data, and next_node that points to the next node in the list.

2. The LinkedList class is initialized with a @head node set to nil, indicating the list's starting point.

3. The append method creates a new node and, if the list is empty, assigns it as the head. If the list is not empty, it iterates through the list and adds the new node to the end.

4. The prepend method creates a new node and places it at the beginning of the list by adjusting the head node.

5. The size method iterates through the list and counts the number of nodes.

6. The at method traverses the list to the specified index and returns the node found at that index.

7. The pop method removes the last node from the list by traversing it.

8. The contains? method checks if a particular value exists in the list by iterating through each node.