为什么对于ArrayList，get操作的运行时为O(1)，而对于LinkedList，运行时为O(N)？
对于ArrayList，get操作的运行时为O(1)（即常数时间复杂度），是因为ArrayList是基于数组实现的数据结构。数组具有随机访问的特点，每个元素在内存中的位置是连续的，通过索引可以直接定位到所需的元素，因此获取元素的时间复杂度为常数级别。
相反，对于LinkedList，get操作的运行时为O(N)（即线性时间复杂度），是因为LinkedList是基于链表实现的数据结构。链表中的每个节点包含了存储的值以及指向下一个节点的指针。要获取指定索引位置的元素，需要从链表头开始，依次遍历节点直到达到目标位置。因此，获取元素的时间复杂度与链表的长度成正比，即为O(N)。
由于ArrayList的元素在内存中是连续存储的，所以可以通过索引直接访问到目标元素，时间复杂度为O(1)，适用于频繁读取元素的场景。而LinkedList需要遍历节点才能找到目标元素，时间复杂度为O(N)，适用于频繁插入、删除元素的场景。因此，在选择使用ArrayList还是LinkedList时，需要根据具体的应用场景来综合考虑元素的读取、插入、删除等操作的频率和重要性。
以下是腾讯云相关产品和产品介绍链接地址：
- 对象存储 COS：提供高扩展性、低成本、可靠安全的云端对象存储服务，适用于海量数据存储、图片、音视频、备份归档等场景。
- 云数据库 MySQL：提供稳定可靠、弹性伸缩的云端MySQL数据库服务，适用于中小型网站、移动应用、游戏、物联网等场景。
- 负载均衡 CLB：提供将访问流量合理分配给多台云服务器的负载均衡服务，提高系统的稳定性和性能。
- 弹性伸缩 AS：帮助用户根据业务需求自动增减云服务器，实现弹性伸缩，提高系统的灵活性和稳定性。
相关·内容
我想使用1 2 3 4或ArrayList来分析移动3 1 2 4 (整数列表)的过程。
我所做的：
aux = arraylist.get(2); // O(1)
arraylist.remove(2); // O(n)
arraylist.add(0, aux); // O(n), shifting elements up.
aux = linkedlist.get(2); // O(n)
linkedlist.remove(2); // O(n)
linkedlist.addFirst(aux); // O(1)
那么，在这种情况下，我们可以说他们是一样的，还是我遗漏了什么？
浏览 2提问于2017-05-10得票数 1
回答已采纳
1回答
下面的代码是这个问题的解决方案：“给定一个二叉树，设计一个算法，它创建每个深度的所有节点的链表(例如，如果你有一棵深度为D的树，你就会有D个链表”。 void createLevelLinkedList(TreeNode root, ArrayList<LinkedList<TreeNode>>lists, int level) {
if(root == null) return; //base case
LinkedList<TreeNode> list = null;
if (lists.size()==level){ //Lev
浏览 27提问于2019-06-23得票数 2
我认为我在理论上很好地理解了ArrayList和LinkedList之间的区别。然而，这是第一次，我把它进行了一个小小的测试，测试结果与我的预期完全不同。
期望：
在开始插入时，Arraylist将比linkedlist慢，因为它必须“移动”元素，对于链接列表，它只需要更新2个引用。
现实:在大多数迭代中，结果都是一样的。对于一些特定的迭代，它要慢一些。
在开始删除时，Arraylist将比LinkedList慢，因为它必须“移动”元素，对于Linkedlist，它只是取消了一个元素。
实际情况:从beg中删除时，性能相同。
测试用例:1 000 000元素
public st
浏览 11提问于2013-03-01得票数 6
回答已采纳
实际上，我已经尝试了一个与相关的proformance vs LinkList .But的例子--我的问题是，proformance对于不同的机器是不同的，在我阅读堆栈溢出中的一个问题之前，就像这样。
package com.demo.collections;
import java.util.ArrayList;
import java.util.LinkedList;
public class ArraylistAndLinklist {
public static void m
浏览 6提问于2013-11-20得票数 0
回答已采纳
1回答
在这个中，作者说get(index)在ArrayList中是O(1)，而在LinkedList中是O(n/2)，因为它需要遍历直到那个条目。在ArrayList中使用恒定时间的get操作是有意义的，因为ArrayList可以访问所有索引。但是，我不理解LinkedList的O(n/2)。我被教导的方式是，当你使用大的哦符号，你应该写它没有常数，使它更容易解释给别人；也就是说，O(n)，而不是O(2n)。O(n)也是最坏情况下的运行时间吗？这样，使用O(n)对我来说就更有意义了，因为您正在搜索的元素可能在末尾。有人知道为什么作者包括n/2吗？
浏览 3提问于2014-09-18得票数 1
回答已采纳
8回答
我在跟踪一个，上面写着：
对于LinkedList
get是O(n)
加法为O(1)
移除是O(n)
Iterator.remove是O(1)
对于ArrayList
get是O(1)
add是O(1)摊销的，但O(n)是最坏的情况，因为数组必须调整大小和复制。
移除是O(n)
因此，通过查看这个，我得出的结论是，如果我只需要在集合中对5000000元素进行顺序插入，那么LinkedList将超过ArrayList。
如果我只需要通过迭代从集合中获取元素，即不在中间抓取元素，那么LinkedList仍将超过ArrayList。
现在，为了验证
浏览 14提问于2011-05-01得票数 66
回答已采纳
据说，LinkedList删除和添加操作的复杂性是O(1)的。如果是ArrayList，则是O(n)。
大小为"M“的ArrayList的计算:如果我想在N个位置删除元素，那么我可以使用索引一次直接到N个位置(我不需要遍历直到N个索引)，然后我可以删除这个元素，直到此时复杂度是O(1)，那么我将不得不移动其余的元素( can移位)，所以我的复杂度将是线性的，即O(M-N+1)。因此，删除或插入在最后将给我最好的表现(如N~ M)，删除或插入在开始将是最差的(如N~ 1)。
现在大小为"M“的LisnkedList :由于我们不能直接到达LinkedList中的N个元素，为了访问
浏览 5提问于2017-03-17得票数 23
回答已采纳
可能重复：
这是一次真正的尝试，想知道何时才会使用LinkedList；
据我所知，由于java.util.LinkedList不支持随机访问，获得第n个元素的唯一方法是跳过从1跳到(n-1)或使用get(n)，这本身效率很低。那么，为什么要使用LinkedList呢？在大多数情况下，除非您想使用ArrayList迭代来自双方的集合，否则ListIterator将起很大的作用。
浏览 2提问于2012-03-19得票数 8
回答已采纳
1回答
我正在处理我的java应用程序，我关心性能速度，特别是因为我有很多数据结构，比如List、Map等等。
我知道LinkedList的add(Object obj)方法的复杂性是O(1) (使用LinkedList的主要原因)，ArrayList的get(int索引)方法的复杂性是O(1) (使用ArrayList的主要原因)。
我在网上找到了这篇文章：
在优化代码的ArrayList性能时，尝试遵循以下规则：
将元素添加到列表的末尾
也从末尾移除元素
避免包含、indexOf和删除(对象)方法
更要避免使用removeAll和retainAll方法
使用subList(int，int).cl
浏览 3提问于2016-06-19得票数 1
回答已采纳
1回答
我正在做一个关于Java中k叉树实现的大学项目，现在我需要计算我以前实现的一些方法(或算法)的计算复杂度(最坏的情况)。
在每个方法的末尾，我写了我认为这个方法的计算复杂性应该是什么。
int ar; //arity of tree, given by user
List<Node<T>> children = new ArrayList<Node<T>>(ar);
public void addChild(Node<T> n) {
if(this.numberOfChildren()>=ar){
Sy
浏览 2提问于2015-06-01得票数 0
回答已采纳
在迭代LinkedList时，get(i)是O(N)操作。因此，我们使用Iterator对象遍历列表是有意义的。但是对于ArrayList，get(i)是O(1)。那么，在这种情况下，我说的对吗?当使用ArrayList时，无论我们使用c样式的循环还是Iterator对象，都没有什么区别吗？
浏览 4提问于2015-04-09得票数 0
回答已采纳
到处都写着，卡恩的拓扑排序的BFS算法需要O(V+E)时间复杂度，但是如果我分解了它的代码，我就会意识到，在计算顶点的内度时，我们要多次访问一个顶点，那么TC不应该是O(n^2)吗？在我们的while循环中，我们不止一次访问顶点，那么TC仍然O(V+E)是怎样的呢？
这是我的代码：
public static void sort(ArrayList<ArrayList<Integer>> adjList,int vertices){
int[] inDegree=new int[vertices];
for(int i=0;i<ad
浏览 10提问于2022-06-21得票数 0
我还没有发现关于Collections.rotate(list，k)的时间复杂性的很多信息，我是否正确地假设了以下这些？
For ArrayList: O(n)为LinkedList的和ArrayDeque: O(k)的大小为n
提前谢谢。
浏览 6提问于2022-04-10得票数 0
在一次创建一个元素，然后在稍后读取一个元素的情况下，最快的列表实现(在java中)是什么？读取将通过迭代器完成，然后列表将被销毁。
我知道get的大O符号是O(1)，ArrayList的add是O(1)，而get的LinkedList是O(n)，add是O(1)。迭代器是否使用相同的大O符号？
浏览 2提问于2008-09-25得票数 27
回答已采纳
我读过和
并且理解LinkedList add(E元素)是O(1)，ArrayList add(E元素)是O(1)摊销的，但是O(n)最坏的情况，因为数组必须调整大小和复制。
但是，当我试着检查的时候
public class ArrayListVSLinkeedList {
public ArrayListVSLinkeedList() {
final int COUNTER = 15000000;
List<Integer> arrayList = new ArrayList<Integer>();
long tStart_add =
浏览 2提问于2015-02-10得票数 4
回答已采纳
2回答
我正在整理算法和数据结构，并有一些问题和声明，我想让你检查。
ArrayList - O(1) (大小、获取、设置、.)、O(n) -添加操作.
LinkedList -所有操作O(1) (包括add() )，但检索n-元素(即O(n) )除外。我假设size()操作也运行在O(1)中，对吗？
TreeSet -所有操作O(lg(N))。尺寸()操作需要O(lg(n))，对吗？
HashSet -如果应用适当的哈希函数，则所有操作O(1)。
HashMap -所有操作O(1)，与HashSet相应。
任何进一步的解释都是非常欢迎的。提前谢谢你。
浏览 2提问于2011-07-09得票数 21
回答已采纳
据我所知，有以下实现：
ArrayListLinkedListVectorStack
(基于，如果错误请正确)
ArrayList是一个动态数组实现，因此，作为数组，get是O(1)，LinkedList有O(1)表示来自头，向量和堆栈是基于ArrayList的，因此，O(1)。
因此，在每种情况下，都可以在任何内置设备上获得(0)(因为您可以自己制作，用于特定的目的: get(0) TS of O(n!))如果O(1)执行列表？
浏览 4提问于2020-10-24得票数 0
是的，这是一个古老的话题，但我仍然有些困惑。
在Java中，人们说：
如果我随机访问ArrayList的元素，那么它的速度要比LinkedList快。我认为随机访问意味着“给我第n个元素”。为什么ArrayList更快？
LinkedList的删除速度比ArrayList快。我明白这句话。ArrayList比较慢，因为内部备份数组需要重新分配。代码解释：
List =新的ArrayList()；list.add("a")；list.add("b")；list.add( "c“)；list.remove("b")；System.ou
浏览 31提问于2012-05-18得票数 76
回答已采纳
4回答
我正在浏览这个对此问题进行了大量讨论并投了很多票，偶然发现了一个评论，它获得了5张选票。
所以我认为这是一个伟大的comment.But，它让我的头同时旋转。有人能解释一下这句话吗？评论说：
如果不考虑常数因素，就不能直接比较大O值。对于小列表(而且大多数列表都很小)，ArrayList的O(N)比LinkedList的O(1)更快。
浏览 0提问于2012-07-19得票数 5
回答已采纳
3回答
对于使用LinkedList实现的Stack抽象数据类型，put(x)和get()函数的时间复杂度是多少？
我的第一个想法是它们都是O(1)。但是，如果get()必须从头节点遍历到列表中的最后一个元素以找到要移除并返回的元素，则get()函数将为O(n)。
put(x)函数也必须遍历整个列表以找到最后一个节点，它将在其中安装一个新节点。所以这也是O(n)。
如果使用LinkedList的“专用”版本，该版本始终保留指向列表中最后一个节点的指针，则这两个操作都将成为常量时间操作。我认为LinkedList的标准实现不会有这个功能，这是正确的吗？
浏览 1提问于2011-06-30得票数 2
回答已采纳
第一部分：
我在"Data Structure and Algorithms made in Java“一书中读到，从Linkedlist和Arraylist中删除最后一个元素的时间复杂度为O(n)。但是链表在内部实现了DoublyLinkedlist，所以时间复杂度应该是O(1)，类似地，对于数组来说，因为它在内部实现了数组，所以时间复杂度应该是O(1)。
第二部分：
它还指出，在linkedlist结尾处插入元素的时间复杂度为O(n)，但是linkedlist在结尾处和前面都保留了指针。那么这句话是正确的吗？而且，如果数组未满，则在数组末尾插入元素的时间复杂度为O(1)，如果数组已
浏览 14提问于2017-04-01得票数 10
回答已采纳
我必须在两种数据结构中进行选择，ArrayList和LinkedList。我有两个操作op_one，op_two。
如果我选择ArrayList -我最终会得到
for op_one ------ O(n), and at maximum n re-allocations
for op_two ------ O(1), and at maximum n re-allocations
如果我选择LinkedList -我最终会得到
for op_one ------ O(n), and zero re-allocations
for op_two ------ O(n), and zero re
浏览 1提问于2012-09-08得票数 1
2回答
我有一个函数，它选择List的一个随机元素并返回它。列表可以而且非常长(数百万个元素)，这个函数每秒被调用数千次，所以效率是很重要的。
我当前的实现如下：
MyClass getRandomElement(List<MyClass> myClasses) {
return myClasses.get(getRandomNumber(myClasses.size()));
}
这个解决方案有两个问题。
List.get不能保证在O(1)中运行。例如，LinkedList在O(n)中实现了它。
size不能保证在所有List实现上都在O(1)中运行。
第二点不是很有
浏览 9提问于2016-06-15得票数 5
回答已采纳
我是Kava的新手，我很难理解我做错了什么，以及为什么我的代码不能工作。
我正在尝试实现桶排序，使用给定的双精度数组(double[] ar)，并使用linkedLists的arrayList。
下面是我的代码：
int n = ar.length;
//initializing the buckets
ArrayList<LinkedList<Double>> buckets = new ArrayList<LinkedList<Double>>(ar.length);
// Initialize
浏览 1提问于2014-04-23得票数 0
3回答
Java中的时间复杂性
、、、
对于ArrayList Java API状态的方法add：
add操作在分期恒定时间内运行，即添加n个元素需要O(n)时间。
我想知道当使用LinkedList的add方法时，它是否具有相同的时间复杂度，线性。
浏览 0提问于2012-02-13得票数 3
回答已采纳
我和我的合作伙伴正在尝试编写一个LinkedList数据结构。我们已经完成了数据结构，并且它可以使用所有需要的方法正常工作。我们需要对LinkedList类中的addFirst()方法与ArrayList结构中的add(0，item)方法的运行时进行比较测试。对于我们的LinkedList数据结构，addFirst()方法的预期复杂度是O(1)常数。这在我们的测试中是正确的。在对ArrayList add()方法进行计时时，我们预期复杂度为O(N)，但我们再次得到的复杂度约为O(1)常数。这似乎是一个奇怪的差异，因为我们使用的是Java的ArrayList。我们认为我们的时间结构可能有问题，如
浏览 0提问于2013-06-20得票数 1
回答已采纳
4回答
迭代数组列表的时间复杂度
、、、、
我有一个数组列表，我可以遍历它。在每次迭代中，我调用get()来获取一个元素，如果该元素通过了某个条件，就会使用add()将其添加到新的数组列表中
List<Item> items = new ArrayList<Item>();
List<Item> lessItems = new ArrayList<Item>();
for(int index = 0; index < items.size(); index++){
Item toCheck = items.get(i);
if(toCheck meets some c
浏览 1提问于2016-09-17得票数 7
- LinkedList和ArrayList__有什么区别？什么时候使用LinkedList__比较好？
我认为每个Java开发人员至少在一次访谈中听到过这个问题。
-如果您希望能够在列表的中间插入项目，则最好使用链接列表。
对于这个问题，这是一个常见的答案。每个人都知道。每次您询问List实现之间的差异时，您都会得到如下的答案：
我什么时候应该使用LinkedList？什么时候需要在元素之间或开始时进行有效的移除？
忘了提到插入费了。在LinkedList中，一旦找到正确的位置，插入成本就会达到O(1)，而在ArrayList中则会上升到O(n) --通过插入点的所有元素都必须移
浏览 16提问于2013-05-29得票数 20
回答已采纳
2回答
来自，
您似乎将ArrayList用于所有目的。在Java中还有其他列表类型，它们比ArrayList更适合某些情况。你应该看看这些，试着去感受一下什么时候使用哪一个列表。在这种特殊情况下，即LinkedList更好。
我还倾向于大量使用ArrayList，并且看不到选择另一种列表类型的逻辑。
显示了五个主要的List子类：、、、和。
从ArrayList文档，
大小、isEmpty、get、set、迭代器和listIterator操作在恒定时间内运行。add操作在摊销常数时间内运行，也就是说，添加n个元素需要O(n)时间。所有其他操作都以线性时间运行(粗略地说)。与LinkedLi
浏览 4提问于2016-02-13得票数 7
回答已采纳
for (int i =0; i < n; i++){
lst.add(lst.size()/2,3*i);
}
我在想for循环将采用o(n)，但我不清楚如果使用ArrayList和LinkedList，add(j，t)之间有什么区别。谢谢!
浏览 6提问于2013-11-03得票数 1
回答已采纳
1回答
在Java的上下文中交谈。如果我想在ArrayList或linkedList中间插入，我已经被告知Arraylist会执行得很糟糕。
我知道这是因为，我们需要转移所有的元素，然后进行插入。这应该是n/2的顺序，即O(n)。
但对于linkedList来说，情况就不一样了。对于链表，我们需要遍历直到找到中间位置，然后执行指针操作。在这种情况下，也需要O(n)时间。不是吗？
谢谢
浏览 0提问于2013-10-09得票数 8
我在一些地方读到，LinkedList在Java中添加和删除元素的时间复杂度是O(1)，而O(n)是获取元素的时间复杂度。ArrayList有O(1)来获取元素，O(n)可以添加和删除元素。
我有一个程序，它必须做许多涉及插入和从列表中恢复元素的操作。因此，我想知道访问元素的ArrayDeque时间是否类似于ArrayList。
浏览 0提问于2018-11-27得票数 2
回答已采纳
在这种情况下，ArrayDeque应该比LinkedList更好吗？。
在我看来，我应该使用LinkedList而不是ArrayDeque，因为这个算法中有相当多的poll和offer操作，并且没有对元素的随机访问。
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode a) {
Queue<TreeNode> q = new LinkedList<>(); // new ArrayDeque<>() ???
q.offer(a);
ArrayLi
浏览 1提问于2019-06-26得票数 1
我目前正在使用OPAL框架开发Java代码的静态分析。我想分析以下Java方法：
private void indirectCaller2b(double d, Object o1, Object o2) {
indirectCaller1(d, o1, o2);
}
我知道，indirectCaller2b只使用参数(double，ArrayList，LinkedList)调用。
考虑到这一点，我构建了一个IndexedSeq of DomainValues，并将其传递给执行方法ob BaseAI。看起来是这样的：
Vector({ai.native_methods_paramet
浏览 3提问于2016-06-18得票数 0
回答已采纳
我问这个问题已有一段时间了，但我对答案并不满意，因为这些区别似乎是武断的，更像是一种被盲目接受的传统智慧，而不是批判性的评价。
在ArrayList中，插入成本(对于单个元素)是线性的。如果我们在索引p处插入0 <= p<n，其中n是列表的大小，那么在将新元素复制到位置p之前，剩余的n元素首先被移动。
在LinkedList中，据说插入成本(对于单个元素)是恒定的。例如，如果我们已经有了一个节点，并且想要在它后面插入，我们重新排列一些指针，它很快就完成了。但是，首先，除了线性搜索之外，我看不出如何完成这个节点(假设它不是像列表开始时的前置或末尾附加这样的琐碎情况)。
然而，在Lin
浏览 4提问于2016-10-03得票数 1
回答已采纳
我试图编写一个代码，将二叉树转换为具有相同深度的节点列表。如果树有深度d，则将创建d列表。逻辑是按顺序遍历，并将当前遍历的节点添加到适当深度的列表中。
public void treeToListofNodesByLevel(Node<T> n,int depth, ArrayList<LinkedList<Node<T>>> treeList){
if(n.right != null){
inOrderWithHeight(n.right, depth + 1);
}
i
浏览 1提问于2016-10-27得票数 0
回答已采纳
我正在学习考试(算法和数据结构)，我试图让quicksort在LinkedList上工作，但它给了我ListIndexOutOfBoundsException。
不久前，我使用straightinsertion对ArrayList和Vector进行排序，现在我想了解一下LinkedList的QuickSort (理论上我是这样做的)。我对linkedlist不是很熟悉，但它应该与ArrayList没有太大不同
public class Sort {
public static void quickSort(LinkedList<Oseba> a) {
sort(a, 0,
浏览 1提问于2013-01-25得票数 0
1回答
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n == 0) {
return nums;
}
int[] result = new int[n - k + 1];
LinkedList<Integer> dq = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (!dq.isEmpty() && dq.pe
浏览 6提问于2020-02-16得票数 2
回答已采纳
2回答
我正在尝试实现一种以插入性能为中心的类似队列的数据结构，它必须满足以下要求：
必须是线程安全的
必须能够在不同步的情况下添加到队列中。
必须能够获得队列的“快照”视图。
我的问题是以一种不需要插入同步的方式获得‘快照’视图。因为我可以阻止删除，并且元素只能添加到末尾，所以获取元素不应该是一个问题。我一直遇到的问题是LinkedList的迭代器有一个不可抑制的并发修改，快速失败，而'LinkedList.get(int)‘是O(n)。
下面是一个缩小的例子，说明我在做什么应该是一个相当简单的任务。
public class SnapshotableQueue<T
浏览 3提问于2016-05-30得票数 1
回答已采纳
3回答
我正在比较ArrayList和LinkedList中contains方法在0到1000之间的数字序列上的性能。
对于这两个列表，我做一个包含(400)。ArrayList的性能总是比LinkedList高3倍。用JMH进行了比较。
ArrayList花费了329,642纳秒
LinkedList花费了945,881纳秒
如果这两个列表都具有worse方法的O(n)性能，为什么LinkedList要差3倍呢？
比较类：
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations
浏览 0提问于2020-08-02得票数 0
回答已采纳
4回答
假设您有一个大小为N的链表，并且您希望从末尾开始对每个元素执行一个操作。
我想出了下面的伪代码：
while N > 0
Current = LinkedList
for 0 to N
Current = Current.tail
end
Operation(Current.head)
N := N-1
end
现在，我必须确定这个算法是哪个大O。
假设Operation()是O(1)，我认为它是这样的：
N + (N-1) + (N-2) + ... + (N-(N-1)) + 1
但我不确定那到底是什么大O。我认为它肯定比O(
浏览 0提问于2011-01-24得票数 0
回答已采纳
关于这个项目我有个问题。
public class Main {
public static void main(String[] args) {
List<String> arrayList = new ArrayList<String>();
for(int i=0; i<100; i++){
arrayList.add("ValueA");
arrayList.add("ValueB");
arrayList.add
浏览 4提问于2015-12-11得票数 3
回答已采纳
public static int Count( List<Integer> lst1, List<Integer> lst2)
{
Iterator<Integer> itr1 = lst1.iterator();
int count=0;
while ( itr1.hasNext() )
{
Integer x = itr1.next();
Iterator<Integer> itr2 = lst2.iterator();
while ( itr2.hasNex
浏览 1提问于2013-06-22得票数 0
1回答
在字符串中搜索子字符串
、、、
嘿，伙计们，我有下面的代码在一个大约有70万个字母的文件中搜索子字符串，我相信，它在ArrayList上工作得很好，但对于LinkedList来说，它需要永远完成。任何人都能理解为什么要花这么多时间？
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
impo
浏览 1提问于2015-02-09得票数 0
我正在实现一个公共方法，它需要一个需要能够处理两端插入的数据结构。由于ArrayList.add(0,key)将占用O(N)时间，所以我决定使用LinkedList -- add和addFirst方法都应该使用O(1)时间。
但是，为了使用现有的API，我的方法需要返回一个ArrayList。所以我有两种方法：
(1)使用LinkedList，在前面加入N/2，将N/2添加到N/2。然后通过调用LinkedList构造函数：return new ArrayList<key>(myLinkedList);将该ArrayList转换为return new ArrayList<ke
浏览 2提问于2013-08-01得票数 4
回答已采纳
为什么ArrayList add()和add( index，E)复杂度是摊销常数时间？
为什么O(1)用于单add()操作，O (n )用于单add(int index，E)操作，O(n)用于添加n个元素(n add操作)？假设我们很少使用add ( index，E)添加到数组末端？
数组(和ArrayList)的操作复杂性不是已经有n个元素的：
加()- O(1)？
添加(int索引，E) - O(n)？
如果我们做了一百万次插入，平均1和2不可能是O(1)，对吗？
甲骨文为什么说
添加操作运行在分期常数时间中，即添加n个元素需要O(n)时间。
I认为复杂性对于add
浏览 17提问于2017-07-20得票数 22
回答已采纳
package data_structures_java ;
import java.util.LinkedList;
class Queue_implementation {
private LinkedList<Float> list = new LinkedList<Float>();
public void enqueue(Float item) {
list.addLast(item);
}
public Float dequeue() {
return list.poll();
}
浏览 4提问于2014-04-10得票数 0
回答已采纳
2回答
问题
给定一个二叉树，设计一个算法，在每个深度上创建一个所有节点的链表(例如，如果你有一棵深度D的树，你就会有D个链表)
这是我试图解决的问题。我还没有对它进行测试，但我试图获得反馈，以确定这是否是一种合适的解决方案。
public class solution {
ArrayList<LinkedList<Node>> makeArrayList(Node n) {
int level = 0;
return addLists(new ArrayList<LinkedList<Node>>(), n,
浏览 0提问于2013-03-01得票数 2
回答已采纳
1回答
区间和的时间复杂度
、、、
我试图理解算法的时间复杂性，并遇到了这个问题。问题是计算区间和(0 <= k <= length_of_list)。
public static void main(String args[]){
LinkedList<Integer> l=new LinkedList<Integer>();
l.add(4);
l.add(2);
l.add(3);
l.add(1);
l.add(5);
int k=2;
List result = new ArrayList();
int n
浏览 3提问于2017-02-14得票数 1
回答已采纳
2回答
我正在尝试了解在访问ArrayList、LinkedList、HashSet、TreeSet、HashMap、TreeMap等Java语言集合中的元素时，哪个更快。
从这个问题：，我知道ArrayList取O(1)，TreeMap取O(log )
其中：表示ArryList为O( n)，HashMap为O(1)，TreeMap为O(log )
其中：表示排序的数组比未排序的数组更快。由于TreeMap中的元素是排序的，那么我可以假设所有排序的集合都比未排序的集合更快吗？
请帮助我理解在访问列表、集合、映射等实现的java集合中的元素时，哪个使用起来更快。
浏览 4提问于2013-11-30得票数 7
回答已采纳
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM
腾讯云开发者
