Ruby LinkedList Class Tutorial: Implementation and Usage

Ruby has a built-in linked list class called LinkedList, which is part of the enumerator package. The LinkedList class is a linear data structure that consists of a sequence of nodes, where each node contains a data element and a reference to the next node in the list.

Here is an example code to create and use a linked list in Ruby:

require 'enumerator'

class Node
  attr_accessor :value, :next_node
  
  def initialize(value, next_node = nil)
    @value = value
    @next_node = next_node
  end
end

class LinkedList
  include Enumerable
  
  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 each(&block)
    current = @head
    while current != nil
      yield current.value
      current = current.next_node
    end
  end
end

# create a new linked list
list = LinkedList.new

# add elements to the list
list.add(1)
list.add(2)
list.add(3)

# print the elements in the list
list.each do |value|
  puts value
end

In this example, we define a Node class that represents a node in the linked list. The LinkedList class is then defined, which includes the Enumerable module to enable iteration over the elements in the list.

The LinkedList class has an add method that adds a new element to the list. The each method is defined to iterate over the elements in the list, yielding each value to a block.

Finally, we create a new LinkedList instance, add some elements to it, and then print out the elements using the each method.

When we run the above code, it will output:

1
2
3

This shows that the linked list is functioning correctly, and we are able to iterate over its elements using the each method.

The LinkedList class can be further extended to include additional methods for manipulating the list, such as remove, insert, and reverse. For example, here is an implementation of the remove method:

def remove(value)
  if @head == nil
    return
  end
  
  if @head.value == value
    @head = @head.next_node
    return
  end
  
  current = @head
  while current.next_node != nil
    if current.next_node.value == value
      current.next_node = current.next_node.next_node
      return
    end
    current = current.next_node
  end
end

This method removes the first node in the list that has the given value. If the list is empty or the value is not found in the list, the method does nothing.

The LinkedList class in Ruby has the following methods:

1. initialize: Initializes a new empty linked list.
2. add: Adds a new node to the end of the linked list.
3. each: Iterates over each node in the linked list and yields the value to a block.
4. empty?: Returns true if the linked list is empty.
5. first: Returns the first value in the linked list.
6. last: Returns the last value in the linked list.
7. length: Returns the number of nodes in the linked list.
8. remove: Removes the first node in the linked list that has the given value.
9. reverse: Reverses the order of the nodes in the linked list.
10. [](index): Returns the value at the given index in the linked list.

Initialize a new empty linked list.

Example code:

def initialize
  @head = nil
end

Explanation: This method creates a new linked list with an empty head node.

Time complexity: O(1)

Space complexity: O(1)

Add a new node to the end of the linked list.

Example code:

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

Explanation: This method adds a new node with the given value to the end of the linked list. If the list is empty, the new node becomes the head node. Otherwise, the method iterates through the list until it reaches the last node, and then adds the new node as its next node.

Time complexity: O(n), where n is the number of nodes in the list.

Space complexity: O(1)

Iterate over each node in the linked list and yields the value to a block.

Example code:

def each(&block)
  current = @head
  while current != nil
    yield current.value
    current = current.next_node
  end
end

Explanation: This method allows the linked list to be iterated over using the each method. It yields each value in the list to the given block.

Time complexity: O(n), where n is the number of nodes in the list.

Space complexity: O(1)

Return true if the linked list is empty.

Example code:

def empty?
  @head.nil?
end

Explanation: This method checks if the linked list is empty by checking if the head node is nil.

Time complexity: O(1)

Space complexity: O(1)

Return the first value in the linked list.

Example code:

def first
  @head.value
end

Explanation: This method returns the value of the head node in the linked list.

Time complexity: O(1)

Space complexity: O(1)

Return the last value in the linked list.

Example code:

def last
  current = @head
  while current.next_node != nil
    current = current.next_node
  end
  current.value
end

Explanation: This method returns the value of the last node in the linked list. It iterates through the list until it reaches the last node, and then returns its value.

Time complexity: O(n), where n is the number of nodes in the list.

Space complexity: O(1)

Return the number of nodes in the linked list.

Example code:

def length
  count = 0
  current = @head
  while current != nil
    count += 1
    current = current.next_node
  end
  count
end

Explanation: This method returns the number of nodes in the linked list by iterating through the list and counting the nodes.

Time complexity: O(n), where n is the number of nodes in the list.

Space complexity: O(1)

Remove the first node in the linked list that has the given value.

Example code:

