用ruby编写的链表 [英] Linked List written in ruby

问题描述

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

I'm preparing for a technical interview and will be asked to write the algorithm for a linked list in ruby. I understand linked lists completely, but have struggled writing the code. Can someone show me how this is done? I started it below..

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

推荐答案

您确实做到了。如果您有足够的勇气向面试官展示，我可以给您一个非常古老的，类似于Lisp的实现。在这种方法中，list是一对（touple有两个元素），第一个元素包含该元素，第二个元素包含另一对，依此类推，等等。最后一对具有 nil 作为第二个要素。这是Ruby中列表的完整实现：

You almost did it, really. I can give you very old-school, Lisp-like implementation, if you are brave enough to show it to your interviewer. In this approach, list is a pair (two elements touple), which first element contains the element, and second contains another pair, etc, etc. The last pair have nil as a second element. And here is the whole implementation of the list in Ruby:

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

要构建列表，只需使用很多括号即可，例如在老式的Lisp中：

To construct the list, just use a lot of parenthesis, like in old, good Lisp:

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

现在，世界在您的手中。您可以使用简单的递归对列表进行任何操作。以下是递归检查的示例：

Now, the world is yours. You can do whatever you want with the list, using simple recursion. Here is an example of recursive 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

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

As you mentioned in a comment, you want to search the list. Here is the code for this:

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

这篇关于用ruby编写的链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！