开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

为什么在LinkedList末尾添加一个元素比添加一个ArrayList要花更长的时间？

在LinkedList末尾添加一个元素比添加一个ArrayList要花更长的时间的原因是LinkedList的内部实现方式不同于ArrayList。

LinkedList是一种链表数据结构，它由一系列节点组成，每个节点包含一个元素和一个指向下一个节点的引用。当在LinkedList末尾添加一个元素时，需要先找到链表的最后一个节点，然后创建一个新的节点并将其链接到最后一个节点的后面。这个过程需要遍历整个链表，直到找到最后一个节点。因此，添加一个元素的时间复杂度是O(n)，其中n是链表的长度。

相比之下，ArrayList是一种基于数组的数据结构，它在内存中分配一块连续的空间来存储元素。当在ArrayList末尾添加一个元素时，只需要将元素直接放入数组的最后一个位置即可，不需要遍历整个数组。因此，添加一个元素的时间复杂度是O(1)。但是，如果数组已经满了，需要进行扩容操作，这个过程会涉及到数据的复制，因此在某些情况下，添加一个元素的时间复杂度可能会达到O(n)。

综上所述，LinkedList在末尾添加一个元素需要遍历整个链表，而ArrayList只需要将元素放入数组的最后一个位置。因此，LinkedList的添加操作相对较慢。但是LinkedList在其他操作上可能更加高效，比如在链表的任意位置插入或删除元素，因为它只需要修改节点的引用，而不需要像ArrayList那样进行数据的搬移。所以，在选择使用LinkedList还是ArrayList时，需要根据具体的场景和需求来进行权衡和选择。

腾讯云相关产品和产品介绍链接地址：

腾讯云云服务器（CVM）：https://cloud.tencent.com/product/cvm
腾讯云云数据库 MySQL 版：https://cloud.tencent.com/product/cdb_mysql
腾讯云对象存储（COS）：https://cloud.tencent.com/product/cos
腾讯云人工智能：https://cloud.tencent.com/product/ai
腾讯云物联网平台：https://cloud.tencent.com/product/iotexplorer

相关搜索:Switch语句不允许我将ArrayLists的最后一个元素添加到新的ArrayList中为什么file.write()要在末尾添加一个额外的字符串？为什么JavaScript要在已解析数字的末尾添加一个额外的非零数字在ArrayList - java的一个索引中添加两种不同的数据类型在C中如何在char数组的末尾添加一个char (零)？在DynamoDBItem中添加/删除字符串集中的一个元素在FlatList的末尾添加最后一个元素在Python - Leetcode中将一个列表的末尾添加到另一个列表的末尾在python中将第一个单词添加到句子的末尾在python的字符串末尾添加一个递增的数字

相关搜索:

页面内容是否对你有帮助？

有帮助

没帮助

相关·内容

数据结构思维第五章双链表

例如，当我们使用add方法将元素添加到ArrayList的末尾，我们发现，执行n次添加的总时间正比于n。也就是说，估计的斜率接近1。...根据我们的分析，我们预计每个add都要花时间，因为在一个链表中，我们不必转移现有元素；我们可以在头部添加一个新节点。所以我们预计n次添加的总时间是线性的。...5.3 LinkedList的尾部添加在开头添加元素是一种操作，我们期望LinkedList的速度快于ArrayList。但是为了在末尾添加元素，我们预计LinkedList会变慢。...图 5.2：分析结果：在LinkedList末尾添加n个元素的运行时间和问题规模同样，测量值很嘈杂，线不完全是直的，但估计的斜率为1.19，接近于在头部添加元素，而并不非常接近2，这是我们根据分析的预期...LinkedList对象包含指向列表的第一个和最后一个元素的链接。所以我们可以从列表的任意一端开始，并以任意方向遍历它。因此，我们可以在常数时间内，在列表的头部和末尾添加和删除元素！

2713 0

面试官：兄弟，说说 ArrayList 和 LinkedList 有什么区别

