代码之家 › 专栏 › 技术社区 › control plane

ruby中链表上size调用的时间复杂性

time-complexity linked-list data-structures algorithm ruby

control plane · 技术社区 · 2 年前

我是ruby的新手。请原谅我问了这么简单的问题。

虽然我知道 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) Java 实现 answer ,看起来 Java语言 跟踪 linked list 使得大小调用的时间复杂性为 O(1) 。

如何使用 ruby ?

2 回复 | 直到 2 年前

spickermann 2 年前

你的 size 实现的复杂性 O(n) 因为它在计算 大小 。

相反,您可以存储当前 大小 在实例变量中,并在添加新节点时递增该变量。当前大小存储在实例变量中。这个 大小 方法将在中返回 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习惯用法。

wayne 2 年前

添加 attr_accessor :size 到您的 Class Linkedlist 和操纵 size 在您的 add 方法如下:

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

推荐文章

Matthew Thomas · 在每个决策中给出多个选择的所有可能的决策路径/结果

1 年前

feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点

1 年前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

1 年前

Matvey Androsyuk · 如何使用React在树结构中呈现我的组件,就像IDE中的默认文件结构一样

1 年前

Pengcheng · 这个简单的递归函数的输出是什么?你能详细解释一下吗?

1 年前

b39b332d · 使用C++标准库实现高效间隔存储

1 年前

Paul C · 在维基百科上,将二叉搜索树转换为排序链表的算法是否存在错误?

1 年前

ABGR · 二叉树的直径——当最长路径不通过根时的失败案例

1 年前

SHUBHAM KUMAR · 这两个是否完全相同-->“下限(股份有限公司rbegin(),股份有限公司rend(),i,更大<int>())”和“下限(dec.begin(

1 年前

EpicAshman · 数独棋盘程序中同一列和同一行出现两次的数字

1 年前