ruby - 将值插入 Ruby 中的链表

Question

我在 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)

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) 常数时间插入到列表的末尾。或者，类(class)可以提供 add_front()没有尾指针，这将设置 new_head.next = old_head和 head = new_head .