Expanding On Custom Linked Lists in Ruby

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