Understanding Ruby Linked Lists

Introduction

Linked lists are a fundamental data structure in computer science that consist of nodes linked together in a sequential manner. In this article, we will explore how linked lists work in Ruby and how you can use them in your programs.

What is a Linked List?

A linked list is a collection of nodes where each node contains a value and a reference to the next node in the sequence. Unlike arrays, linked lists do not have a fixed size and can grow dynamically as nodes are added or removed.

Types of Linked Lists

There are several types of linked lists, including:

Singly Linked List: Each node has a reference to the next node in the sequence.
Doubly Linked List: Each node has references to both the next and previous nodes in the sequence.
Circular Linked List: The last node in the list points back to the first node, creating a circular structure.

Implementing a Linked List in Ruby

In Ruby, we can implement a linked list using classes to represent nodes and the list itself. Here is a simple example of a singly linked list in Ruby:

class Node
  attr_accessor :value, :next_node

  def initialize(value, next_node = nil)
    @value = value
    @next_node = next_node
  end
end

class LinkedList
  def initialize
    @head = nil
  end

  def add(value)
    if @head.nil?
      @head = Node.new(value)
    else
      current = @head
      while !current.next_node.nil?
        current = current.next_node
      end
      current.next_node = Node.new(value)
    end
  end

  def display
    current = @head
    while !current.nil?
      puts current.value
      current = current.next_node
    end
  end
end

# Create a new linked list
list = LinkedList.new

# Add nodes to the list
list.add(1)
list.add(2)
list.add(3)

# Display the list
list.display

Operations on Linked Lists

Linked lists support various operations, including:

Adding a node to the end of the list
Inserting a node at a specific position
Removing a node from the list
Searching for a node with a specific value

Adding a Node

To add a node to the end of a linked list, you can traverse the list until you reach the last node and then add the new node:

def add(value)
  if @head.nil?
    @head = Node.new(value)
  else
    current = @head
    while !current.next_node.nil?
      current = current.next_node
    end
    current.next_node = Node.new(value)
  end
end

Inserting a Node

To insert a node at a specific position in the list, you can traverse the list until you reach the desired position and then insert the new node:

def insert_at(value, position)
  if position == 0
    new_node = Node.new(value, @head)
    @head = new_node
  else
    current = @head
    (position - 1).times do
      current = current.next_node
    end
    new_node = Node.new(value, current.next_node)
    current.next_node = new_node
  end
end

Removing a Node

To remove a node from the list, you can traverse the list until you find the node to remove and then update the references to skip over it:

def remove(value)
  if @head.value == value
    @head = @head.next_node
  else
    current = @head
    while !current.next_node.nil? && current.next_node.value != value
      current = current.next_node
    end
    unless current.next_node.nil?
      current.next_node = current.next_node.next_node
    end
  end
end

Conclusion

Linked lists are a versatile data structure that can be used in a variety of applications. By understanding how linked lists work and how to implement them in Ruby, you can take advantage of their dynamic nature and efficient operations in your programs.