在Ruby中实现链表而不使用/扩展Array类的最佳方法是什么？这是我过去使用过的一个实现，但它似乎不是最好的方法：
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
我认为你是为了自学而实现的，否则就没有任何意义。只需使用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
我最近遇到了一个有趣的链表实现（不确定意外发生在哪里），Node类实现了插入和删除方法。以下是用于双链表的Node类，但同样的原则也适用于单链表。
class Node
protected
attr_writer :prev, :next
public
attr_reader :value, :prev, :next
def initialize(value)
@value = value
end
def remove
@prev.next = @next if @prev
@next.prev = @prev if @next
@next = @prev = nil
end
def insert_after(node)
remove
@next = node.next
@next.prev = self if @next
@prev = node
node.next = self
end
end
我觉得这个实现很有趣，因为我发现它非常通用。只需要一个Node就可以开始构建一个列表并对其进行操作
head = Node.new(1)
middle = Node.new(2)
middle.insert_after(head)
tail = Node.new(3)
tail.insert_after(middle)
middle.remove
在这个实现之上，您可以构建一个更高级的API，它非常容易理解。以下是LinkedList或Deque的更完整版本。列表本身是Node的子类，并链接到列表的头部和尾部。
class ListNode < Node
protected :remove # prevent incorrect access to Node methods
def initialize
@next = @prev = self
end
def head
@next unless @next == self
end
def tail
@prev unless @prev == self
end
def add_to_head(node)
node.insert_after(self)
end
def add_to_tail(node)
node.insert_after(self.prev)
end
def each(&block)
return enum_for(:each) unless block_given?
node = @next
while node != self
yield node
node = node.next
end
end
def to_a
each.collect {|node| node.value }
end
end
以下是它在实践中的使用方法：
# create a new list
list = ListNode.new
# add some items to the head or tail
list.add_to_head(Node.new('Hello'))
list.add_to_tail(Node.new('World'))
list.to_a # => ["Hello", "World"]
# remove items from the head
list.head.remove
list.to_a # => ["World"]
list.head == list.tail # => true
# remove items from the tail
list.tail.remove
list.to_a # => []
更好的是each方法，它允许我们使用任何可枚举函数来搜索和迭代节点：
list = ListNode.new
list.add_to_head(Node.new(1))
list.add_to_head(Node.new(2))
list.add_to_head(Node.new(3))
list.add_to_head(Node.new(4))
# list each value
list.each {|node| puts node.value }
# select all nodes with values greater than 2
list.each.select {|node| node.value > 2 }
# find the first node with a value of 4
list.each.find {|node| node.value == 4 }