Вставка значения в связанный список в Ruby

Question

У меня проблемы с использованием связанного списка в Ruby. В методе insert_node, если head не равно nil, то current_node.next = _node получит значение, которое будет вставлено в конец связанного списка. Я не понимаю, как head обновляется с добавленной стоимостью в конце связанного списка. Мне кажется, что current_node является копией head, а затем после цикла до current_node.next получает значение для вставки. Просто взглянув на это, я подумал, что head будет таким же предыдущим связанным списком без добавленной стоимости, предполагая, что заголовок не равен 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

Функция insert здесь работает, потому что current_node.next = _node является постоянной модификацией объекта в списке, на который указывает head. После этого вызова, даже если current_node собирает мусор (это просто временный указатель), у узла, на который он указывал в строке current_node.next = _node, свойство .next постоянно изменено.

Вот схема добавления нового узла 3 в список 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 

Кстати, этот insert метод демонстрирует плохую конструкцию; каждая вставка представляет собой O (n) линейную операцию времени, требующую обхода всего списка. Улучшенный дизайн класса LinkedList предлагает указатель tail, позволяющий вставлять O (1) с постоянным временем в конец списка. С другой стороны, класс может предложить add_front() без указателя хвоста, который установит new_head.next = old_head и head = new_head.