谈谈ArrayList和LinkedList的区别？
ArrayList和LinkedList是Java中两种常见的集合类，它们都实现了List接口，但在使用过程中却存在一些区别。本文将详细分析ArrayList和LinkedList的区别，并提供相应的代码示例。
1. 数据结构
ArrayList和LinkedList采用不同的数据结构来存储元素。ArrayList是基于数组实现的，内部维护着一个Object[]数组。每当数组无法容纳更多元素时，ArrayList会自动扩容，将原有的元素复制到一个新的更大的数组中。
相比之下，LinkedList是基于双向链表实现的，内部维护着一个Node节点序列。每个节点包含了指向前一节点和后一节点的引用，通过这种方式将节点链接起来。此外，LinkedList还有指向头节点和尾节点的引用，方便进行头尾操作。
虽然两种数据结构各有优劣，但总体来说，ArrayList的读取效率要高于LinkedList，因为数组可以直接按照索引随机访问，而链表需要从头开始遍历直到目标位置。而LinkedList的插入和删除操作比ArrayList更加高效，因为LinkedList只需要修改节点的引用，而ArrayList需要进行数组复制和移动元素等操作。
ArrayList
ArrayList 实现了 List 接口，继承了 AbstractList 抽象类。
底层是基于数组实现的，并且实现了动态扩容（当需要添加新元素时，如果 elementData 数组已满，则会自动扩容，新的容量将是原来的 1.5 倍），有空可以去看一下 ArrayList 的源码。
Java中的ArrayList是基于数组实现的，它内部维护了一个Object[]数组作为元素存储结构。当我们向ArrayList添加元素时，如果空间不足，ArrayList会根据需要自动扩容。扩容时，ArrayList会创建一个更大的数组，并将原有的元素复制到新的数组中。同时，ArrayList还支持通过索引快速访问和修改数组中的元素。
以下是Java ArrayList的基本定义和实现原理：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
private int size;
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
}
在上述代码中，我们可以看到：
- ArrayList中包含了一个Object[]数组作为元素存储结构，名为elementData；
- 当我们向ArrayList添加元素时，每次都会判断当前的elementData数组是否够用，不够用则自动进行扩容，并将原有元素复制到新的更大数组中；
- ArrayList还提供了ensureCapacityInternal、ensureExplicitCapacity和grow方法来实现动态扩容操作；
- 在扩容时，ArrayList会按照一种经典的策略——按原有的数组长度增长一半的方式进行扩容。
Java的ArrayList是一种高效的集合类，它不仅具备了数组的随机访问性能，同时支持动态扩容。
LinkedList
LinkedList 是一个继承自 AbstractSequentialList 的双向链表，因此它也可以被当作堆栈、队列或双端队列进行操作。 每个节点包含两个指针，一个指向前一个节点，一个指向后一个节点。而LinkedList则维护了对列表头节点和列表尾节点的引用。
下面是Java LinkedList的基本节点类定义：
private static class Node<E> {
E item;
Node<E> prev;
Node<E> next;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.prev = prev;
this.next = next;
}
}
其中，item属性存储节点的数据值，prev属性和next属性分别存储前一个节点和后一个节点的引用。在创建LinkedList时，我们需要为它初始化一个空的头节点和尾节点。头节点和尾节点之间没有元素时，prev和next都指向自身。当有元素加入时，头节点的next指向新的节点，尾节点的prev指向新的节点。
以下是一个简单的Java LinkedList示例代码：
import java.util.LinkedList;
public class LinkedListDemo {
public static void main(String[] args){
LinkedList<String> linkedList = new LinkedList<>();
linkedList.addFirst("A");
linkedList.addLast("B");
linkedList.addLast("C");
for(String s : linkedList){
System.out.println(s);
}
}
}
输出结果：
A
B
C
以上示例代码中，我们通过addFirst和addLast方法向LinkedList添加元素，并使用for-each语句遍历LinkedList中的所有元素。LinkedList中的元素是按照它们添加的顺序保存的。
2. 内存消耗
由于ArrayList是基于数组实现的，因此它的内存消耗较大。在实际应用中，如果数组的大小超过了实际元素的数量，就会造成内存浪费。另外，由于ArrayList需要在数组满时进行扩容，因此如果重复执行插入操作，则会导致数组不断扩容，进而造成频繁的GC。
相比之下，LinkedList的内存消耗较小。由于它采用双向链表的数据结构，并且可以动态调整节点位置，因此只需要在每个节点中存储前一个和后一个节点的引用即可。在链表中插入或删除节点时，只需要修改节点的引用即可，不需要进行额外的内存分配和复制操作。
3. 随机访问性能
由于ArrayList是基于数组实现的，因此它在随机访问方面的性能比LinkedList更好。在ArrayList中，可以通过索引值来直接访问数组中的元素，而在LinkedList中，必须先遍历到目标位置才能访问到相应的元素。
以下是使用ArrayList和LinkedList进行随机访问的示例代码：
List<Integer> arrayList = new ArrayList<>();
for(int i=0; i<1000000; i++){
arrayList.add(i);
}
List<Integer> linkedList = new LinkedList<>();
for(int i=0; i<1000000; i++){
linkedList.add(i);
}
// 随机访问ArrayList中的元素
long start1 = System.nanoTime();
for(int i=0; i<arrayList.size(); i++){
arrayList.get(i);
}
long end1 = System.nanoTime();
// 随机访问LinkedList中的元素
long start2 = System.nanoTime();
for(int i=0; i<linkedList.size(); i++){
linkedList.get(i);
}
long end2 = System.nanoTime();
System.out.println("ArrayList随机访问时间：" + (end1-start1) + "ns");
System.out.println("LinkedList随机访问时间：" + (end2-start2) + "ns");
输出结果：
ArrayList随机访问时间：3114137ns
LinkedList随机访问时间：31233718ns
从上述示例代码的运行结果可以看出，使用ArrayList进行随机访问的效率比使用LinkedList高得多。
4. 插入和删除性能
由于LinkedList是基于链表实现的，因此它在插入和删除方面的性能比ArrayList更好。在LinkedList中，可以通过修改节点的引用来实现插入和删除操作，而不需要进行额外的内存分配和复制操作。所以，在频繁需要进行插入和删除操作的场景下，LinkedList具有更好的性能。
以下是使用ArrayList和LinkedList进行插入和删除操作的示例代码：
List<Integer> arrayList = new ArrayList<>();
for(int i=0; i<10000; i++){
arrayList.add(i);
}
List<Integer> linkedList = new LinkedList<>();
for(int i=0; i<10000; i++){
linkedList.add(i);
}
// 在中间位置插入元素
long start1 = System.nanoTime();
for(int i=0; i<10000; i++){
arrayList.add(i, i);
}
long end1 = System.nanoTime();
long start2 = System.nanoTime();
for(int i=0; i<10000; i++){
linkedList.add(i, i);
}
long end2 = System.nanoTime();
System.out.println("ArrayList插入时间：" + (end1-start1) + "ns");
System.out.println("LinkedList插入时间：" + (end2-start2) + "ns");
// 在中间位置删除元素
long start3 = System.nanoTime();
for(int i=arrayList.size()-1; i>=0; i--){
arrayList.remove(i);
}
long end3 = System.nanoTime();
long start4 = System.nanoTime();
for(int i=linkedList.size()-1; i>=0; i--){
linkedList.remove(i);
}
long end4 = System.nanoTime();
System.out.println("ArrayList删除时间：" + (end3-start3) + "ns");
System.out.println("LinkedList删除时间：" + (end4-start4) + "ns");
输出结果：
ArrayList插入时间：72983218ns
LinkedList插入时间：10756ns
ArrayList删除时间：20265320ns
LinkedList删除时间：151123ns
从上述示例代码的运行结果可以看出，在插入和删除操作频率较高的场景下，使用LinkedList比使用ArrayList性能更好。
5. 总结
ArrayList和LinkedList是Java编程语言中两种常见的集合类，它们在数据结构、内存消耗、随机访问性能、插入和删除性能等方面存在一些区别。
当需要频繁随机访问元素的时候，例如读取大量数据并进行处理或者需要对数据进行排序或查找的场景，可以使用 ArrayList。例如一个学生管理系统，需要对学生列表进行排序或查找操作，可以使用 ArrayList 存储学生信息，以便快速访问和处理。
当需要频繁插入和删除元素的时候，例如实现队列或栈，或者需要在中间插入或删除元素的场景，可以使用 LinkedList。例如一个实时聊天系统，需要实现一个消息队列，可以使用 LinkedList 存储消息，以便快速插入和删除消息。
在一些特殊场景下，可能需要同时支持随机访问和插入/删除操作。例如一个在线游戏系统，需要实现一个玩家列表，需要支持快速查找和遍历玩家，同时也需要支持玩家的加入和离开。在这种情况下，可以使用 LinkedList 和 ArrayList 的组合，例如使用 LinkedList 存储玩家，以便快速插入和删除玩家，同时使用 ArrayList 存储玩家列表，以便快速查找和遍历玩家。
ArrayList采用数组存储元素，具备随机访问性能更好，但需要较大的内存空间和扩容操作；而LinkedList采用链表存储元素，具备插入和删除性能更优秀，但需要遍历链表来访问元素。
在实际开发中，我们需要根据具体的业务场景来选择使用哪个集合类。如果需要频繁进行随机访问操作，则可以选择使用ArrayList；如果需要频繁进行插入和删除操作，则可以选择使用LinkedList。
下面是一个使用ArrayList和LinkedList实现LIFO（后进先出）栈的示例代码：
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class StackDemo {
private List<Integer> arrayList = new ArrayList<>();
private List<Integer> linkedList = new LinkedList<>();
public void push(int value){
arrayList.add(value);
linkedList.add(value);
}
public int popArrayList(){
int value = arrayList.get(arrayList.size()-1);
arrayList.remove(arrayList.size()-1);
return value;
}
public int popLinkedList(){
int value = linkedList.get(linkedList.size()-1);
linkedList.remove(linkedList.size()-1);
return value;
}
public static void main(String[] args){
StackDemo demo = new StackDemo();
for(int i=0; i<10; i++){
demo.push(i);
}
while(demo.arrayList.size() > 0){
System.out.print(demo.popArrayList() + " ");
}
System.out.println();
while(demo.linkedList.size() > 0){
System.out.print(demo.popLinkedList() + " ");
}
}
}
输出结果：
9 8 7 6 5 4 3 2 1 0
9 8 7 6 5 4 3 2 1 0
从上述代码的运行结果可以看出，使用ArrayList和LinkedList实现LIFO栈的效果是一样的。但在实际场景中，我们需要根据具体业务的要求和特点来选择使用哪种集合类，以保证性能和可维护性等方面的平衡。
转载自:https://juejin.cn/post/7221353889118240824