def remove(value)
  if @head == nil
    return
  end
  
  if @head.value == value
    @head = @head.next_node
    return
  end
  
  current = @head
  while current.next_node != nil
    if current.next_node.value == value
      current.next_node = current.next_node.next_node
      return
    end
    current = current.next_node
  end
end

Explanation: This method removes the first node in the linked list that has the given value. If the list is empty, the method does nothing. If the head node has the given value, it is removed and the next node becomes the new head. Otherwise, the method iterates through the list until it finds the node with the given value, removes it, and updates the links to connect the previous node to the next node.

Time complexity: O(n), where n is the number of nodes in the list.

Space complexity: O(1)

Reverse the order of the nodes in the linked list.

Example code:

def reverse
  previous = nil
  current = @head
  while current != nil
    next_node = current.next_node
    current.next_node = previous
    previous = current
    current = next_node
  end
  @head = previous
end

Explanation: This method reverses the order of the nodes in the linked list. It does this by iteratively changing the links between nodes so that each node points to its previous node instead of its next node.

Time complexity: O(n), where n is the number of nodes in the list.

Space complexity: O(1)

Return the value at the given index in the linked list.

Example code:

def [](index)
  count = 0
  current = @head
  while current != nil
    if count == index
      return current.value
    end
    count += 1
    current = current.next_node
  end
  nil
end

Explanation: This method returns the value of the node at the given index in the linked list. It does this by iterating through the list until it reaches the node at the given index, and then returns its value. If the index is out of bounds, the method returns nil.

Time complexity: O(n), where n is the number of nodes in the list.

Space complexity: O(1)

Doubly linked list in Ruby

we can modify the LinkedList class to create a doubly linked list in Ruby. A doubly linked list is a type of linked list where each node has a reference to both its previous node and its next node.

Here is an example implementation of a doubly linked list using Ruby:

class Node
  attr_accessor :value, :next_node, :prev_node
  
  def initialize(value, next_node = nil, prev_node = nil)
    @value = value
    @next_node = next_node
    @prev_node = prev_node
  end
end

class DoublyLinkedList
  include Enumerable
  
  def initialize
    @head = nil
    @tail = nil
  end
  
  def add(value)
    if @head.nil?
      @head = Node.new(value)
      @tail = @head
    else
      new_node = Node.new(value, nil, @tail)
      @tail.next_node = new_node
      @tail = new_node
    end
  end
  
  def each(&block)
    current = @head
    while current != nil
      yield current.value
      current = current.next_node
    end
  end
  
  def empty?
    @head.nil?
  end
  
  def first
    @head.value
  end
  
  def last
    @tail.value
  end
  
  def length
    count = 0
    current = @head
    while current != nil
      count += 1
      current = current.next_node
    end
    count
  end
  
  def remove(value)
    if @head == nil
      return
    end
    
    if @head.value == value
      @head = @head.next_node
      @head.prev_node = nil if @head
      return
    end
    
    current = @head
    while current.next_node != nil
      if current.next_node.value == value
        current.next_node = current.next_node.next_node
        current.next_node.prev_node = current if current.next_node
        return
      end
      current = current.next_node
    end
  end
  
  def reverse
    current = @head
    while current != nil
      temp_node = current.next_node
      current.next_node = current.prev_node
      current.prev_node = temp_node
      current = temp_node
    end
    temp_node = @head
    @head = @tail
    @tail = temp_node
  end
  
  def [](index)
    count = 0
    current = @head
    while current != nil
      if count == index
        return current.value
      end
      count += 1
      current = current.next_node
    end
    nil
  end
end

The DoublyLinkedList class is similar to the LinkedList class, except that each node has an additional reference to its previous node. The add and remove methods have been modified to handle the previous node reference, and the reverse method has been updated to swap the previous and next node references.

Here is how you can use the DoublyLinkedList class:

# create a new doubly linked list
list = DoublyLinkedList.new

# add elements to the list
list.add(1)
list.add(2)
list.add(3)

# print the elements in the list
list.each do |value|
  puts value
end

# check if the list is empty
puts "Is the list empty? #{list.empty?}"

# get the first and last elements in the list
puts "First element: #{list.first}"

puts "Last element: #{list.last}"

# get the length of the list
puts "Length of list: #{list.length}"

# remove an element from the list
list.remove(2)

# print the elements in the list again
list.each do |value|
    puts value
end

# reverse the order of the elements in the list
list.reverse

# print the elements in the list again
list.each do |value|
    puts value
end