1）ArrayList ArrayList 新增元素有两种情况，一种是直接将元素添加到数组末尾，一种是将元素插入到指定位置。...595 LinkedList从集合头部位置新增元素花费的时间15 ArrayList 花费的时间比 LinkedList 要多很多。...69 LinkedList从集合尾部位置新增元素花费的时间193 ArrayList 花费的时间比 LinkedList 要少一些。...ArrayList 在添加元素的时候如果不涉及到扩容，性能在两种情况下（中间位置新增元素、尾部新增元素）比 LinkedList 好很多，只有头部新增元素的时候比 LinkedList 差，因为数组复制的原因...花费的时间比 LinkedList 少很多；从集合尾部删除元素时，ArrayList 花费的时间比 LinkedList 少一点。

6193 1

说一下 ArrayList 和 LinkedList 的区别？

在上一篇文章里，我们聊到了基于动态数组 ArrayList 线性表，今天我们来讨论一个基于链表的线性表 —— LinkedList。...，而链表需要 O(n) 时间复杂度查找元素；在添加和删除操作上：如果是在数组的末尾操作只需要 O(1) 时间复杂度，但在数组中间操作需要搬运元素，所以需要 O(n)时间复杂度，而链表的删除操作本身只是修改引用指向...♀️ 疑问 2：为什么字段都声明 transient 关键字？这个问题我们在分析源码的过程中回答。疑问比 ArrayList 少很多，LinkedList 真香（还是别高兴得太早吧）。...的构造方法 LinkedList 有 2 个构造方法： 1、无参构造方法： no-op； 2、带集合的构造：在链表末尾添加整个集合，内部调用了 addAll 方法将整个集合添加到数组的末尾。...分析一下添加方法的时间复杂度，区分在链表两端或中间添加元素的情况共：如果是在链表首尾两端添加：只需要 O(1) 时间复杂度；如果在链表中间添加：由于需要定位到添加位置的前驱和后继节点，所以需要

3342 0

ArrayList VS LinkedList，最后一战

1）ArrayList ArrayList 新增元素有两种情况，一种是直接将元素添加到数组末尾，一种是将元素插入到指定位置。...595 LinkedList从集合头部位置新增元素花费的时间15 ArrayList 花费的时间比 LinkedList 要多很多。...69 LinkedList从集合尾部位置新增元素花费的时间193 ArrayList 花费的时间比 LinkedList 要少一些。...ArrayList 在添加元素的时候如果不涉及到扩容，性能在两种情况下（中间位置新增元素、尾部新增元素）比 LinkedList 好很多，只有头部新增元素的时候比 LinkedList 差，因为数组复制的原因...花费的时间比 LinkedList 少很多；从集合尾部删除元素时，ArrayList 花费的时间比 LinkedList 少一点。

3093 0

Collection子接口之List

