我在 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
属性永久修改。
这是添加新节点 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
.
关于ruby - 将值插入 Ruby 中的链表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54262086/