ruby - 在 Ruby 的链接列表中，带有索引的方法 add_at 无法正常工作

Question

我正在学习 Ruby，这个 Linked list 练习对我来说有点复杂，我进步了，但不确定我做错了什么：

class Node
  attr_accessor :value, :next_node
  alias_method :next, :next_node

  def initialize(value, next_node = nil)
    @value = value
    @next_node = next_node
  end

  def next
    @next_node
  end
end

class LinkedList
  attr_accessor :head, :tail

  def initialize
    @head = nil
    @tail = nil
  end

  def add(number)
    if @head.nil?
      new_node = Node.new(number)
      @head = new_node
      @tail = new_node
    else
      new_node = Node.new(number)
      @tail.next_node = new_node
      @tail = new_node
    end
  end

  def get(index)
    current = @head
    index.times do
      current = current.next_node
    end
    return current.value
  end

  def add_at(index, item)
    current = head
    (index - 1).times do
      raise "List not long enough" if current.nil?
      current = current.next_node
    end

    new_node = Node.new(item)    
    new_node.next_node = current.next_node   
    current.next_node = new_node  
  end
end

试图改变 Node 方法，但似乎这不是答案

对我来说一切似乎都很好，但是根据以下测试，数据没有在正确的位置排序：

list = LinkedList.new

list.add(3)
list.add(5)
list.add_at(1, 11)
list.add_at(0, 13)

puts list.get(#)

最后应该是 13,3,11,5

难道我做错了什么？

标签： ruby

Answer 1

插入到列表的开头（或结尾）时，您的LinkedList#add_at方法无法正常工作。

特别是，当调用 时list.add_at(0, 13)，会发生什么：

def add_at(index, item)
  current = head # Current is set to the "3" node
  (index - 1).times do # This never yields
    raise "List not long enough" if current.nil?
    current = current.next_node
  end

  new_node = Node.new(item) # Creates the "13" node
  new_node.next_node = current.next_node # "13" points to "11"
  current.next_node = new_node # "3" points to "13"
end

结果：不是3 --> 11 --> 5变成13 --> 3 --> 11 --> 5，而是变成了3 --> 13 --> 11 --> 5。

换句话说，调用的最终结果与调用list.add_at(0, 13)相同list.add_at(1, 13)。

我不想在这里为你规定一个单一的解决方案；关键要点应该是如何调试问题。例如，您可以尝试安装pry，添加binding.pry到方法中并逐步执行代码以重现我的摘要。这是以这种方式解决问题所需要的绝对重要的开发人员技能。

...但是话虽如此，这里有一个建议：重新使用现有方法来获取previousandnext节点；然后在必要时重新设置head/tail值（以及将新节点“插入”到列表中）：

def add_at(index, item)
  new_node = Node.new(item)

  previous_node = get(index-1)
  next_node = get(index)

  if previous_node
    previous_node.next_node = new_node
  else
    head = new_node
  end

  if next_node
    new_node.next_node = next_node
  else
    tail = new_node
  end
end