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:

Ruby
Copy to clipboard
1class Node
2  attr_accessor :value, :next, :prev
3
4  def initialize(value)
5    @value = value
6    @next = nil
7    @prev = nil
8  end
9end
10
11class LinkedList
12  attr_accessor :head
13
14  def initialize
15    @head = nil
16  end
17end
18
19# Create a linked list
20students = 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:

Ruby
Copy to clipboard
1class LinkedList
2  # other methods...
3  
4  def add_last(value)
5    new_node = Node.new(value)
6    if @head.nil?
7      @head = new_node
8    else
9      current = @head
10      current = current.next until current.next.nil?
11      current.next = new_node
12      new_node.prev = current
13    end
14  end
15
16  def add_first(value)
17    new_node = Node.new(value)
18    new_node.next = @head
19    @head.prev = new_node unless @head.nil?
20    @head = new_node
21  end
22
23  def remove_first
24    return if @head.nil?
25    @head = @head.next
26    @head.prev = nil unless @head.nil?
27  end
28
29  def find(value)
30    current = @head
31    until current.nil?
32      return current if current.value == value
33      current = current.next
34    end
35    nil
36  end
37end

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

Ruby
Copy to clipboard
1def traverse
2  current = @head
3  until current.nil?
4    puts current.value
5    current = current.next
6  end
7end
8
9# Example usage
10students.add_last("John")
11students.add_last("Alice")
12students.traverse
13# Output:
14# John
15# 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:

Ruby
Copy to clipboard
1class LinkedList
2  # other methods...
3
4  def add_after(node, value)
5    return if node.nil?
6    new_node = Node.new(value)
7    new_node.next = node.next
8    node.next.prev = new_node unless node.next.nil?
9    node.next = new_node
10    new_node.prev = node
11  end
12
13  def add_before(node, value)
14    return if node.nil? || node.prev.nil?
15    new_node = Node.new(value)
16    new_node.prev = node.prev
17    node.prev.next = new_node
18    new_node.next = node
19    node.prev = new_node
20  end
21
22  def clear
23    @head = nil
24  end
25
26  def contains(value)
27    !find(value).nil?
28  end
29end

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!