ruby - 没有扩展数组的 ruby​​ 中最好的链表？

Question

在不使用/扩展 Array 类的情况下，在 Ruby 中实现链表的最佳方法是什么？这是我过去使用过的一个实现，但它似乎不是最好的实现方式:

class Node

    attr_accessor :value, :next_node

    def initialize(value = nil)
        @value = value
    end

    def to_s
        @value
    end

end

class SinglyLinkedList

    attr_accessor :head

    def initialize(first_value=nil)
        @head = Node.new(first_value) if first_value
    end

    def add(value)
        #adds a new node to the list, amakes it the new head and links it to the former head
        new_node = Node.new(value)
        new_node.next_node = @head

        @head = new_node
    end

    def remove
        @head = @head.next_node
    end
end

Answer 1

我假设你是为了自学而实现这个，否则它没有任何意义。只需使用 Array，即 ruby​​ 的列表实现。

在我看来，你应该用 C 编写这些练习，因为实现链表的全部意义在于更接近机器并更好地理解它是如何工作的。 C 是完成此任务的更好工具，了解计算机的工作原理。

这是大学里教经典链表的方式:O(n) 插入，O(n) 搜索，O(n ) 删除。之后，大多数书籍都讨论了对其的改进。

我在脑海中写下了，根本没有对其进行测试，但这应该会给你一个想法，并希望这是一个练习来纠正你发现的任何错误。 (更新:@Nitesh 发现了一个拼写错误，并修复了它。希望它现在有一些测试)。

class Node
    attr_accessor :value, :next

    def initialize(value = nil)
        @value = value
    end

    def to_s
        @value
    end
end

class SinglyLinkedList

    attr_accessor :head

    def initialize(first_value=nil)
      @head = Node.new(first_value) if first_value
    end

    def add(value)
      if head.nil?
        head = Node.new(value)
      else
        current_node = @head
        while current_node.next
          current_node = current_node.next
        end
        current_node.next = Node.new(value)
      end
    end

    def find(value)
      current_node = head
      while current_node != nil
        return current_node if current_node.value == value
        current_node = current_node.next
      end
      nil
    end

    def remove(value)
      if head.value == value
        head = head.next
      else
        current_node = head.next
        prev_node = head
        while current_node
          if current_node.value == value
            prev_node.next = current_node.next
            return true
          end
          prev_node = current_node
          current_node = current_node.next
        end
        nil
      end
    end
end