如何在Ruby中实现时间复杂度为O(1)的LinkedList size方法？

核心思路和Java一致：在LinkedList类中维护一个实例变量记录当前链表长度，每次添加或删除元素时同步更新这个变量，size方法直接返回该变量即可，时间复杂度就能降到O(1)。

具体修改步骤如下：

1. 初始化长度变量 #

在Linkedlist类的构造方法里初始化@size为0，同时显式初始化@head为nil（让代码逻辑更清晰）：

class Linkedlist
  def initialize
    @head = nil
    @size = 0
  end

  # 原empty?方法可以简化，依赖@size判断更直接
  def empty?
    @size == 0
  end
end

2. 简化size方法 #

直接返回维护的@size变量，无需再遍历链表计数：

def size
  @size
end

3. 更新add方法（及其他修改元素数量的方法） #

在添加元素时同步把@size加1，同时修正你原add方法里的两个小问题：

• 方法需要接收data参数
• 非空链表时要初始化current_node为@head

修改后的add方法：

def add(data)
  if empty?
    @head = Node.new(data)
  else
    current_node = @head
    while current_node.next != nil
      current_node = current_node.next
    end
    current_node.next = Node.new(data)
  end
  @size += 1 # 每次添加元素后更新长度
end

4. 后续扩展注意事项 #

如果以后实现删除元素的方法（比如remove），记得在成功删除元素时把@size减1，这样长度才能保持准确。

完整示例代码：

class Node
  attr_accessor :data, :next
  def initialize(data, next_node = nil)   
    @data = data
    @next = next_node
  end
end

class Linkedlist
  def initialize
    @head = nil
    @size = 0
  end

  def empty?
    @size == 0
  end

  def size
    @size
  end
        
  def add(data)
    if empty?
      @head = Node.new(data)
    else
      current_node = @head
      while current_node.next != nil
        current_node = current_node.next
      end
      current_node.next = Node.new(data)
    end
    @size += 1
  end
end

这样size方法就能在O(1)时间内返回结果，和Java的LinkedList实现思路完全一致。

内容的提问来源于stack exchange，提问作者control plane