Welcome! In this lesson, we'll expand on our linked list implementation using Ruby. As you know by now, linked lists in Ruby require the manual creation and management of nodes and pointers. You'll learn how to build and improve on linked lists by defining your own classes and methods, providing an efficient way to perform data operations.

In Ruby, a doubly-linked list can be constructed manually by defining a Node class, where each node points to the next and previous nodes, facilitating bidirectional traversal. This structure allows flexible data management but requires careful handling of node connections to avoid complexity and errors.

To construct a linked list in Ruby, we define our own Node and LinkedList classes to manage the nodes and their connections:

class Node
  attr_accessor :value, :next, :prev

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

class LinkedList
  attr_accessor :head

  def initialize
    @head = nil
  end
end

# Create a linked list
students = LinkedList.new

In this code, we've set up a LinkedList with a head that starts as nil. Next, we'll add methods for connecting nodes and managing this list.

Here are some custom methods we can define in Ruby to manipulate our linked list:

• add_last(value): Appends an element to the end of the list.
• add_first(value): Inserts an element at the beginning of the list.
• remove_first: Removes the first element of the list.
• find(value): Searches for the first occurrence of the specified value.

An example implementation might look like this:

class LinkedList
  # other methods...
  
  def add_last(value)
    new_node = Node.new(value)
    if @head.nil?
      @head = new_node
    else
      current = @head
      current = current.next until current.next.nil?
      current.next = new_node
      new_node.prev = current
    end
  end

  def add_first(value)
    new_node = Node.new(value)
    new_node.next = @head
    @head.prev = new_node unless @head.nil?
    @head = new_node
  end

  def remove_first
    return if @head.nil?
    @head = @head.next
    @head.prev = nil unless @head.nil?
  end

  def find(value)
    current = @head
    until current.nil?
      return current if current.value == value
      current = current.next
    end
    nil
  end
end

To traverse a linked list in Ruby, you can use a loop to manually follow each node's connections:

def traverse
  current = @head
  until current.nil?
    puts current.value
    current = current.next
  end
end

# Example usage
students.add_last("John")
students.add_last("Alice")
students.traverse
# Output:
# John
# Alice

We can implement more complex linked list operations in Ruby, such as:

• add_after(node, value): Inserts a new node after the specified existing node.
• add_before(node, value): Inserts a new node before the specified existing node.
• clear: Removes all elements from the list.
• contains(value): Checks if the list contains the specified element.

Here's how these methods would look:

class LinkedList
  # other methods...

  def add_after(node, value)
    return if node.nil?
    new_node = Node.new(value)
    new_node.next = node.next
    node.next.prev = new_node unless node.next.nil?
    node.next = new_node
    new_node.prev = node
  end

  def add_before(node, value)
    return if node.nil? || node.prev.nil?
    new_node = Node.new(value)
    new_node.prev = node.prev
    node.prev.next = new_node
    new_node.next = node
    node.prev = new_node
  end

  def clear
    @head = nil
  end

  def contains(value)
    !find(value).nil?
  end
end

Congratulations! You've learned how to create and manipulate linked lists from scratch in Ruby. We covered implementing nodes, managing connections, and performing operations such as adding, removing, and traversing elements. Now, practice creating your own linked list implementations and building functionality to reinforce your understanding and prepare for more complex data structure challenges in Ruby. Happy coding!