Ruby中链表上size调用的时间复杂度

ztigrdn8 于 2023-06-29 发布在 Ruby

关注(0)|答案(2)|浏览(130)

我是个新手。请原谅我问这么简单的问题。
虽然我知道Ruby不包含LinkedList类，所以我们需要创建自己的，因此我创建了自己的类，如下所示：

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

class Linkedlist

    def empty?
        @head == nil  
    end

    def size
        count = 0
        if self.empty?
            return count
        else
            current_node = @head
            while current_node.next !=nil
                count += 1
                current_node = current_node.next
            end
            return count
        end
    end
        
    ...
    ...

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

我对size调用的实现清楚地显示了O(n)的时间复杂度。当查看这个answer中的Java实现时，似乎Java跟踪linked list的大小，使得大小调用的时间复杂度为O(1)。
如何使用ruby实现这一点？

ruby

来源：https://stackoverflow.com/questions/76546255/time-complexity-for-size-call-on-a-linked-list-in-ruby

2条答案

按热度按时间

g0czyy6m1#

您的size实现具有O(n)的复杂性，因为它在计算size时迭代了整个列表。
相反，您可以将当前size存储在一个示例变量中，并在添加新节点时递增该变量。当前大小存储在示例变量中。size方法将在O(1)中返回。

class LinkedList
  attr_reader :size

  def initialize
    @size = 0
  end

  def add(data)
    if empty?
      @head = Node.new(data)
    else
      current_node = head
      current_node = current_node.next while current_node.next

      current_node.next = Node.new(data)
    end

    @size += 1
  end

  def empty?
    size.zero?
  end
    
  private

  attr_reader :head
end

list = LinkedList.new

list.add(:a)
list.add(:b)
list.add(:c)

list.size
#=> 3

当你实现一个remove方法时，该方法需要递减@size变量。
注意：我重新格式化并重写了一些代码，以遵循常见的Ruby习惯用法。

赞(0）回复(0）举报 2023-06-29

yfwxisqw2#

将attr_accessor :size添加到Class Linkedlist中，并在add方法中操作size，如下所示：

class Linkedlist
    attr_accessor :size

    def add
        if self.empty?
            @head = Node.new(data)
        else
            while current_node.next != nil
                current_node = current_node.next
            end
            current_node.next = Node.new(data)
        end
        modify_size("add")
    end

    def remove
        .
        . 
        # after removing node
        modify_size("remove")
        return removed_node
    end

    def modify_size(arg)
        case arg
        when 'add'
            self.size += 1
        when 'remove'
            self.size -= 1
        else
        end
    end

end

l1 = Linkedlist.new.add(1)
puts l1.size

赞(0）回复(0）举报 2023-06-29

我来回答

Ruby中链表上size调用的时间复杂度

2条答案

相关问题

热门标签

最新问答