`ArrayList` 与 `LinkedList`：底层实现、性能特点与选择场景

ArrayList与LinkedList：一场关于效率与灵活性的“爱恨情仇”

各位看官，大家好！今天我们要聊聊Java集合框架中两位“性格迥异”的选手：ArrayList和LinkedList。它们都是List接口的实现类，都能存储一堆元素，但底层实现和性能特点却大相径庭，这就导致了它们各自擅长的“战场”也不一样。

让我们一起深入了解这对“欢喜冤家”，看看它们是如何在不同的场景下各显神通，以及我们该如何根据实际需求做出明智的选择。

一、底层实现：一场关于“连续”与“分散”的哲学探讨

要理解ArrayList和LinkedList的区别，首先要从它们的底层实现说起。

ArrayList：连续存储的“拥趸”

ArrayList的底层是一个动态数组。想象一下，你有一排房间，每个房间都紧挨着，编号从0开始。ArrayList就像这样一排房间，每个房间（数组的每个元素）都存储着一个对象引用。
```
// ArrayList 底层数组的声明
transient Object[] elementData; // non-private to simplify nested class access
```
当ArrayList的空间不够用时，它会创建一个更大的数组，并将所有元素复制到新数组中。这就像你觉得房间不够住了，于是买了一栋更大的房子，把所有家具都搬过去。
```
// ArrayList 扩容的实现
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容为原来的1.5倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}
```
由于元素在内存中是连续存储的，所以可以通过索引直接访问任何元素，就像你知道房间号就能直接找到对应的房间一样。
LinkedList：分散存储的“浪漫主义者”

LinkedList的底层是一个双向链表。想象一下，你有一堆房间，但这些房间不是紧挨着的，而是分散在各处。每个房间（链表的每个节点）除了存储对象引用外，还存储着指向前一个房间和后一个房间的“指针”。
```
// LinkedList 节点的定义
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;
    }
}
```
要找到某个元素，你需要从链表的头或尾开始，沿着“指针”一个一个地遍历，直到找到目标元素。这就像你要找到某个朋友，你需要先找到他的一个朋友，然后问他朋友是否知道你要找的人在哪里，直到最终找到你的朋友。

二、性能特点：一场关于“速度”与“灵活”的较量

底层实现的差异直接影响了ArrayList和LinkedList的性能特点。

操作	ArrayList	LinkedList	说明
随机访问（get/set）	O(1)	O(n)	`ArrayList`基于数组，可以通过索引直接访问，时间复杂度为O(1)。`LinkedList`需要从头或尾遍历，时间复杂度为O(n)。
插入/删除元素（中间位置）	O(n)	O(1)	`ArrayList`插入/删除元素需要移动后续元素，时间复杂度为O(n)。`LinkedList`只需要修改相邻节点的指针，时间复杂度为O(1)。
插入/删除元素（首尾位置）	O(1) / O(n)	O(1)	`ArrayList`在尾部插入/删除元素的时间复杂度为O(1)，在头部插入/删除元素需要移动所有元素，时间复杂度为O(n)。`LinkedList`在首尾插入/删除元素的时间复杂度为O(1)。
查找元素（contains）	O(n)	O(n)	两者都需要遍历列表，时间复杂度都为O(n)。
空间占用	相对较小	相对较大	`ArrayList`的空间占用相对较小，因为只需要存储元素本身。`LinkedList`需要存储节点信息（元素、前驱指针、后继指针），空间占用相对较大。

ArrayList：随机访问的“速度之王”

由于ArrayList基于数组，可以通过索引直接访问任何元素，所以随机访问速度非常快，时间复杂度为O(1)。这就像你知道房间号就能直接找到对应的房间一样，效率非常高。

// ArrayList 随机访问示例
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("Java");
arrayList.add("Python");
arrayList.add("C++");

String element = arrayList.get(1); // 获取索引为1的元素，即 "Python"
System.out.println(element); // 输出：Python

LinkedList：插入/删除的“灵活大师”

LinkedList在插入/删除元素时，只需要修改相邻节点的指针，而不需要移动其他元素，所以插入/删除速度非常快，时间复杂度为O(1)。这就像你要在两个房间之间增加一个房间，只需要修改连接这三个房间的“指针”就可以了，不需要移动其他房间。
```
// LinkedList 插入/删除示例
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("Java");
linkedList.add("Python");
linkedList.add("C++");

linkedList.add(1, "JavaScript"); // 在索引为1的位置插入 "JavaScript"
linkedList.remove(2); // 删除索引为2的元素，即 "Python"
System.out.println(linkedList); // 输出：[Java, JavaScript, C++]
```
但是，LinkedList要找到某个元素，需要从头或尾开始遍历，所以随机访问速度较慢，时间复杂度为O(n)。这就像你要找到某个朋友，你需要先找到他的一个朋友，然后问他朋友是否知道你要找的人在哪里，直到最终找到你的朋友，效率比较低。

