ruby - 将值插入Ruby中的链表

我在ruby中使用链表时遇到问题。在方法insert_node中，如果head不是nil，则current_node.next = _node将得到要插入链表末尾的值。我不明白如何用链接列表末尾的值来更新head。在我看来current_node是head的副本，然后在until循环current_node.next获得要插入的值之后。仅仅通过观察，我认为如果head不是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)

最佳答案

这里的insert函数起作用，因为current_node.next = _node是对列表中由head指向的对象的永久性修改。在这个调用之后，即使current_node被垃圾回收（它只是一个临时指针），它在current_node.next = _node行中指向的节点的.next属性也被永久修改。
下面是将新节点添加到列表中的示意图：

(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

顺便说一下，这个3方法的设计很差；每次插入都是一个o（n）线性时间操作，需要遍历整个列表。一个改进的1->2->nil类设计将提供一个insert指针，允许o（1）常量时间插入到列表的末尾。或者，类可以提供不带尾部指针的LinkedList，尾部指针可以设置tail和add_front()。

关于ruby - 将值插入Ruby中的链表，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/54262086/