ruby - 用 ruby​​ 编写的链表

Question

我正在准备技术面试，将被要求用 ruby​​ 编写链表的算法。我完全理解链表，但一直在努力编写代码。有人可以告诉我这是怎么做到的吗？我在下面开始..

class Node
  def initialize(item)
    @item = item
    @next = nil 
  end
end

Answer 1

你几乎做到了，真的。如果你有足够的勇气向你的面试官展示，我可以给你非常老派的、类似 Lisp 的实现。在这种方法中，列表是一对(双元素对)，第一个元素包含该元素，第二个元素包含另一对，依此类推。最后一对将 nil 作为第二个元素。下面是 Ruby 列表的完整实现:

class Pair
  attr_reader :car, :cdr
  def initialize(car, cdr=nil)
    @car = car
    @cdr = cdr
  end
end

要构建列表，只需使用大量括号，就像在旧的、优秀的 Lisp 中一样:

list = Pair.new(1, Pair.new(2, Pair.new(3)))

现在，世界是你的。您可以使用简单的递归对列表做任何您想做的事情。下面是一个递归 inspect 的例子:

class Pair
  def inspect
    if cdr.nil?
      car.inspect
    else
      "#{car.inspect}, #{cdr.inspect}"
    end
  end
end

pry(main)> list = Pair.new(1, Pair.new(2, Pair.new(3)))
=> 1, 2, 3

正如您在评论中提到的，您想要搜索列表。这是为此的代码:

class Pair
  def find(index)
    find_ index, 0
  end
  def find_(index, i)
    if index == i
      car
    else
      cdr.find_ index, i+1
    end
  end
end

pry(main)> list.find 2
=> 3