三、选择场景：一场关于“需求”与“权衡”的艺术

了解了ArrayList和LinkedList的底层实现和性能特点，我们就可以根据实际需求做出明智的选择。

优先选择ArrayList的场景：
- 频繁进行随机访问： 如果你需要经常通过索引访问元素，那么ArrayList是最佳选择，因为它具有O(1)的随机访问速度。
- 元素数量相对固定： 如果你的列表元素数量相对固定，不需要频繁进行插入/删除操作，那么ArrayList也是一个不错的选择。
- 对内存占用要求较高： ArrayList的空间占用相对较小，如果对内存占用要求较高，可以优先选择ArrayList。
示例：
- 存储一组固定的配置信息，需要频繁读取这些配置信息。
- 实现一个简单的缓存，需要快速访问缓存中的数据。
- 存储一组用户ID，需要根据用户ID快速查找用户信息。
```
// 示例：存储一组固定的配置信息
ArrayList<String> configList = new ArrayList<>();
configList.add("database.url=localhost:3306");
configList.add("database.username=root");
configList.add("database.password=123456");

// 快速读取配置信息
String url = configList.get(0); // 获取数据库URL
System.out.println(url); // 输出：database.url=localhost:3306
```
优先选择LinkedList的场景：
- 频繁进行插入/删除操作： 如果你需要经常在列表的中间位置插入/删除元素，那么LinkedList是最佳选择，因为它具有O(1)的插入/删除速度。
- 元素数量变化频繁： 如果你的列表元素数量变化频繁，需要经常进行插入/删除操作，那么LinkedList也是一个不错的选择。
- 对随机访问性能要求不高： 如果你对随机访问性能要求不高，可以接受O(n)的随机访问速度，那么LinkedList也是可以考虑的。
示例：
- 实现一个消息队列，需要频繁添加和删除消息。
- 实现一个撤销/重做功能，需要记录用户的操作历史。
- 实现一个文本编辑器，需要频繁插入/删除字符。
```
// 示例：实现一个消息队列
LinkedList<String> messageQueue = new LinkedList<>();

// 添加消息
messageQueue.add("Message 1");
messageQueue.add("Message 2");
messageQueue.add("Message 3");

// 删除消息
String message = messageQueue.removeFirst(); // 删除第一个消息
System.out.println(message); // 输出：Message 1
```

四、源码分析：更深入的理解

为了更深入地理解ArrayList和LinkedList，我们可以简单地分析一下它们的源码。这里我们主要关注一些关键的方法。

ArrayList的add(E e)方法：

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

这个方法首先会检查数组容量是否足够，如果不够，则进行扩容。然后将元素添加到数组的末尾，并将size加1。

LinkedList的add(E e)方法：
```
public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}
```
这个方法会在链表的末尾添加一个新节点。首先创建一个新节点，并将新节点的prev指针指向当前链表的最后一个节点。然后将新节点设置为链表的最后一个节点，并将原链表最后一个节点的next指针指向新节点。

ArrayList的get(int index)方法：

public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index, size));
}

@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

这个方法会直接通过索引访问数组中的元素，时间复杂度为O(1)。

LinkedList的get(int index)方法：

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index, size));
}

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

这个方法会首先检查索引是否合法，然后从链表的头或尾开始遍历，直到找到目标节点，时间复杂度为O(n)。

五、总结：选择适合自己的“武器”

ArrayList和LinkedList各有优缺点，没有绝对的“好”与“坏”，只有适合与不适合。选择哪种列表取决于你的具体需求。

如果你需要频繁进行随机访问，那么ArrayList是你的首选。
如果你需要频繁进行插入/删除操作，那么LinkedList更适合你。
如果你对性能要求不高，或者列表元素数量较少，那么ArrayList和LinkedList都可以选择。

希望通过本文的讲解，你能更深入地理解ArrayList和LinkedList，并在实际开发中做出明智的选择。记住，没有最好的工具，只有最适合的工具！

ArrayList与LinkedList：一场关于效率与灵活性的“爱恨情仇”

发表回复 取消回复

发表回复取消回复