java-LinkedList源码详解

前言：

LinkedList 是 Java 中另一个常用的集合类，它基于双向链表实现，支持高效的插入和删除操作，但随机访问性能较差

类定义和成员变量：

public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable {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;}}
}

size：链表中元素的数量。
first：链表的头节点。
last：链表的尾节点。
Node：内部静态类，表示链表的节点，包含数据 (item)、前驱节点 (prev) 和后继节点 (next)。

构造方法：

LinkedList 提供了两个构造方法：

// 构造一个空链表
public LinkedList() {
}// 构造一个包含指定集合元素的链表
public LinkedList(Collection<? extends E> c) {this();addAll(c);
}

无参构造方法：创建一个空链表。
使用集合构造方法：创建一个包含指定集合元素的链表。

核心方法：

添加元素

// 在链表末尾添加元素
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; // 新节点也是头节点elsel.next = newNode; // 否则，将新节点链接到原尾节点的后面size++; // 链表大小增加modCount++; // 修改次数增加
}

add(E e)：在链表末尾添加元素。
linkLast(E e)：在链表末尾链接一个新节点。

获取元素

// 获取指定索引位置的元素
public E get(int index) {checkElementIndex(index); // 检查索引是否越界return node(index).item;  // 返回节点的数据
}// 检查索引是否越界
private void checkElementIndex(int index) {if (index < 0 || index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}// 返回指定索引位置的节点
Node<E> node(int 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;}
}

get(int index)：获取指定索引位置的元素。
node(int index)：根据索引返回节点，优化了查找性能（从头部或尾部开始遍历）。

删除元素

// 删除指定索引位置的元素
public E remove(int index) {checkElementIndex(index); // 检查索引是否越界return unlink(node(index)); // 删除节点并返回其数据
}// 删除指定节点
E unlink(Node<E> x) {final E element = x.item; // 获取节点的数据final Node<E> next = x.next; // 获取后继节点final Node<E> prev = x.prev; // 获取前驱节点if (prev == null) { // 如果删除的是头节点first = next;} else {prev.next = next; // 将前驱节点的 next 指向后继节点x.prev = null;    // 清除当前节点的 prev 引用}if (next == null) { // 如果删除的是尾节点last = prev;} else {next.prev = prev; // 将后继节点的 prev 指向前驱节点x.next = null;    // 清除当前节点的 next 引用}x.item = null; // 清除当前节点的数据引用，帮助 GCsize--;        // 链表大小减少modCount++;    // 修改次数增加return element;
}

remove(int index)：删除指定索引位置的元素。
unlink(Node x)：删除指定节点，并调整链表结构。

修改元素

// 修改指定索引位置的元素
public E set(int index, E element) {checkElementIndex(index); // 检查索引是否越界Node<E> x = node(index);  // 获取节点E oldVal = x.item;        // 获取旧值x.item = element;         // 设置新值return oldVal;            // 返回旧值
}

set(int index, E element)：修改指定索引位置的元素。

其他方法

队列操作

LinkedList 实现了 Deque 接口，支持队列和双端队列操作：

// 在链表头部添加元素
public void addFirst(E e) {linkFirst(e);
}// 在链表头部链接一个新节点
private void linkFirst(E e) {final Node<E> f = first; // 获取当前头节点final Node<E> newNode = new Node<>(null, e, f); // 创建新节点first = newNode; // 更新头节点为新节点if (f == null) // 如果链表为空last = newNode; // 新节点也是尾节点elsef.prev = newNode; // 否则，将新节点链接到原头节点的前面size++; // 链表大小增加modCount++; // 修改次数增加
}// 在链表尾部添加元素
public void addLast(E e) {linkLast(e);
}// 获取链表头部元素
public E getFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return f.item;
}// 获取链表尾部元素
public E getLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return l.item;
}

工具方法

// 返回链表大小
public int size() {return size;
}// 判断链表是否为空
public boolean isEmpty() {return size == 0;
}// 清空链表
public void clear() {for (Node<E> x = first; x != null; ) {Node<E> next = x.next;x.item = null;x.next = null;x.prev = null;x = next;}first = last = null;size = 0;modCount++;
}

序列化

LinkedList 实现了 Serializable 接口，支持序列化。由于 first 和 last 是 transient 的，LinkedList 自定义了序列化和反序列化的逻辑：

private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException {s.defaultWriteObject();s.writeInt(size); // 写入链表大小// 遍历链表，写入每个元素for (Node<E> x = first; x != null; x = x.next)s.writeObject(x.item);
}private void readObject(java.io.ObjectInputStream s)throws java.io.IOException, ClassNotFoundException {s.defaultReadObject();int size = s.readInt(); // 读取链表大小// 遍历链表，读取每个元素并添加到链表中for (int i = 0; i < size; i++)linkLast((E) s.readObject());
}