Linked List Operations

Lesson Overview

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.

Understanding Linked Lists in Ruby

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.

Linked List Definition

To work with linked lists, we first need to define a ListNode class, which represents a single node in the linked list. Ruby class ListNode attr_accessor :value, :next def initialize(value = 0, next_node = nil) @value = value # Stores the data of the node @next = next_node # Points to the next node in the linked list; default is nil end end # Initializing a linked list head = 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 .

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Task Example: Reversing a Linked List

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

class ListNode
  attr_accessor :val, :next

  def initialize(val = 0, next_node = nil)
    @val = val
    @next = next_node
  end
end

def reverse_linked_list(head)
  prev = nil
  current = head
  while current
    next_node = current.next       # Save the next node to keep track
    current.next = prev            # Reverse the current node's pointer
    prev = current                 # Move prev to the current node
    current = next_node            # Proceed to the next node in the list
  end
  prev                             # prev becomes the new head of the reversed list
end

# Test
head = ListNode.new(1, ListNode.new(2, ListNode.new(3, ListNode.new(4, ListNode.new(5)))))
reversed_head = reverse_linked_list(head)
while reversed_head
  print "#{reversed_head.val} "  # Output: 5 4 3 2 1
  reversed_head = reversed_head.next
end

class ListNode
  attr_accessor :val, :next

  def initialize(val = 0, next_node = nil)
    @val = val
    @next = next_node
  end
end

def reverse_linked_list(head)
  prev = nil
  current = head
  while current
    next_node = current.next       # Save the next node to keep track
    current.next = prev            # Reverse the current node's pointer
    prev = current                 # Move prev to the current node
    current = next_node            # Proceed to the next node in the list
  end
  prev                             # prev becomes the new head of the reversed list
end

# Test
head = ListNode.new(1, ListNode.new(2, ListNode.new(3, ListNode.new(4, ListNode.new(5)))))
reversed_head = reverse_linked_list(head)
while reversed_head
  print "#{reversed_head.val} "  # Output: 5 4 3 2 1
  reversed_head = reversed_head.next
end

Here's how the algorithm operates:

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.
Iterate Through the List:
- while current: Continue looping until all nodes are processed (current becomes nil).
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.
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.