用ruby写的链表
我正在准备技术面试，并将被要求为ruby中的链表编写算法。 我完全理解链接列表，但一直在努力编写代码。 有人能告诉我这是怎么做到的吗？ 我在下面开始..
class Node def initialize(item) @item = item @next = nil end end 你差点做到了，真的。 如果你足够勇敢地向你的面试官展示，我可以给你非常老派，类似Lisp的实施。 在这种方法中，list是一对（两个元素touple），其中第一个元素包含元素，第二个元素包含另一对等，最后一对将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
这是列表（和布尔人）的标准教会编码：
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不是为尾调用编码的，但可以用那种方式重写。）