Inserting a value into a linked list in Ruby

Question

I am having trouble using linked list in Ruby. In the method insert_node, if head is not nil then current_node.next = _node will get the value to be inserted at the end of the linked list. I don't understand how head is being updated with the value added to the end of the linked list. To me it seems that current_node is a copy of head and then after the until loop current_node.next gets the value to be inserted. Just by looking at it I thought that head will be the same previous linked list without the added value assuming head is not nil.

class Node 
  attr_accessor :data, :next

  def initialize(data)
    @data = data 
    @next = nil 
  end
end

class List

  def insert_node(head, value)
    _node = Node.new(value)

    if head.nil?
      return _node
    end

    current_node = head 
    until current_node.next.nil?
      current_node = current_node.next
    end

    current_node.next = _node
    head
  end

  def display(head)
    temp = head 
    while temp 
      print "#{temp.data} "
      temp = temp.next
    end
  end

end

obj = List.new
head = nil

head = obj.insert_node(head, 1)
head = obj.insert_node(head, 2)
obj.display(head)

Answer 1

The insert function here works because current_node.next = _node is a permanent modification to an object in the list that is pointed to by head. After this call, even though current_node is garbage collected (it's just a temporary pointer), the node that it was pointing to during the current_node.next = _node line has had its .next property permanently modified.

Here's a diagram of adding the new node 3 to the list 1->2->nil:

(before the `until` loop)

+---------+   +---------+
| data: 1 |   | data: 2 |   
| next: ----> | next: ----> [nil]
+---------+   +---------+
  ^    ^
  |    |
head  current_node 

(after the `until` loop; `current_node.next == nil`)
(and before `current_node.next = _node`)

+---------+   +---------+
| data: 1 |   | data: 2 |   
| next: ----> | next: ----> [nil]
+---------+   +---------+
     ^             ^
     |             |
   head        current_node 

(after `current_node.next = _node`)

+---------+   +---------+   +---------+
| data: 1 |   | data: 2 |   | data: 3 |   
| next: ----> | next: ----> | next: ----> [nil]
+---------+   +---------+   +---------+
     ^             ^
     |             |
   head        current_node 

Incidentally, this insert method exhibits poor design; every insertion is an O(n) linear time operation requiring traversal of the entire list. An improved LinkedList class design would offer a tail pointer, allowing O(1) constant time insertion to the end of the list. Alternately, the class could offer add_front() without a tail pointer, which would set new_head.next = old_head and head = new_head.