深入剖析 Java 中 ArrayList 和 LinkedList 的区别

欢迎大家来到IT世界,在知识的湖畔探索吧!

ArrayList和LinkedList都是 Java 中常用的集合类，它们在很多方面存在差异，以下详细说明它们在添加、删除、查找元素方面的时间复杂度以及内存占用情况。

数据结构

1. ArrayList

ArrayList是基于动态数组实现的。它在内存中连续存储元素，可以通过索引快速访问和修改元素。

例如，假设有一个ArrayList存储了整数，ArrayList<Integer> list = new ArrayList<>(); list.add(10); list.add(20); list.add(30);，在内存中，这些整数是连续存储的，可以通过索引直接访问，比如list.get(1)可以快速获取到值为 20 的元素。

2. LinkedList

LinkedList是基于双向链表实现的。每个元素都包含指向前一个元素和后一个元素的引用，通过这些引用可以在链表中进行遍历和操作。

例如，对于LinkedList<Integer> linkedList = new LinkedList<>(); linkedList.add(10); linkedList.add(20); linkedList.add(30);，在内存中，每个元素都有对前后元素的引用，形成一个链表结构。

添加元素的时间复杂度

1. ArrayList

在末尾添加元素：时间复杂度为 O (1)。因为ArrayList在末尾添加元素时，只需要将新元素放入数组的下一个位置即可，不需要移动其他元素。

在中间添加元素：时间复杂度为 O (n)。如果要在ArrayList的中间位置插入一个元素，需要将插入位置后面的所有元素都向后移动一位，以腾出空间插入新元素。移动元素的数量取决于插入位置和数组的大小，平均来说，需要移动大约一半的元素，所以时间复杂度为 O (n)。

例如，在一个有 100 个元素的ArrayList中间插入一个新元素，可能需要将后面的 50 个元素依次向后移动一位。

2. LinkedList

在末尾添加元素：时间复杂度为 O (1)。只需要修改最后一个元素的下一个引用指向新元素，新元素的上一个引用指向原来的最后一个元素即可。

在中间添加元素：时间复杂度为 O (1)。只需要修改插入位置前后两个元素的引用，将新元素插入到它们之间。

例如，在一个有 100 个元素的LinkedList中间插入一个新元素，只需要修改前后两个元素的引用，将新元素插入到它们之间。

删除元素的时间复杂度

1. ArrayList

删除末尾元素：时间复杂度为 O (1)。直接删除数组的最后一个元素即可，不需要移动其他元素。

删除中间元素：时间复杂度为 O (n)。删除中间元素时，需要将删除位置后面的所有元素都向前移动一位，以填补删除的元素留下的空缺。移动元素的数量取决于删除位置和数组的大小，平均来说，需要移动大约一半的元素，所以时间复杂度为 O (n)。

例如，在一个有 100 个元素的ArrayList中间删除一个元素，可能需要将后面的 49 个元素依次向前移动一位。

2. LinkedList

删除末尾元素：时间复杂度为 O (n)。需要遍历到链表的末尾，找到最后一个元素，然后修改倒数第二个元素的下一个引用为 null。

删除中间元素：时间复杂度为 O (1)。只需要修改删除位置前后两个元素的引用，跳过要删除的元素即可。

例如，在一个有 100 个元素的LinkedList中间删除一个元素，只需要修改前后两个元素的引用，跳过要删除的元素。

查找元素的时间复杂度

1. ArrayList

随机访问查找：时间复杂度为 O (1)。由于ArrayList是基于数组实现的，可以通过索引直接访问任意位置的元素，所以随机访问查找的时间复杂度为 O (1)。

顺序查找：时间复杂度为 O (n)。如果不知道元素的索引，需要从头开始遍历数组，逐个比较元素，直到找到目标元素，所以顺序查找的时间复杂度为 O (n)。

例如，要查找一个有 100 个元素的ArrayList中的特定元素，如果知道元素的索引，可以直接通过索引访问，时间复杂度为 O (1)；如果不知道索引，需要遍历整个数组，时间复杂度为 O (n)。

2. LinkedList

随机访问查找：时间复杂度为 O (n)。由于LinkedList是基于链表实现的，不支持高效的随机访问。要查找特定位置的元素，需要从链表的头部或尾部开始遍历，直到找到目标元素，所以随机访问查找的时间复杂度为 O (n)。

顺序查找：时间复杂度为 O (n)。与随机访问查找类似，顺序查找也需要遍历链表，逐个比较元素，直到找到目标元素，所以时间复杂度为 O (n)。

例如，要查找一个有 100 个元素的LinkedList中的特定元素，无论是否知道元素的位置，都需要遍历链表，时间复杂度为 O (n)。

内存占用

1. ArrayList

ArrayList在内存中是连续存储的，因此可能会浪费一些空间，特别是在存储的元素数量较少时。但是，由于数组的连续存储特性，它可以更好地利用 CPU 缓存，提高访问速度。

例如，如果创建一个初始容量为 10 的ArrayList，但只存储了 3 个元素，那么剩下的 7 个位置就会被浪费。而且，当ArrayList需要扩容时，会创建一个新的更大的数组，并将原数组中的元素复制到新数组中，这也会带来一定的内存开销。

3. LinkedList

LinkedList每个元素都需要额外的空间来存储前后元素的引用，因此内存占用相对较高。但是，它可以更灵活地分配内存，不会像ArrayList那样在扩容时一次性分配大量的连续空间。

例如，对于存储相同数量的元素，LinkedList可能会比ArrayList占用更多的内存，因为每个元素都有额外的引用。而且，由于链表的节点在内存中可能不是连续存储的，所以可能会导致内存碎片的产生，影响内存的使用效率。

适用场景

1. ArrayList

适用于需要频繁进行随机访问，而插入和删除操作相对较少的场景。例如，存储和遍历一组数据，不需要频繁地在中间插入或删除元素。

例如，在一个游戏中，存储玩家的得分列表，只需要在末尾添加新的得分，然后遍历列表进行排序和显示，这种情况下使用ArrayList比较合适。

2. LinkedList

适用于需要频繁进行插入和删除操作，而随机访问较少的场景。例如，实现一个栈或队列数据结构，需要在两端进行插入和删除操作。

例如，在一个任务调度系统中，使用LinkedList作为任务队列，新任务可以在队列尾部插入，已完成的任务可以从队列头部删除。

ArrayList和LinkedList在添加、删除、查找元素方面的时间复杂度不同，内存占用情况也不同，适用场景也不同。在选择使用哪个集合类时，需要根据具体的需求来进行权衡。