为什么对于ArrayList，get操作的运行时为O(1)，而对于LinkedList，运行时为O(N)？

文章/答案/技术大牛

发布

1回答

arraylist、linked-list、runtime、big-o

这两个运行时之间有什么区别，是如何实现的？如果我也能得到运行时的解释，那就太好了！

浏览 37提问于2020-09-12得票数 1

回答已采纳

1回答

在这种情况下，在O(N)表示法中需要一个常数吗？

java、algorithm、arraylist、linked-list、big-o

在这个中，作者说get(index)在ArrayList中是O(1)，而在LinkedList中是O(n/2)，因为它需要遍历直到那个条目。在ArrayList中使用恒定时间的get操作是有意义的，因为ArrayList可以访问所有索引。但是，我不理解LinkedList的O(n&#

浏览 3提问于2014-09-18得票数 1

回答已采纳

1回答

ArrayList和Linkedlist哪个更适合实现中位数算法？

java

我正在尝试用Java实现中位数算法。我想知道这两个列表实现中哪一个在列表遍历和比较方面成本更低？谢谢!

浏览 1提问于2012-08-23得票数 0

2回答

LinkedList --使用Iterator来"get()“来更快地迭代

java、collections、linked-list、iterator

请有人解释一下，在调用get(i)时，使用迭代器如何减少运行时间？

浏览 4提问于2017-04-10得票数 1

回答已采纳

4回答

迭代数组列表的时间复杂度

java、arrays、algorithm、arraylist、data-structures

在每次迭代中，我调用get()来获取一个元素，如果该元素通过了某个条件，就会使用add()将其添加到新的数组列表中List<Item> lessItems = new ArrayList<Item>(); ItemtoCheck = items.get(i);

浏览 1提问于2016-09-17得票数 7

1回答

为什么在这个树遍历中只有log(N)个递归调用？

java、recursion、arraylist、linked-list、binary-tree

list = lists.get(level); createLevelLinkedlist(root.left, lists, level+1);} ArrayList<LinkedList<TreeNode>> createLevelLinkedListcreateLevelLinkedlist(root, li

浏览 27提问于2019-06-23得票数 2

8回答

ArrayList诉LinkedList

java、data-structures、collections、arraylist、linked-list

我在跟踪一个，上面写着： add是O(1)摊销的</em

浏览 14提问于2011-05-01得票数 66

回答已采纳

2回答

在java中高效地在给定索引处添加ArrayList中的元素

java、performance、arraylist

我需要在索引i处的ArrayList中插入一个Person类型的元素(我自己定义的类我知道我可以使用。但是，有没有什么有效的方法可以做到这一点，因为在我的列表中，平均需要大约1.5ms(通过1000次插入收集的数据，然后进行平均)。

浏览 1提问于2013-06-17得票数 8

3回答

当将元素移到第一位置时，ArrayList与LinkedList复杂性

java、algorithm、arraylist、linked-list、complexity-theory

我想使用1 2 3 4或ArrayList来分析移动3 1 2 4 (整数列表)的过程。我所做的：arraylist.remove(2); // O(n) arraylist.add(0, aux); // O(n

浏览 2提问于2017-05-10得票数 1

回答已采纳

3回答

仅为添加(插入)操作优化的Java集合

java、list、arraylist、collections、linked-list

我唯一的两个期望是： ArrayList不是最佳的候选对象，因为当没有更多的空间时，内部数组会调整大小。您能提议为这些操作优化

浏览 1提问于2018-08-06得票数 0

4回答

这个代码是O(n)还是O(logn)？

java、big-o

它只检查for循环1/3n次，所以我猜它在技术上仍然是线性的？然而，我真的不明白为什么它不是O(logn)，因为很多时候，一个运行时间为O(logn)的代码最终会检查大约1/3n。O(logn)每次都会将选项除以2吗？for (int i = 0; i < n; i = i+3) a = a+i;

浏览 0提问于2014-03-19得票数 0

6回答

为什么链表删除和插入操作具有O(1)的复杂性？不是应该是O(n)吗？

java、data-structures、collections、linked-list、time-complexity

据说，LinkedList删除和添加操作的复杂性是O(1)的。如果是ArrayList，则是O(n)。大小为"M“的ArrayList的计算:如果我想在N个位置删除元素，那么我可以使用索引一次直接到N个位置(我不需要遍历直到N个索引)，然后我可以删除这个元素，直到此时复杂度是O(<e

浏览 5提问于2017-03-17得票数 23

回答已采纳

2回答

何时使用每个Java集合数据结构

java、data-structures

我看到有一吨的。它们都实现了List，因此它们几乎可以互换使用，但是我什么时候想要使用它们呢？就我个人而言，我坚持使用LinkedList，因为它是我“熟悉”的东西。我不是要求对每一个结构进行解释，但你能解释一些更常见的结构并给出它们的用途，以及比较和对比"Vector-like“结构的用法吗？

浏览 4提问于2014-03-03得票数 0

4回答

用Big符号理解比较

algorithms、linked-list

所以我认为这是一个伟大的comment.But，它让我的头同时旋转。有人能解释一下这句话吗？评论说：如果不考虑常数因素，就不能直接比较大O值。对于小列表(而且大多数列表都很小)，ArrayList的O(N)比LinkedList的O(1)更快。

浏览 0提问于2012-07-19得票数 5

回答已采纳

2回答

如果由ArrayList和LinkedList实现，下面的代码运行的是什么？

java、list、arraylist、linked-list

for (int i =0; i < n; i++){ } 我在想for循环将采用o(n)，但我不清楚如果使用ArrayList和LinkedList，add(j，t)之间有什么区别。

浏览 6提问于2013-11-03得票数 1

回答已采纳

2回答

为什么二进制堆作为数组比树更好？

tree、binary-tree、heap、big-o

当创建二进制最大堆时，为什么最好将其实现为基于数组的堆，而不是基于树的堆(基于树的，每个节点也有指向其父节点的指针)？在运行时分析、内存使用、性能方面.对于二进制最大堆，运行时间为：对于树的<

浏览 22提问于2013-02-05得票数 19

2回答

pop、push和multipop复杂性

data-structures、time-complexity

我对计算pop和push在数据结构中的成本感到有点困惑。1)它说，push(x)：像往常一样实现，Θ(1)时间3)这是最令人困惑的部分。从空开始，执行m次操作。总时间是多少？至多m次推送，m次弹出: t

