LinkedList源码解读

简介

LinkedList 是对 Java 集合框架中 List 接口的一种具体实现，归属于线性数据结构的范畴。其核心内部结构是通过双向链表（double-linked list）来实现的，这使得它在元素插入、删除操作上具备较高的效率，尤其是在列表的首尾进行操作时。

相较于数组实现的列表，如 ArrayList，LinkedList 在非索引访问或遍历操作上可能效率较低。

LinkedList 类继承自 AbstractList 抽象类，并且实现了 List 接口以及标记接口 Serializable。通过实现 Serializable 接口，ArrayList 集合的实例能够支持序列化过程，从而允许对象的状态被转换成可以存储或传输的形式，用于网络传输或保存到文件等。

---

源码解读

基础变量

// 记录元素个数
transient int size = 0;// 当前节点的前一个结点
transient Node<E> first;// 当前节点的后一个结点
transient Node<E> last;// 初始化结点
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;}
}

构造函数

LinkedList()

构造一个空链表。

public LinkedList() {}

LinkedList(Collection<? extends E> c)

传入一个 Collection 的子类集合，将元素存储到 LinkedList。

public LinkedList(Collection<? extends E> c) {this();addAll(c);
}

1. addAll©

public boolean addAll(Collection<? extends E> c) {// size：链表长度，这里作为开始添加新元素的位置return addAll(size, c);
}

2. addAll(size, c)

public boolean addAll(int index, Collection<? extends E> c) {// 判断 index 是否超出范围（index >= 0 && index <= size）checkPositionIndex(index);// 将集合转为数组Object[] a = c.toArray();int numNew = a.length;    // 数组长度if (numNew == 0)return false;// 初始化前结点、后结点Node<E> pred, succ;// 如果index == size，说明实在链表的末尾添加，后继节点为null，前驱节点为最后一个节点if (index == size) {succ = null;pred = last;} else {// 否则，找到指定索引位置的节点，作为后继节点，并找到其前驱节点succ = node(index);pred = succ.prev;}// 遍历数组a，将每个元素添加到链表中for (Object o : a) {@SuppressWarnings("unchecked") E e = (E) o;// 创建新节点，前驱为pred，元素为e，后继为null（暂时）Node<E> newNode = new Node<>(pred, e, null);// 如果前驱节点为null，说明新节点是第一个节点if (pred == null)first = newNode;// 否则，将新节点链接到前驱节点的后面elsepred.next = newNode;pred = newNode;}// 如果后继节点为null，说明是在链表末尾添加，更新最后一个节点为predif (succ == null) {last = pred;} // 否则，将新添加的最后一个节点链接到原来的后继节点else {pred.next = succ;succ.prev = pred;}// 更新链表的大小size += numNew;modCount++;  // 修改次数return true;
}

---

总结

数据结构	底层结构	线程安全	执行效率
ArrayList	可变数组 Object[] elementData	线程不同步、不安全	查询效率搞、增删效率低
LinkedList	双向链表	线程不同步、不安全	增删效率搞、查询效率低