用ruby编写的链表

Question

我正在准备一个技术面试，面试将要求我用ruby编写一个链表的算法。我完全理解链表，但一直在努力编写代码。谁能告诉我这是怎么做的?我从下面开始…

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

Answer 1

你差一点就成功了，真的。我可以给你一个非常老派的，类似lisp的实现，如果你有足够的勇气向你的面试官展示它。在这种方法中，list是一对(两个元素对)，其中第一个元素包含元素，第二个元素包含另一个元素对，以此类推。最后一对的第二元素是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

Answer 2

这是列表(和布尔值)的标准教会编码:

True   = ->(iff, _) { iff }
False  = ->(_, els) { els }
Pair   = ->(first, rest) { -> x { x.(first, rest) }}
First  = -> list { list.(True ) }
Rest   = -> list { list.(False) }
List   = Pair.(1, Pair.(2, nil))
First.(Rest.(List))
# => 2

当然，这不是你在Ruby中实际编写的内容，但它非常简单，并演示了对编程最重要原则之一的理解:代码即数据，数据即代码。

下面是一个更现实的面向对象的列表编码:

class List
  include Enumerable
  def self.[](*els) els.reverse_each.inject(Empty, &:cons) end
  def cons(el) Pair[el, self] end
  def prepend(prefix)
    case
    when        empty? then prefix
    when prefix.empty? then self
    else prepend(prefix.rest).cons(prefix.first)
    end
  end
  def to_s; "List[#{map(&:to_s).join(', ')}]" end
  def inspect; "List[#{map(&:inspect).join(', ')}]" end
  def each; return enum_for(__method__) unless block_given? end
  class << Empty = new
    def empty?; true end
    alias_method :inspect, def to_s; 'Empty' end
    freeze
  end
  Empty.freeze
  class Pair < self
    def initialize(first, rest=Empty)
      self.first, self.rest = first, rest
      freeze
    end
    def empty?; false end
    def each(&blk)
      return super unless block_given?
      yield first
      rest.each(&blk)
    end
    private
    attr_writer :first, :rest
    protected
    attr_reader :first, :rest
    class << self; alias_method :[], :new end
    freeze
  end
  freeze
end

请注意，代码中绝对没有条件和循环。对于面向对象代码来说，这总是一个好兆头:无论如何，多态方法调用比条件调用更强大，通常情况下，根本不需要条件。

一些例子:

list1 = List::Pair[1, List::Pair[2, List::Pair[3, List::Empty]]]
# => List[1, 2, 3]
list2 = List::Empty.cons(6).cons(5).cons(4)
# => List[4, 5, 6]
list3 = List[7, 8, 9]
# => List[7, 8, 9]
list4 = list3.prepend(list2).prepend(list1)
# => List[1, 2, 3, 4, 5, 6, 7, 8, 9]
list4.partition(&:odd?)
# => [[1, 3, 5, 7, 9], [2, 4, 6, 8]]

不幸的是，这种面向对象的编码将为更大的列表吹堆栈(在我的系统上List[*(1..9338)].each {}仍然工作，但9339不)，即使each是尾部调用本身，因此应该在O(1)堆栈空间中运行。正如Guy L. Steele多次指出的那样，OO语言必须支持适当的尾部调用，否则您需要打破OO以避免破坏堆栈。(prepend没有为尾部调用编码，但可以这样重写)