比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。...内存空间占用： ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间...为什么呢？我觉得还是和底层数据结构有关！ArrayList 底层是数组，而 LinkedList 底层是链表。数组天然支持随机访问，时间复杂度为 O(1)，所以称为快速随机访问。...ArrayList 的扩容机制先来看 add 方法 /** * 将指定的元素追加到此列表的末尾。...当 add 第 2 个元素时，minCapacity 为 2，此时 e lementData.length(容量)在添加第一个元素后扩容成 10 了。

5641 0

ArrayList和LinkendList不是我们想的那样？

这两种方法也是有很大不同的，添加元素到任意位置，会导致数组中在该位置之后的所有元素都需要重新排列，将元素添加到数组的末尾。而直接在末尾新增元素，如果不扩容的时候是没有元素复制排序的过程的。...，默认是将元素添加到链表的末尾，首先将last元素置换到临时变量中，生成一个新的Node节点对象，然后将last引用指向新节点对象，之前的last对象的前指针执行新节点对象。...也是支持将元素添加到任意位置的，将元素添加到任意两个元素的中间，只会改变前后元素的前后指针，指针将会指向添加的新元素，所以比ArrayList的添加操作性能优势明显。...从中间添加元素的时候，我们知道ArrayList需要对部分数据进行复制重排，效率不是很高，但是LinkedList将元素添加到中间位置是添加元素效率最低的，我们知道靠近中间位置在添加元素之前的循环查找是遍历元素最多的操作...从尾部添加元素的操作测试中，我们发现如果不需要扩容的情况下，ArrayList的效率比LinkedList的效率高，这是因为ArrayList从尾部添加元素的时候不需要重排数据，效率非常高，而LinkedList

5792 0

Collection 子接口之 List

比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。...内存空间占用：ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间...为什么呢？我觉得还是和底层数据结构有关！ArrayList 底层是数组，而 LinkedList 底层是链表。数组天然支持随机访问，时间复杂度为 O(1)，所以称为快速随机访问。...ArrayList 的扩容机制先来看 add 方法 /** * 将指定的元素追加到此列表的末尾。...当 add 第 2 个元素时，minCapacity 为 2，此时 e lementData.length(容量)在添加第一个元素后扩容成 10 了。

4663 0

Java集合解惑

解析：当在 ArrayList 中增加一个对象时 Java 会去检查 Arraylist 以确保已存在的数组中有足够的容量来存储这个新对象，如果没有足够容量就新建一个长度更长的数组（原来的1.5倍），...从动态扩容角度看由于 ArrayList 和 Vector（Stack 继承自 Vector，只在 Vector 的基础上添加了几个 Stack 相关的方法，故之后不再对 Stack 做特别的说明）使用数组实现...，抛开两个只在序列化过程中使用的方法不说，没有一个 ArrayList 的方法是同步的，相反，绝大多数 Vector（Stack）的方法法都是直接或者间接的同步的，因此就造成 ArrayList 比 Vector...（Stack）更快些，不过在最新的 JVM 中，这两个类的速度差别是很小的，几乎可以忽略不计；而 LinkedList 是双向链表实现，根据索引访问元素时需要遍历寻找，性能略差。...LinkedHashMap 支持插入顺序或者访问顺序，LRU 算法其实就要用到它访问顺序的特性，即对一个键执行 get、put 操作后其对应的键值对会移到链表末尾，所以最末尾的是最近访问的，最开始的最久没被访问的

6522 0

笔记29 | 整理Java的容器类

默认在队列末尾添加元素；如果指定了索引位置，则在指定位置末尾添加元素 get : 获取指定位置的元素 indexOf : 获取指定元素的第一个索引位置 lastIndexOf : 获取指定元素的最后一个索引位置...链表的常用方法包括上面队列列出的几个，下面列出添加的方法 addFirst/addLast : 添加到开头/添加到末尾 getFirst/getLast : 获取首元素/获取末元素 removeFirst...具体的说，当一个向量的指针Iterator正在使用时，另一个线程改变了向量的状态（比如添加或删除了一些元素），这时调用指针的方法将抛出异常(ConcurrentModificationException...堆栈的常用方法比向量多了三个，分别是 peek（获取首元素）、 pop（出栈）、 push（入栈），看起来Stack类似一个堆栈方式的链表。...因为同步需要花费机器时间，所以HashTable的执行效率要低于HashMap，向量和队列的情况与之类似。哈希表的常用方法与映射是一样的，就不一一列举了。

5714 0

Java高频面试之集合篇

从集合头部位置新增元素花费的时间" + (timeEnd - timeStart)); } ArrayList从集合头部位置新增元素花费的时间415 LinkedList从集合头部位置新增元素花费的时间...从集合中间位置新增元素花费的时间" + (timeEnd - timeStart)); } ArrayList从集合中间位置新增元素花费的时间19 LinkedList从集合中间位置新增元素花费的时间28610...从集合尾部位置新增元素花费的时间" + (timeEnd - timeStart)); } ArrayList从集合尾部位置新增元素花费的时间17 LinkedList从集合尾部位置新增元素花费的时间13...> elementData.length 通过索引将元素添加到末尾 elementData[size++] = e list.add(int index, Object e) 性能比较差检查插入的位置是否在合理的范围之内...[index] = e LinkedList 添加元素流程 list.add(Object e) 直接将元素添加到队尾 list.add(int index, Object e) 检查插入的位置是否在合理的范围之内

601 0

【面试题精讲】ArrayList 插入和删除元素的时间复杂度

为什么需要 ArrayList？在开发过程中，我们经常需要处理一组数据，并且可能需要频繁地进行插入、删除操作。...ArrayList 插入和删除元素的时间复杂度在 ArrayList 的末尾插入元素：O(1) 在 ArrayList 的中间或开头插入元素：O(n)...删除指定位置的元素：O(n) 3.1 在 ArrayList 的末尾插入元素当我们向 ArrayList 的末尾插入元素时，只需将新元素添加到内部数组的最后一个位置即可，不需要移动其他元素...ArrayList 插入和删除元素的优点在 ArrayList 的末尾插入元素的时间复杂度为 O(1)，效率高。...在末尾插入元素的时间复杂度为 O(1)，而在中间或开头插入元素、删除指定位置的元素的时间复杂度为 O(n)。如果需要频繁地进行这些操作，可以考虑使用 LinkedList 替代 ArrayList。

4853 0

Java 容器 & 泛型：二、ArrayList 、LinkedList和Vector比较

三、LinkedList 与 ArrayList 性能比 LinkedList 与 ArrayList 一样实现 List 接口，LinkedList 是 List 接口链表的实现。...基于链表实现的方式使得 LinkedList 在插入和删除时更优于 ArrayList，而随机访问则比 ArrayList 逊色些。...LinkedList 和ArrayList 的方法时间复杂度总结如下图所示。表中，add() 指添加元素的方法，remove() 是指除去（int index）角标。...ArrayList 具有 O（N）的任意指数时间复杂度的添加/删除，但 O（1）的操作列表的末尾。链表的 O（n）的任意指数时间复杂度的添加/删除，但 O（1）操作端/列表的开始。...从复杂度和测试结果，我们应该懂得平时在添加或者删除操作频繁的地方，选择LinkedList时考虑： 1、没有大量的元素的随机访问 2、添加/删除操作下面用 LinkedList 实现一个数据结构–栈。

2493 0

【Java提高十六】集合List接口详解

add 操作以分摊的固定时间运行，也就是说，添加 n 个元素需要 O(n) 时间（由于要考虑到扩容，所以这不只是添加元素会带来分摊固定时间开销那样简单）。 ArrayList擅长于随机访问。...在每次添加新的元素时，ArrayList都会检查是否需要进行扩容操作，扩容操作带来数据向新数组的重新拷贝，所以如果我们知道具体业务数据量，在构造ArrayList时可以给ArrayList指定一个初始容量...基于链表实现的方式使得LinkedList在插入和删除时更优于ArrayList，而随机访问则比ArrayList逊色些。...2.1增加：add(E e) add(E e)：将指定元素添加到此向量的末尾。 ?...所以linkedList的插入动作比ArrayList动作快就在于两个方面。 1:linkedList不需要执行元素拷贝动作，没有牵一发而动全身的大动作。

1.1K3 1

Java集合之LinkedList源码分析

概述 LinkedLIst和ArrayLIst一样, 都实现了List接口, 但其内部的数据结构不同, LinkedList是基于链表实现的(从名字也能看出来), 随机访问效率要比ArrayList差....它的插入和删除操作比ArrayList更加高效, 但还是要遍历部分链表的指针才能移动到下标所指的位置, 只有在链表两头的操作能省掉移动, 如add(), addFirest(), removeLast(...LinkedList源码分析 1.数据结构 LinkedList是基于链表结构实现的, 在类中定义了头尾指针. 其内部维护了一个双向链表 ? ? 2.构造方法默认构造函数很简单, 啥也没有 ?...将集合的元素添加的LinkedList中: ? ? ? 3.存储 (1)add(E)在链表的末尾添加元素 ? ? (2)add(int, E)在指定的位置插入元素 ? ? ?...(3)addAll(Collection)将集合添加到链表末尾, 该方法在构造方法中介绍了, 在此不再赘述 ?

3554 0

Java集合经典26问！

ArrayList 了解吗？ ArrayList 的底层是动态数组，它的容量能动态增长。在添加大量元素前，应用可以使用ensureCapacity操作增加 ArrayList 实例的容量。...(size + 1); //将e添加到数组末尾 elementData[size++] = e; return true; } // 每次在新增一个元素时，需要判断这个...因为ArrayList直接通过数组下标直接找到元素；LinkedList要移动指针遍历每个元素直到找到为止。新增和删除元素，LinkedList的速度要优于ArrayList。...因为ArrayList在新增和删除元素时，可能扩容和复制数组；LinkedList实例化对象需要时间外，只需要修改指针即可。...当我们往容器添加元素时，不直接往容器添加，而是先将当前容器进行复制，复制出一个新的容器，然后往新的容器添加元素，添加完元素之后，再将原容器的引用指向新容器。

3861 0

java面试强基（17）

比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。...内存空间占用： ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间...我们在项目中一般是不会使用到 LinkedList 的，需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替，并且，性能通常会更好！...聊一聊ArrayList的扩容机制？以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。...即向数组中添加第一个元素时，数组容量扩为 10。 Arrlist扩容是原来的数组长度1.5倍。

1444 0

Java高频面试题- 每日三连问？【Day3】 — 集合容器篇

常用的实现类有 ArrayList、LinkedList 和 Vector。 Set：一个无序（存入和取出顺序有可能不一致）容器，不可以存储重复元素，只允许存入一个null元素，必须保证元素唯一性。...数据结构:ArrayList 是动态数组的数据结构实现；随机查询效率：（优势），ArrayList 比 LinkedList 在随机访问的时候效率要高，因为 LinkedList 是线性的数据存储方式...插入和删除效率：在List中间插入和删除数据时，ArrayList 要比 LinkedList 效率低很多，因为 ArrayList 增删操作要影响数组内的其他数据的下标（整体移动），而如果是正常的末尾追加方式...内存空间占用：LinkedList 比 ArrayList 更占内存，因为 LinkedList 的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。 ?...Collections内部使用数组排序方法，所有它们两者都有相同的性能，只是Collections需要花时间将列表转换为数组。 ?

5712 0

数据结构思维第四章 `LinkedList`

上运行add所需的时间，它向末尾添加新元素。...如果你将这个序列传给plotResults，它会产生一个如图 4.1 所示的图形。图 4.1 分析结果：将n个元素添加到ArrayList末尾的运行时间与问题规模。下一节解释了如何解释它。...4.4 解释结果基于我们对ArrayList工作方式的理解，我们期望，在添加元素到最后时，add方法需要常数时间。所以添加n个元素的总时间应该是线性的。...解释嘈杂的测量值的更好方法是，在重对数刻度上绘制的运行时间和问题规模。 为什么？我们假设运行时间与n ** k成正比，但是我们不知道指数k是什么。...基于我们对ArrayList工作方式的理解，我们期望，每个添加操作是线性的，所以n次添加的总时间应该是平方的。如果是这样，在重对数刻度中，直线的估计斜率应该接近2。是吗？

2952 0

《我们一起学集合》-LinkedList

-4.png] 如图我们可以知道，在向末尾添加元素时先预存了last节点，然后构造新节点newNode并连接到当前尾节点，然后在更新newNode节点为last节点，最后在将节点连接完成。...[LinkedList-6.jpg] 下面是添加集合到链表的方法，插入方式和上面基本相似。 // 将指定集合中的所有元素追加到此列表的末尾，按照指定集合的迭代器返回它们的顺序。...的区别有：结构不同：ArrayList是基于数组，LinkedList是基于节点Node 效率不同：ArrayList随机访问比LinkedList效率高，因为LinkedList必须每次从头遍历查找...从理论上讲ArrayList删除一个元素的效率是比LinkedList低，应为ArrayList删除一个不是末尾的元素会产生元素拷贝，而LinkedList删除一个元素只是修改前后节点的引用。...此操作需要时间，并且当此类获取频繁发生时缓存中的内存页面需要一直替换->缓存未命中->缓存效率不高。ArrayList元素存储在连续内存中，这更利于缓存。这也正是现代CPU体系结构正在优化的内容。

3480 0

【JDK1.8】JDK1.8集合源码阅读——LinkedList

一、前言这次我们来看一下常见的List中的第二个——LinkedList，在前面分析ArrayList的时候，我们提到，LinkedList是链表的结构，其实它跟我们在分析map的时候讲到的LinkedHashMap...extends E> c)作为public方法，所以要考虑到在list已经存在元素的情况下，在链表末尾添加元素： public boolean addAll(Collection<?...if (index == size) { // index == size，说明要插入元素的位置就在链表的末尾，后置元素为null，前一个元素就是last succ = null;...3.3 LinkedList的重要方法 3.3.1 add(E e) 先说一下具体思路，作为链表结构，那么添加元素就是在链表的末尾插入元素，这个过程中要考虑：末尾元素为null，该如何处理 public...四、LinkedList的使用场景 LinkedList作为链表结构的特性，可以保证其在端点操作：如插入以及删除等，速度比ArrayList快，道理很简单，ArrayList在删除后，每次都要把后面的元素往前移

77912 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