浏览 3提问于2016-11-21得票数 0

1回答

初始化数组和链表的一段代码的大O表示法

time-complexity

我正在尝试对运行时间有更多的理解。假设我的函数中有代码，并且每个语句都有一些不同的时间复杂度： LinkedList myLL = new LinkedList(); //O(1) myLL.addAtHead("2"); //O</e

浏览 12提问于2020-01-26得票数 0

回答已采纳

3回答

加法的时间比较: ArrayList，LinkedList，ArrayList* (用某种值初始化)*

java、performance、list、arraylist、linked-list

我希望了解更多关于数据结构及其实现的信息(用JAVA语言)。今天，我编写了一个测试来比较(时间比较) ADT列表的不同实现。= new LinkedList<Integer>(); arrayBasedList.add(index); long t1End = System.curre

浏览 7提问于2013-12-06得票数 0

回答已采纳

1回答

平铺搜索(嵌套For循环)

java、performance、for-loop

我在一个平铺数组上搜索，所以基本上有x和y-比方说，一个10乘10的网格。目前我在x和y上使用嵌套的for循环，但我想知道，由于我对Java的算法设计了解不多，有没有更快的方法来做到这一点？每个瓦片我去(xn，yn)，其中n是瓦片编号，我在上面执行一个操作。或者这是最快的方法吗？

浏览 1提问于2013-05-13得票数 0

点击加载更多