ruby - Ruby 单链表实现

Question

我想编写一个exist函数，如果一个值作为链表中的节点存在，则返回 true，否则返回 false。到目前为止，我有以下代码始终返回 true。任何帮助表示赞赏：

class SinglyLinkedList
  attr_accessor :head, :tail, :count

  def initialize
    @head = nil
    @tail = nil
    @count = 0
  end

  def insert_front(value)
    node = Node.new(value)
    if @head.nil?
    @head = node
    @tail = node
    else
      node.next = @head
      @head = node
    end 
    @count +=1
  end

  def print_first()
    puts head.data
  end

  def print_last()
    puts tail.data
  end

  def exist(value)
    walker = @head
    until walker.nil? 
      if walker.data == value
        return true
      end
      walker = walker.next
    end   
      false
  end

  def size()
    count
  end

end

class Node
  attr_accessor :data, :next

  def initialize(data)
    @next = nil 
    @data = data
  end 
end

这是我的测试代码：

list = SinglyLinkedList.new
list.insert_front(1)
list.exist(2)

返回true。

Answer 1

在解决方案之前，只需考虑单链表只能通过append列表插入。您尝试以错误的方向插入节点。您的代码的问题是您使用保留的方法名称next，只需重构您的代码并编写简单的代码：

class SinglyLinkedList
  class Node
    attr_reader :value
    attr_accessor :pointer

    def initialize(value, pointer = nil)
      @value = value
      @pointer = pointer
      @count = 0
    end
  end

  attr_reader :head, :tail

  def initialize
    @head = nil
    @tail = nil
  end

  def insert(value)
    node = Node.new(value)
    @count += 1

    if @head.nil?
      @head = node
      @tail = node
    else
      @tail.pointer = node
      @tail = node
    end
  end

  def inspect
    return [] unless @head

    values = []
    node = @head

    begin
      values << node.value
      node = node.pointer
    end while node != nil

    values
  end

  def exists?(value)
    return false unless @head

    node = @head

    begin
      node = node.pointer
    end while node != nil && node.value != value

    node.nil?
  end
end