ArrayList 和LinkedList的区别比较

前言

‌ArrayList和LinkedList的主要区别在于它们的底层数据结构、性能特点以及适用场景。‌ArrayList和LinkedList从名字分析，他们一个是Array（动态数组）的数据结构，一个是Linked（链表）的数据结构，此外，他们两个都是对List接口的实现。前者是数组队列，相当于动态数组；后者为双向链表结构，也可当作堆栈、队列、双端队列。

一、底层数据结构

‌ArrayList‌：基于动态数组实现。它维护一个Object类型的数组来存储元素，可以根据需要自动扩展容量。当元素数量超过当前容量时，ArrayList会进行扩容操作，通常是将现有元素复制到一个新的更大数组中‌。 

‌LinkedList‌：基于双向链表实现。每个节点包含存储的元素、指向前一个节点的引用和指向下一个节点的引用。LinkedList不需要预先分配固定大小的空间，可以在链表的头部或尾部灵活地添加或删除元素‌。

二、性能特点

2‌.1 查询性能‌：

ArrayList‌：通过索引直接访问元素，查询速度非常快，时间复杂度为O(1)。适合需要频繁访问特定‌位置数据的场景‌。

LinkedList‌：由于需要遍历链表来找到指定索引的元素，查询速度较慢，时间复杂度为O(n)‌。

2.2 添加和删除性能‌：

‌ArrayList‌：在列表中间插入或删除元素时，需要移动后续的所有元素，时间复杂度为O(n)。因此，在列表中间进行添加或删除操作时，LinkedList通常更快‌。

LinkedList‌：在头部或尾部添加或删除元素时，只需更改指针引用，时间复杂度为O(1)，因此在这些位置进行操作时更快‌。

三、空间和耗时效率对比

从利用效率来看，ArrayList自由性较低，因为它需要手动的设置固定大小的变化，但是他的使用比较方便，只需要创建，然后添加数据，通过调用下标进行使用；而LinkedList自由性较高，能够动态的数据量的变化而变化，但是他不便于使用。

ArrayList主要的空间开销在于需要在IList列表预留一定空间；而LinkedList主要空间开销在于需要存储节点信息以及结点指针信息。

ArrayList想要在指定位置插入或删除元素时，主要耗时的是 System.arraycopy 动作，会移动 index 后面所有的元素；LinkedList 主耗时的是要先通过 for 循环找到 index，然后直接插入或删除。这就导致了两者并非一定谁快谁慢。 主要有两个因素决定他们的效率，插入的数据量和插入的位置。

LinkedList需要更多的内存，因为ArrayList的每个索引的位置是实际的数据，而LinkedList中的每个节点中存储的是实际的数据和前后节点的位置。

四、ArrayList 扩容问题

ArrayList 使用一个内置的数组来存储元素，这个数组的起始容量是 10，当数组需要增长时，新的容量按如下公式获得：新容量=(旧容量*3)/2+1，也就是说每一次容量大概会增长50%。这就意味着，如果你有一个包含大量元素的 ArrayList 对象，那么最终将有很大的空间会被浪费掉，这个浪费是由ArrayList的工作方式本身造成的。如果没有足够的空间来存放新的元素，数组将不得不被重新进行分配以便能够增加新的元素。对数组进行重新分配，将会导致性能急剧下降。

五、ArrayList随机访问比LinkedList快的原因

ArrayList从原理上就是数据结构中的数组，也就是内存中的一片空间，这意味着，当我get(index)的时候，我可以根据数组的首地址+偏移量，直接计算出我想访问的第index元素在内存中的位置；而LinkedList可以简单理解为数据结构中的链表，在内存中开辟的不是一段连续的空间，而是每个元素有一个元素和下一个元素地址这样的内存结构，当get(index)时，只能从首元素开始，依次获取下一个元素的地址。上面已经说过，用时间复杂度来表示的话，ArrayList的get(index)是O(1)，而LinkedList是O(n)。

我们编写代码对比测试，说明两者的性能：

1. 定义抽象类，作为List接口的测试，并定义有测试方法

//定义内部抽象类，作为List测试。
private abstract static class Tester {String name;int size;Tester(String name, int size) {this.name = name;this.size = size;}//定义抽象方法abstract void test(List a);}

2. 定义一个测试的数组,分别存储获取、遍历、插入和删除的方法

private static final int LOOP_COUNTS = 1000;private static Tester[] tests = {//一个测试数组，存储get(随机取)、iteration(顺序遍历)、insert(中间插入)、remove(随机删除)new Tester("get", 500) {void test(List a) {for (int i = 0; i < LOOP_COUNTS; i++) {for (int j = 0; j < a.size(); j++) {a.get(j);}}}},new Tester("iteration", 500) {void test(List a) {for (int i = 0; i < LOOP_COUNTS; i++) {Iterator it = a.iterator();while (it.hasNext()) {it.next();}}}},new Tester("insert", 2000) {void test(List a) {int half = a.size() / 2;String s = "test";ListIterator it = a.listIterator(half);for (int i = 0; i < size * 10; i++) {it.add(s);}}},new Tester("remove", 5000) {void test(List a) {ListIterator it = a.listIterator(3);while (it.hasNext()) {it.next();it.remove();}}}};

 3. 编写测试方法

public static void test(List a) {//输出测试的类名称System.out.println("Testing for --" + a.getClass().getName());for (int i = 0; i < tests.length; i++) {fill(a, tests[i].size);//填充空集合System.out.print(tests[i].name);long t1 = System.currentTimeMillis();tests[i].test(a);//进行测试long t2 = System.currentTimeMillis();System.out.print("花费时间:" + (t2 - t1) + " ms ，");}}public static Collection fill(Collection c, int size) {for (int i = 0; i < size; i++) {c.add(Integer.toString(i));}return c;}

4. 调用ArrayList和LinkedList的方法

public static void main(String[] args) {test(new ArrayList());System.out.println();test(new LinkedList());}

 5. 运行结果

六、适用场景

‌ArrayList‌：适合需要频繁访问特定位置数据的场景，如排行榜、购物车列表等。由于扩容机制的存在，建议在创建时指定初始容量以减少扩容次数‌。

‌LinkedList‌：适合需要频繁在列表开头、中间或末尾进行添加和删除操作的场景。由于其链表结构，插入和删除操作更为高效‌。

总之， 它们的适用场景：Array数组，查找快，插入删除慢。 适用于频繁查找和修改的场景。Linked链表，插入删除快，查找修改慢。适用于频繁添加和删除的场景。