LinkedList 简介

Java 中的 LinkedList 类实现了 List 接口和 Deque 接口。LinkedList 具有以下一些显著特性：

1. 元素按照插入顺序进行存储。
2. 支持存储重复元素。
3. 可以添加任意数量的 null 元素。

LinkedList 的内部实现

LinkedList 类包含一个名为 Node 的静态内部类，该类包含三个字段：

• item：存储当前节点的值。
• next：指向下一个节点的指针。
• prev：指向前一个节点的指针。

以下是 Node 类的代码实现：

1private static class Node<E> {
2    E item;
3    Node<E> next;
4    Node<E> prev;
5
6    Node(Node<E> prev, E element, Node<E> next) {
7        this.item = element;
8        this.next = next;
9        this.prev = prev;
10    }
11}

当向 LinkedList 添加一个元素时，会创建一个新的 Node 实例，并根据插入位置设置其 prev 和 next 指针。

当删除索引为 i 的节点时，索引为 i-1 的节点的 next 指针将指向索引为 i+1 的节点；同时，索引为 i+1 的节点的 prev 指针将指向索引为 i-1 的节点。

LinkedList 操作的时间复杂度

下面我们来看一下 LinkedList 各种操作的时间复杂度。

添加元素

在 LinkedList 中添加元素的时间复杂度为 $O(1)$。如果需要先查找插入位置，则查找过程的时间复杂度为 $O(n)$，但通常情况下元素是插入到链表头部或尾部，因此实际插入操作的时间复杂度为 $O(1)$。

与数组相比，LinkedList 最大的优势在于：当添加或删除元素时，不需要像数组那样移动其他元素，从而避免了整体数据的重新排列。

删除元素

如果已知待删除元素的位置，删除操作的时间复杂度为 $O(1)$。但如果需要先搜索再删除，则时间复杂度为 $O(n)$。

查找元素

查找某个元素的时间复杂度为 $O(n)$，因为在最坏情况下需要遍历整个 LinkedList 才能找到目标元素。

创建 LinkedList

创建 LinkedList 有两种方式：

使用无参构造函数

默认构造函数不接受任何参数，创建一个初始为空（大小为零）的 LinkedList。语法如下：

1List<Integer> list = new LinkedList<Integer>();

基于已有集合创建

也可以通过已有的 Collection 来创建 LinkedList。新创建的 LinkedList 将按原集合中的顺序包含所有元素。

1List<Integer> list = new LinkedList<Integer>(oldList);

向 LinkedList 插入元素

下面介绍几种常用的插入元素的方法。

在末尾插入单个元素

可以使用 add(E e) 或 addLast(E e) 方法将单个元素插入到链表末尾。addLast(E e) 没有返回值，而来自 List 接口的 add(E e) 返回 boolean（恒为 true）。

在开头插入单个元素

使用 addFirst(E e) 方法可将元素插入到链表的起始位置。

在指定索引处插入元素

使用 add(int index, E element) 方法可在指定索引位置插入元素。索引必须满足 0 ≤ index ≤ size（即可以等于链表大小，表示追加到末尾），否则会抛出 IndexOutOfBoundsException 异常。

从另一个集合批量插入多个元素

若有一个 Collection，并希望将其所有元素添加到 LinkedList 末尾，可使用 addAll(Collection c) 方法。

1list.addAll(anotherList)

在指定位置批量插入另一个集合的元素

若要将某个集合的所有元素插入到 LinkedList 的指定位置，可使用 addAll(int index, Collection c) 方法。该方法会从指定位置开始，依次插入集合中的所有元素。

1list.addAll(3, anotherList)

1import java.util.ArrayList;
2import java.util.LinkedList;
3import java.util.List;
4
5public class LinkedListDemo {
6
7    public static void main(String args[]) {
8        LinkedList<Integer> linkedList = new LinkedList<>();
9
10        linkedList.add(1); // 将 1 添加到列表中
11        linkedList.add(2); // 将 2 添加到列表末尾
12        linkedList.addLast(3); // 将 3 添加到列表末尾
13        System.out.println(linkedList);
14
15        linkedList.addFirst(10); // 将 10 添加到列表开头
16        System.out.println(linkedList);
17
18        linkedList.add(2, 20); // 将 20 插入到索引 2 的位置
19        System.out.println(linkedList);
20
21        List<Integer> list = new ArrayList<>();
22        list.add(101);
23        list.add(102);
24        list.add(103);
25
26        linkedList.addAll(3, list); // 从索引 3 开始插入该集合的所有元素
27        System.out.println(linkedList);
28    }
29}