ArrayList和LinkedList使用不当，性能差距会如此之大！
发布时间：2025-11-05 12:25:35 来源：码上建站 作者：数据库
前言
在面试的使用时候，经常会被问到几个问题：
ArrayList和LinkedList的不当区别，相信大部分朋友都能回答上：
ArrayList是差距基于数组实现，LinkedList是使用基于链表实现 当随机访问List时，ArrayList比LinkedList的不当效率更高，等等当被问到ArrayList和LinkedList的差距使用场景是什么时，大部分朋友的使用答案可能是：
ArrayList和LinkedList在新增、删除元素时，不当LinkedList的差距效率要高于 ArrayList，而在遍历的使用时候，ArrayList的不当效率要高于LinkedList那这个回答是否准确呢?今天我们就来研究研究!
我们先来简单介绍下ArrayList和LinkedList的原理实现!
源码分析
ArrayList
实现类
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.SerializableArrayList实现了List接口，继承了AbstractList抽象类，差距底层是使用数组实现的，并且实现了自增扩容数组大小。不当
ArrayList还实现了Cloneable接口和Serializable接口，差距所以他可以实现克隆和序列化。
ArrayList还实现了RandomAccess接口，这个接口是源码库一个标志接口，他标志着“只要实现该接口的List类，都能实现快速随机访问”。
基本属性
ArrayList属性主要由数组长度size、对象数组elementData、初始化容量default_capacity等组成， 其中初始化容量默认大小为10。
//默认初始化容量 private static final int DEFAULT_CAPACITY = 10; //对象数组 transient Object[] elementData; //数组长度 private int size;从ArrayList属性来看，elementData被关键字transient修饰了，transient关键字修饰该字段则表示该属性不会被序列化。
但ArrayList其实是实现了序列化接口，这是为什么呢?由于ArrayList的数组是基于动态扩增的，所以并不是所有被分配的内存空间都存储了数据。
如果采用外部序列化法实现数组的序列化，会序列化整个数组，ArrayList为了避免这些没有存储数据的内存空间被序列化，内部提供了两个私有方法writeObject以及readObject来自我完成序列化与反序列化，从而在序列化与反序列化数组时节省了空间和时间。
因此使用transient修饰数组，是防止对象数组被其他外部方法序列化。
ArrayList自定义序列化方法如下：
初始化
有三种初始化办法：无参数直接初始化、指定大小初始化、站群服务器指定初始数据初始化，源码如下：
当ArrayList新增元素时，如果所存储的元素已经超过其已有大小，它会计算元素大小后再进行动态扩容，数组的扩容会导致整个数组进行一次内存复制。
因此，我们在初始化ArrayList时，可以通过第一个构造函数合理指定数组初始大小，这样有助于减少数组的扩容次数，从而提高系统性能。
注意点：
ArrayList 无参构造器初始化时，默认大小是空数组，并不是大家常说的 10，10 是在第一次 add 的时候扩容的数组值。
新增元素
ArrayList新增元素的方法有两种，一种是直接将元素加到数组的末尾，另外一种是添加元素到任意位置。
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }两个方法的相同之处是在添加元素之前，免费信息发布网都会先确认容量大小，如果容量够大，就不用进行扩容;如果容量不够大，就会按照原来数组的1.5倍大小进行扩容，在扩容之后需要将数组复制到新分配的内存地址。
下面是具体的源码：
这两个方法也有不同之处，添加元素到任意位置，会导致在该位置后的所有元素都需要重新排列，而将元素添加到数组的末尾，在没有发生扩容的前提下，是不会有元素复制排序过程的。
所以ArrayList在大量新增元素的场景下效率不一定就很慢的如果我们在初始化时就比较清楚存储数据的大小，就可以在ArrayList初始化时指定数组容量大小，并且在添加元素时，只在数组末尾添加元素，那么ArrayList在大量新增元素的场景下，性能并不会变差，反而比其他List集合的性能要好。
删除元素
ArrayList 删除元素有很多种方式，比如根据数组索引删除、根据值删除或批量删除等等，原理和思路都差不多。
ArrayList在每一次有效的删除元素操作之后，都要进行数组的重组，并且删除的元素位置越靠前，数组重组的开销就越大。
我们选取根据值删除方式来进行源码说明：
遍历元素
由于ArrayList是基于数组实现的，所以在获取元素的时候是非常快捷的。
public E get(int index) { rangeCheck(index); return elementData(index); } E elementData(int index) { return (E) elementData[index]; }LinkedList
LinkedList是基于双向链表数据结构实现的。
这个双向链表结构，链表中的每个节点都可以向前或者向后追溯，有几个概念如下：
链表每个节点我们叫做 Node，Node 有 prev 属性，代表前一个节点的位置，next 属性，代表后一个节点的位置; first 是双向链表的头节点，它的前一个节点是 null。 last 是双向链表的尾节点，它的后一个节点是 null; 当链表中没有数据时，first 和 last 是同一个节点，前后指向都是 null; 因为是个双向链表，只要机器内存足够强大，是没有大小限制的。Node结构中包含了3个部分：元素内容item、前指针prev以及后指针next，代码如下。
private static class Node<E> { E item;// 节点值 Node<E> next; // 指向的下一个节点 Node<E> prev; // 指向的前一个节点 // 初始化参数顺序分别是：前一个节点、本身节点值、后一个节点 Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }LinkedList就是由Node结构对象连接而成的一个双向链表。
实现类
LinkedList类实现了List接口、Deque接口，同时继承了AbstractSequentialList抽象类，LinkedList既实现了List类型又有Queue类型的特点;LinkedList也实现了Cloneable和Serializable接口，同ArrayList一样，可以实现克隆和序列化。
由于LinkedList存储数据的内存地址是不连续的，而是通过指针来定位不连续地址，因此，LinkedList不支持随机快速访问，LinkedList也就不能实现RandomAccess接口。
public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable基本属性
transient int size = 0; transient Node first; transient Node last;我们可以看到这三个属性都被transient修饰了，原因很简单，我们在序列化的时候不会只对头尾进行序列化，所以LinkedList也是自行实现readObject和writeObject进行序列化与反序列化。
下面是LinkedList自定义序列化的方法。
节点查询
链表查询某一个节点是比较慢的，需要挨个循环查找才行，我们看看 LinkedList 的源码是如何寻找节点的：
LinkedList 并没有采用从头循环到尾的做法，而是采取了简单二分法，首先看看 index 是在链表的前半部分，还是后半部分。
如果是前半部分，就从头开始寻找，反之亦然。通过这种方式，使循环的次数至少降低了一半，提高了查找的性能。
新增元素
LinkedList添加元素的实现很简洁，但添加的方式却有很多种。
默认的add (Ee)方法是将添加的元素加到队尾，首先是将last元素置换到临时变量中，生成一个新的Node节点对象，然后将last引用指向新节点对象，之前的last对象的前指针指向新节点对象。
LinkedList也有添加元素到任意位置的方法，如果我们是将元素添加到任意两个元素的中间位置，添加元素操作只会改变前后元素的前后指针，指针将会指向添加的新元素，所以相比ArrayList的添加操作来说，LinkedList的性能优势明显。
删除元素
在LinkedList删除元素的操作中，我们首先要通过循环找到要删除的元素，如果要删除的位置处于List的前半段，就从前往后找;若其位置处于后半段，就从后往前找。
这样做的话，无论要删除较为靠前或较为靠后的元素都是非常高效的，但如果List拥有大量元素，移除的元素又在List的中间段，那效率相对来说会很低。
遍历元素
LinkedList的获取元素操作实现跟LinkedList的删除元素操作基本类似，通过分前后半段来循环查找到对应的元素，但是通过这种方式来查询元素是非常低效的，特别是在for循环遍历的情况下，每一次循环都会去遍历半个List。
所以在LinkedList循环遍历时，我们可以使用iterator方式迭代循环，直接拿到我们的元素，而不需要通过循环查找List。
分析测试
新增元素操作性能测试
测试用例源代码：
ArrayList：https://paste.ubuntu.com/p/gktBvjgMGk/ LinkedList：https://paste.ubuntu.com/p/3jQrY2XMPr/
测试结果：
通过这组测试，我们可以知道LinkedList添加元素的效率未必要高于ArrayList。
从集合头部位置添加元素由于ArrayList是数组实现的，在添加元素到数组头部的时候，需要对头部以后的数据进行复制重排，所以效率很低;
LinkedList是基于链表实现，在添加元素的时候，首先会通过循环查找到添加元素的位置，如果要添加的位置处于List的前半段，就从前往后找;若其位置处于后半段，就从后往前找，因此LinkedList添加元素到头部是非常高效的。
从集合中间位置位置添加元素ArrayList在添加元素到数组中间时，同样有部分数据需要复制重排，效率也不是很高;
LinkedList将元素添加到中间位置，是添加元素最低效率的，因为靠近中间位置，在添加元素之前的循环查找是遍历元素最多的操作。
从集合尾部位置添加元素而在添加元素到尾部的操作中，在没有扩容的情况下，ArrayList的效率要高于LinkedList。
这是因为ArrayList在添加元素到尾部的时候，不需要复制重排数据，效率非常高。
LinkedList虽然也不用循环查找元素，但LinkedList中多了new对象以及变换指针指向对象的过程，所以效率要低于ArrayList。
注意：这是排除动态扩容数组容量的情况下进行的测试，如果有动态扩容的情况，ArrayList的效率也会降低。删除元素操作性能测试
ArrayList和LinkedList删除元素操作测试的结果和添加元素操作测试的结果很接近!
结论：如果需要在List的头部进行大量的插入、删除操作，那么直接选择LinkedList。否则，ArrayList即可。
遍历元素操作性能测试
测试用例源代码：
ArrayList：https://paste.ubuntu.com/p/ZNWc9H2pYm/ LinkedList：https://paste.ubuntu.com/p/xSk4nHDHvN/
测试结果：
我们可以看到，LinkedList的for循环性能是最差的，而ArrayList的for循环性能是最好的。
这是因为LinkedList基于链表实现的，在使用for循环的时候，每一次for循环都会去遍历半个List，所以严重影响了遍历的效率;ArrayList则是基于数组实现的，并且实现了RandomAccess接口标志，意味着ArrayList可以实现快速随机访问，所以for循环效率非常高。
LinkedList的迭代循环遍历和ArrayList的迭代循环遍历性能相当，也不会太差，所以在遍历LinkedList时，我们要切忌使用for循环遍历。
- 上一篇：ubuntu系统如何切换root用户身份 本文将为大家介绍ubuntu切换root用户帐号方法，希望对大家有所帮助！说明：小编的这个建议只适合于10.10之前版本的ubuntu系统，后面的11.04，11.10。。。14.04系统因为采用的默认桌面不同，所以本经验不适用，若要使用，那么请安装GNOME桌面方法/步骤1、按照下面的方式打开终端工具，或者使用终端工具的快捷键Ctrl + Alt +T 打开终端2、终端工具打开后如下图所示，我们的操作就在这个窗口中进行3、切换root用户的的方式一执行命令 sudo su执行上面点命令后会要求我们输入当前我们的密码4、输入密码后就切换到root用户了，我们可以看到当前的用户已经是root了5、退出root用户的方法在切换成root用户后，我们只要执行exit命令就退出root用户账号了6、切换为root用户账户的第二种方法执行sudo -i命令也可以将当前用户有普通用户切换到root用户模式中7、执行命令后，一般也要求输入我们的密码，小编这里因为是刚切换到root用户不久，所以系统不要求输入密码，一般在10分钟之内我们来回切换root用户时系统不会提示输入密码，之后会要求我们再次输入密码END以上就是ubuntu切换root用户帐号方法介绍，希望对大家有一定的帮助！
- 下一篇：1. 下载Sublime Text 2在官网下载对应系统位数的版本，从压缩包中提取出源代码，解压后文件夹中的sublime_text双击即可直接运行。2. 建立快捷链接将整个文件夹Sublime拷贝到 /opt 目录下，然后打开终端输入以下命令为sublime_text建立链接：复制代码代码如下:复制代码代码如下:复制代码代码如下:复制代码代码如下:复制代码代码如下:import urllib2,os;pf=Package Control.sublime-package;ipp=sublime.installed_packages_path();os.makedirs(ipp) if not os.path.exists(ipp) else None;open(os.path.join(ipp,pf),wb).write(urllib2.urlopen(http://sublime.wbond.net/+pf.replace( ,%20)).read())重启Sublime Text 2，假如在Perferences->package settings中看到package control这一项，则安装成功。6. 使用Package Control安装插件按下Ctrl+Shift+P调出命令面板，输入install 调出 Install Package 选项并回车，然后在列表中选中要安装的插件。
- 华为天际通（探索5G通信时代的智能互联未来）
- 怎么换新的网站域名？域名更换有什么技巧？
- 域名转出如何操作？域名转出流程介绍
- 域名转入后年限未增加的原因是什么？
- 探索AKGN20NC耳机的音质和功能（一款耳机的卓越音质和令人惊叹的功能）
- 一个网站多个域名好吗？一个网站多少域名合适？
- 现在域名需要实名认证吗？国内域名实名到底什么目的？
- 企业转型互联网需要域名吗？企业转型需要怎样的域名？
- 假如你想清理你的 Ubuntu 主机，你可以按照以下的一些简单步骤来移除所有不需要的垃圾文件。移除多余软件包这又是一个内置功能，但这次我们不必使用新得立包管理软件(Synaptic Package Manager)，而是在终端中达到目的。现在，在终端窗口中键入如下命令：复制代码代码如下:sudo apt-get autoclean这便激活了包清除命令。这个命令所做的工作是： 自动清除那些当你安装或升级程序时系统所缓存的 .deb 包(即清除 /var/cache/apt/archives 目录，不过只清理过时的包)。假如需要使用清除命令，只需在终端窗口中键入以下命令：复制代码代码如下:sudo apt-get clean然后你就可以使用自动移除命令。这个命令所做的工作是：清除那些 在系统中被某个已经卸载的软件 作为依赖所安装的软件包。要使用自动移除命令，在终端窗口中键入以下命令：复制代码代码如下:sudo apt-get autoremove移除不需要的本地化数据为达到此目的，我们需要安装 localepurge 软件，它将自动移除一些不需要的本地化数据（LCTT 译注：即各种语言翻译）。这个软件是一个简单的脚本，它将从那些不再需要的本地化文件和本地化联机手册( man pages ) 所占用的空间中回收磁盘空间。这个软件将在任何 apt 安装命令运行时 被自动激活。在 Ubuntu 中安装 localepurge：复制代码代码如下:sudo apt-get install localepurge在通过 apt-get install 安装任意软件后， localepurge 将移除所有不是使用你系统中所设定语言的翻译文件和翻译的联机手册。假如你想设置 localepurge，你需要编辑 /ect/locale.nopurge 文件。根据你已经安装的软件，这将为你节省几兆的磁盘空间。例子：假如我试着使用 apt-get 来安装 dicus软件：复制代码代码如下:sudo apt-get install discus在软件安装完毕之后，你将看到如下提示：复制代码代码如下:localepurge: Disk space freed in /usr/share/locale: 41860K移除孤包假如你想移除孤包，你需要安装 deborphan 软件：在 Ubuntu 中安装 deborphan :复制代码代码如下:sudo apt-get install deborphan使用 deborphan，打开终端并键入如下命令即可:复制代码代码如下:sudo deborphan | xargs sudo apt-get -y remove --purge使用 GtkOrphan 来移除孤包GtkOrphan (一个针对 debian 系发行版本的 Perl/Gtk2 应用) 是一个分析用户安装过程状态并查找孤立库文件的图形化工具，它为 deborphan 提供了一个 GUI 前端，并具备移除软件包的功能。在 Ubuntu 中安装 GtkOrphan，打开终端并运行如下命令：复制代码代码如下:sudo apt-get install gtkorphan一张截图使用 Wajig 移除孤包Wajig是 Debian 包管理系统中一个简单的软件包管理前端。它将 apt、apt-cache、 dpkg、 /etc/init.d 中的脚本等 通过一个单一命令集成在一起，它的设计初衷是使用简单和为它的所有功能提供丰富的文档。通过适当的 sudo配置，大多数（假如不是全部）的软件包安装和创建等任务可以通过一个用户 shell 来完成。Wajig 也适用于一般的系统管理。另外，一个 Gnome GUI 命令 gjig也被囊括在这个软件包之中。在 Ubuntu 中安装 Wajig，打开终端并运行如下命令：复制代码代码如下:sudo apt-get install wajigDebfoster --- 跟踪你在安装过程中的操作debfoster 将会维护一个列有被明确需要安装的软件包的列表，但不包括那些作为某个软件的依赖而被安装的软件包。参数是完全可选的，你甚至可以使得在 dpkg 和/或 apt-get 每次运行之后马上激活 debfoster 。另外，你还可以在命令行中使用 debfoster 来安装或移除某些特定的软件包。那些后缀为 --- 的软件包将会被移除，而没有后缀的软件包将会被安装。假如一个新的软件包或 debfoster 注意到作为某个软件包的依赖的软件包是一个孤包，则 debfoster 将会询问你下一步如何操作。若你决定保留这个孤包， debfoster 将只会进行记录并继续安装过程；若你觉得这个软件包不足以引起你的兴趣，在 debfoster 询问这个问题后，它将移除这个软件包。进一步的，假如你的决定使得其他的软件包变为孤包，更多的提问将会接踵而来。在 Ubuntu 中安装 debfoster，打开终端并运行如下命令：复制代码代码如下:sudo apt-get install debfoster使用 debfoster为了创建一个初始跟踪文件，可以使用如下命令：复制代码代码如下:sudo debfoster -q你总可以编辑 /var/lib/debfoster/keepers 文件，来定义那些你想留在系统中的软件包。为了编辑这个文件，可以键入：复制代码代码如下:sudo vi /var/lib/debfoster/keepers要强制使 debfoster 去移除所有没有被列在上面这个文件的软件包，或安装作为某些列在这个文件中的软件包的依赖，它也同时会添加所有在这个列表中没有被安装的软件包。若要根据这个列表来执行相关操作，只需执行：复制代码代码如下:sudo debfoster -f若需要跟踪你新安装的软件包，你需要时不时地执行如下命令：复制代码代码如下:sudo debfosterxdiskusage -- 查看你的硬盘空间都去哪儿了图形化地展示磁盘使用情况的 du。xdiskusage 是一个用户友好型的程序，它将为你展示你所有磁盘的使用情况。 它是在 Phillip C. Dykstra 所写的 “xdu” 程序的基础上设计的。做了一些修改以使得它可以为你运行 “du”命令，并显示磁盘的剩余空间，并且假如你想清晰地了解你的磁盘空间都去哪儿了，它还可以生成一个 PostScript 格式的名为 display.xdiskusage 的文件。在 Ubuntu 中安装 xdiskusage，只需使用如下命令：复制代码代码如下:sudo apt-get install xdiskusage若你想打开这个应用，你需要使用如下命令：复制代码代码如下: sudo xdiskusage一旦这个应用被打开，你将看到如下图所示的界面：BleachbitBleachBit 能快速地释放磁盘空间并不知疲倦地保护你的隐私。它可以释放缓存，删除 cookie，清除 Internet 上网历史，粉碎临时文件，删除日志，丢弃你所不知道存在何处的垃圾。为 Linux 和 Windows 系统而设计，它支持擦除清理数以千计的应用程序，如 Firefox, Internet Explorer, Adobe Flash, Google Chrome, Opera, Safari 等等。除了简单地删除文件，BleachBit 还包括许多高级功能，诸如粉碎文件以防止恢复，擦除磁盘空间来隐藏被其他应用程序所删除文件的痕迹，为火狐“除尘”，使其速度更快等。比免费更好，BleachBit 是一个开源软件。在 Ubuntu 中安装 Bleachbit，打开终端并运行如下命令：复制代码代码如下:sudo apt-get install bleachbit一张截图
- 现在域名需要实名认证吗？国内域名实名到底什么目的？
- Copyright © 2025 Powered by ArrayList和LinkedList使用不当，性能差距会如此之大！,码上建站 滇ICP备2023006006号-47sitemap