Linked list in Ruby

A linked list is a linear data structure where elements are stored in nodes, and each node points to the next node in the sequence. Linked lists provide an efficient way to store and manipulate data, especially when insertions and deletions are frequent. In this article, we'll explore how to implement a simple singly linked list in Ruby, complete with code samples.

Creating the node class

To start, we'll create a Node class to represent the elements in our linked list. Each node will contain a value and a reference to the next node in the sequence.

class Node
  attr_accessor :value, :next

  def initialize(value)
    @value = value
    @next = nil
  end
end

Implementing the LinkedList Class

Next, we'll create the LinkedList class, which will manage our list of nodes. We'll start by implementing the initialize method, which sets the head of the list to nil.

class LinkedList
  def initialize
    @head = nil
  end
end

Adding elements to the linked list

We'll now add a method to insert elements at the end of our list. The append method will iterate through the list until it finds the last node and then set the next reference of the last node to the new node.

class LinkedList
  # Previously added code

  def append(value)
    new_node = Node.new(value)

    if @head.nil?
      @head = new_node
      return
    end

    current = @head
    current = current.next while current.next
    current.next = new_node
  end
end

Removing elements from the linked list

To remove elements from our list, we'll implement a delete method that searches for the node with the specified value and removes it from the list by updating the next reference of the previous node.

class LinkedList
  # Previously added code

  def delete(value)
    return if @head.nil?

    if @head.value == value
      @head = @head.next
      return
    end

    current = @head
    while current.next && current.next.value != value
      current = current.next
    end

    current.next = current.next.next if current.next
  end
end

Traversing the linked list

To traverse the linked list and print out its contents, we'll create a to_s method that iterates through the list and collects the values in an array.

class LinkedList
  # Previously added code

  def to_s
    values = []
    current = @head

    while current
      values << current.value
      current = current.next
    end

    values.join(' -> ')
  end
end

Usage

Now that we've implemented our LinkedList class, we can use it to create and manipulate a list of nodes.

list = LinkedList.new
list.append(5)
list.append(10)
list.append(15)

puts list.to_s # Output: 5 -> 10 -> 15

list.delete(10)
puts list.to_s # Output: 5 -> 15

In this article, we've explored how to create a simple singly linked list in Ruby. We've implemented methods to insert and delete elements and traverse the list. Linked lists are a versatile data structure that can be used in various scenarios where dynamic allocation and efficient insertion and deletion operations are needed. With this foundation, you can further