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;
// 否则，将新节点链接到前驱节点的后面
else
pred.next = newNode;
pred = newNode;
}

// 如果后继节点为null，说明是在链表末尾添加，更新最后一个节点为pred
if (succ == null) {
last = pred;
} 
// 否则，将新添加的最后一个节点链接到原来的后继节点
else {
pred.next = succ;
succ.prev = pred;
}

// 更新链表的大小
size += numNew;
modCount++;  // 修改次数
return true;
}

---

总结

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

原文地址：https://blog.csdn.net/weixin_51329147/article/details/142848505

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！