1. 数据结构设计

(1) 节点结构

LinkedList 的核心是双向链表节点 Node：

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;}
}

• 双向链接：每个节点同时记录前驱和后继，支持双向遍历。
• 首尾指针：通过 first 和 last 字段快速访问链表两端。

(2) 与 ArrayList 的存储对比

特性	LinkedList	ArrayList
底层结构	双向链表	动态数组
内存占用	更高（每个元素额外存储指针）	更低（连续内存）
CPU缓存友好性	差（节点分散）	好（局部性原理）

---

2. 核心操作实现

(1) 添加元素

尾部插入（add(E e)）

public boolean add(E e) {linkLast(e); // 时间复杂度 O(1)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++;
}

• 优势：无需扩容，直接修改指针。

指定位置插入（add(int index, E element)）

public void add(int index, E element) {checkPositionIndex(index);if (index == size) {linkLast(element); // 尾部插入优化} else {linkBefore(element, node(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;}
}

• 时间复杂度：
  • 头尾操作：O(1)
  • 中间操作：O(n)（需遍历）

(2) 删除元素

remove(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;x.prev = null; // 清除引用}if (next == null) {last = prev; // 删除的是尾节点} else {next.prev = prev;x.next = null;}x.item = null; // 帮助GCsize--;return element;
}

• 关键点：正确处理头尾节点的边界条件。

(3) 访问元素

get(int index)

public E get(int index) {checkElementIndex(index);return node(index).item; // 需遍历链表
}

• 性能缺陷：随机访问效率远低于 ArrayList（O(n) vs O(1)）。

---

3. 迭代器实现

(1) 普通迭代器 (Iterator)

private class ListItr implements ListIterator<E> {private Node<E> lastReturned;private Node<E> next;private int nextIndex;private int expectedModCount = modCount;public boolean hasNext() { return nextIndex < size; }public E next() {checkForComodification();if (!hasNext()) throw new NoSuchElementException();lastReturned = next;next = next.next;nextIndex++;return lastReturned.item;}
}

• 快速失败机制：通过 modCount 检测并发修改。

(2) 双向迭代器 (ListIterator)

支持向前遍历：

public E previous() {checkForComodification();if (!hasPrevious()) throw new NoSuchElementException();lastReturned = next = (next == null) ? last : next.prev;nextIndex--;return lastReturned.item;
}

---

4. 线程安全与性能优化

(1) 线程安全问题

• 非线程安全：并发修改会导致数据不一致或迭代器失效。
• 解决方案：

  List<String> syncList = Collections.synchronizedList(new LinkedList<>());
  

  或使用并发容器 ConcurrentLinkedDeque。

(2) 设计取舍

操作	LinkedList	ArrayList
头部插入	O(1)	O(n)（需移动元素）
中间插入	O(n)（查找）+ O(1)	O(n)（移动元素）
随机访问	O(n)	O(1)
内存占用	高	低

---

5. 应用场景建议

• 使用 LinkedList 的场景：
  • 频繁在 头部/中部 插入删除（如实现队列/栈）。
  • 不需要频繁随机访问。
• 使用 ArrayList 的场景：
  • 需要快速随机访问。
  • 内存敏感型应用。