Doubly Linked List Implementation in Ruby

1. Introduction

A Doubly Linked List is a type of linked list in which each node contains a data part and two pointers. The two pointers are:

1. A pointer to the next node in the sequence (next_node).

2. A pointer to the preceding node in the sequence (prev_node).

This bidirectional link allows for more efficient traversal in both directions, but at the cost of increased complexity in insertion and deletion operations, as well as increased memory overhead due to the extra pointer.

2. Implementation Steps

1. Define the Node class, which will have three attributes: value, next_node, and prev_node.

2. Initialize the DoublyLinkedList class with a head node and a tail node, both set to nil.

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

4. Implement the prepend method to add elements at the beginning.

5. Implement the delete method to remove a node from the list.

6. Implement the size method to get the number of elements in the list.

7. Implement the at method to get the node at a given index.

3. Implementation in Ruby Programming

class Node
    attr_accessor :value, :next_node, :prev_node
    def initialize(value)
        @value = value
        @next_node = nil
        @prev_node = nil
    end
end
class DoublyLinkedList
    def initialize
        @head = nil
        @tail = nil
    end
    # Append element at the end
    def append(value)
        new_node = Node.new(value)
        if @head.nil?
            @head = new_node
            @tail = new_node
        else
            new_node.prev_node = @tail
            @tail.next_node = new_node
            @tail = new_node
        end
    end
    # Prepend element at the beginning
    def prepend(value)
        new_node = Node.new(value)
        if @head.nil?
            @head = new_node
            @tail = new_node
        else
            new_node.next_node = @head
            @head.prev_node = new_node
            @head = new_node
        end
    end
    # Delete a node with given value
    def delete(value)
        current = @head
        while current
            if current.value == value
                if current.prev_node
                    current.prev_node.next_node = current.next_node
                else
                    @head = current.next_node
                end
                if current.next_node
                    current.next_node.prev_node = current.prev_node
                else
                    @tail = current.prev_node
                end
            end
            current = current.next_node
        end
    end
    # Return size of the list
    def size
        count = 0
        current = @head
        while current
            count += 1
            current = current.next_node
        end
        count
    end
    # Return node at given index
    def at(index)
        current = @head
        index.times do
            return nil unless current.next_node
            current = current.next_node
        end
        current
    end
end
# Client code
dll = DoublyLinkedList.new
dll.append("A")
dll.append("B")
dll.prepend("C")
puts "Size after adding three elements: #{dll.size}"  # Output: 3
puts "Element at index 1: #{dll.at(1).value}"  # Output: A
dll.delete("A")
puts "Size after deleting an element: #{dll.size}"  # Output: 2

Output:

Size after adding three elements: 3
Element at index 1: A
Size after deleting an element: 2

Explanation:

1. The Node class represents each element in the doubly linked list. It has attributes for value, next_node (pointer to the next node), and prev_node (pointer to the previous node).

2. The DoublyLinkedList class initializes with both head and tail nodes set to nil.

3. The append method adds a node to the end. If the list is empty, the new node becomes both the head and tail. Otherwise, it is linked to the previous tail and then becomes the new tail.

4. The prepend method works similarly but adds the new node at the start.

5. The delete method iterates through the list searching for a node with a matching value. Once found, it adjusts the pointers of the neighboring nodes to exclude the found node, effectively deleting it.

6. The size method iterates through all nodes, counting them.

7. The at method traverses the list to a specified index and returns the node found there.