Implementing a Singly Linked List in Ruby

,

A singly linked list stores each value in a node that points to the next node. It provides cheap insertion at the head, but random access is O(n) because nodes must be traversed in order.

Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
class LinkedList
  Node = Struct.new(:value, :next_node)

  include Enumerable

  attr_reader :size

  def initialize
    @head = nil
    @tail = nil
    @size = 0
  end

  def prepend(value)
    @head = Node.new(value, @head)
    @tail ||= @head
    @size += 1
    self
  end

  def append(value)
    node = Node.new(value)

    if @tail
      @tail.next_node = node
    else
      @head = node
    end

    @tail = node
    @size += 1
    self
  end

  def delete_at(index)
    raise IndexError, "index out of bounds" unless index.between?(0, size - 1)

    if index.zero?
      removed = @head
      @head = @head.next_node
      @tail = nil if size == 1
    else
      previous = node_at(index - 1)
      removed = previous.next_node
      previous.next_node = removed.next_node
      @tail = previous if index == size - 1
    end

    @size -= 1
    removed.value
  end

  def reverse!
    previous = nil
    current = @head
    @tail = @head

    while current
      following = current.next_node
      current.next_node = previous
      previous = current
      current = following
    end

    @head = previous
    self
  end

  def cycle?
    slow = @head
    fast = @head

    while fast&.next_node
      slow = slow.next_node
      fast = fast.next_node.next_node
      return true if slow.equal?(fast)
    end

    false
  end

  def each
    return enum_for(__method__) unless block_given?

    current = @head
    while current
      yield current.value
      current = current.next_node
    end
  end

  private

  def node_at(index)
    current = @head
    index.times { current = current.next_node }
    current
  end
end

Usage:

1
2
3
4
5
6
list = LinkedList.new
list.append(1).append(2).prepend(0)
list.to_a       # => [0, 1, 2]
list.delete_at(1) # => 1
list.reverse!
list.to_a       # => [2, 0]

What the old implementation got wrong

  • Deleting the head did not update @head correctly.
  • Reversing by swapping values was not actually reversing links.
  • Cycle detection returned false even when it found a repeated node.
  • Appending traversed the entire list despite already tracking length; keeping a tail makes append O(1).

The pointer operations are the lesson. If values are merely swapped, the list topology has learned nothing and neither have we.

Complexity

Operation Complexity
Prepend O(1)
Append with tail O(1)
Access/delete by index O(n)
Reverse O(n)
Cycle detection O(n) time, O(1) space