Welcome to our tutorial focusing on Linked List Operations in Ruby. Singly Linked Lists, or simply Linked Lists, are foundational data structures in computer science. They allow efficient data storage and access without requiring contiguous memory allocation. This unique feature sets linked lists apart from arrays, making them an essential tool in any programmer's toolkit.

It's important to note that Linked lists aren’t as commonly used in Ruby as arrays, thanks to the language’s robust array handling and built-in methods. However, linked lists offer advantages in certain scenarios, particularly when you need efficient insertion and deletion without shifting elements, which arrays would require. This makes linked lists a smart choice in tasks like implementing queues, stacks, or handling memory in lower-level systems.

While you may often reach for arrays in Ruby, gaining a solid understanding of linked lists broadens your toolkit and enhances your problem-solving skills, especially for technical interviews where linked lists frequently appear. Let’s dive into the fundamentals and practical operations to prepare you for these cases.arrays may not be optimal. Mastering linked lists also prepares you for technical interviews, where they frequently appear in problem-solving exercises.

To work with linked lists, we first need to define a ListNode class, which represents a single node in the linked list.

Ruby
Copy to clipboard
1class ListNode
2  attr_accessor :value, :next
3
4  def initialize(value = 0, next_node = nil)
5    @value = value     # Stores the data of the node
6    @next = next_node  # Points to the next node in the linked list; default is nil
7  end
8end
9
10# Initializing a linked list
11head = ListNode.new(1, ListNode.new(2, ListNode.new(3, ListNode.new(4, ListNode.new(5)))))

In this ListNode class:

• @value holds the data stored in the node.
• @next is a reference to the next node in the linked list. By default, it’s set to nil, indicating no further connection when a node is created.

A linked list is essentially a sequence of nodes, where each node contains data and a reference (or link) to the next node in line. In the example above, we have created a linked list where each node points to the next, forming the chain: 1 -> 2 -> 3 -> 4 -> 5, with the last node pointing to nil.

A common task when working with linked lists, particularly in interviews, is reversing the list. This operation involves rearranging each node’s next reference to point to the previous node, effectively reversing the order.

Let’s look at an example of reversing a linked list efficiently—it runs in ( O(n) ) time since we visit each node just once, and uses ( O(1) ) space because we reverse the list right in place.

Ruby
Copy to clipboard
1class ListNode
2  attr_accessor :val, :next
3
4  def initialize(val = 0, next_node = nil)
5    @val = val
6    @next = next_node
7  end
8end
9
10def reverse_linked_list(head)
11  prev = nil
12  current = head
13  while current
14    next_node = current.next       # Save the next node to keep track
15    current.next = prev            # Reverse the current node's pointer
16    prev = current                 # Move prev to the current node
17    current = next_node            # Proceed to the next node in the list
18  end
19  prev                             # prev becomes the new head of the reversed list
20end
21
22# Test
23head = ListNode.new(1, ListNode.new(2, ListNode.new(3, ListNode.new(4, ListNode.new(5)))))
24reversed_head = reverse_linked_list(head)
25while reversed_head
26  print "#{reversed_head.val} "  # Output: 5 4 3 2 1
27  reversed_head = reversed_head.next
28end

Here's how the algorithm operates:

1. Initialize Pointers:

   • prev = nil: Start with prev as nil since the new tail of the reversed list will point to nil.
   • current = head: Begin with current at the head of the original list.

2. Iterate Through the List:

   • while current: Continue looping until all nodes are processed (current becomes nil).

3. Inside the Loop:

   • next_node = current.next: Temporarily store the next node to prevent losing the reference after reversing.
   • current.next = prev: Redirect the next pointer of the current node to point to the previous node, effectively reversing the link.
   • prev = current: Move the prev pointer forward to the current node, setting it up for the next iteration.
   • current = next_node: Advance the current pointer to the next node in the original list.

4. Finalize the Reversed List:

   • After the loop, prev points to the new head of the reversed list. Returning prev gives you the head of the reversed linked list.

By following these steps, the linked list is reversed efficiently, ensuring that each node is visited only once and no extra space is used beyond a few pointers.

Take a moment to observe, analyze, and understand the problem and its solution. This approach will reinforce your understanding of linked list operations and their practical applications. By the end of this lesson, you’ll feel more comfortable tackling linked list tasks in technical interviews and other coding scenarios. Let’s move forward and dive into some hands-on exercises!