当前位置：首页 > news >正文

深入解析 LinkedList

news 2025/7/13 6:27:49

、链表基础概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序通过链表中的指针链接实现。核心特点：节点1 -> 节点2 -> 节点3

链表类型对比：

类型	特点	示意图
单向链表	只有 next 指针	`A → B → C → null`
双向链表	有 prev 和 next 指针	`null ⇄ A ⇄ B ⇄ C ⇄ null`
循环链表	尾节点指向头节点	`A → B → C → A`

与数组的对比：
特性数组(ArrayList) 链表(LinkedList)
内存连续性连续内存块非连续内存块
随机访问 O(1) O(n)
头部插入 O(n) O(1)
内存利用率可能浪费空间按需分配
CPU缓存友好性高低

特性	数组(ArrayList)	链表(LinkedList)
内存连续性	连续内存块	非连续内存块
随机访问	O(1)	O(n)
头部插入	O(n)	O(1)
内存利用率	可能浪费空间	按需分配
CPU缓存友好性	高	低

二、LinkedList 核心解析

2.1 类结构分析

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

2.2 时间复杂度全景图

操作	时间复杂度	原理说明
addFirst()/addLast()	O(1)	直接修改头尾指针
getFirst()/getLast()	O(1)	直接访问头尾节点
removeFirst()/removeLast()	O(1)	修改头尾指针
get(int index)	O(n)	需要遍历到指定位置
add(int index, E e)	O(n)	找到位置后修改指针（O(1)）
contains(Object o)	O(n)	必须遍历所有元素

三、LinkedList 使用详解

3.1 构造方法

// 示例1：空链表
LinkedList<String> list1 = new LinkedList<>();// 示例2：从集合初始化
List<String> names = Arrays.asList("Alice", "Bob", "Charlie");
LinkedList<String> list2 = new LinkedList<>(names);

3.2 核心操作方法

1. 添加元素：

// 尾部添加（推荐）
linkedList.add("Tail"); // 头部添加
linkedList.addFirst("Head");// 指定位置插入
linkedList.add(2, "Middle");

2. 删除元素：

// 删除头部
String head = linkedList.removeFirst();// 删除尾部
String tail = linkedList.removeLast();// 按值删除（删除第一个匹配项）
linkedList.remove("Bob");// 按索引删除
linkedList.remove(1);

3. 访问元素

// 获取头部（不删除）
String first = linkedList.getFirst();// 获取尾部（不删除）
String last = linkedList.getLast();// 随机访问（效率低）
String item = linkedList.get(3);

4. 队列操作（实现Deque接口）：

// 作为队列使用
Queue<String> queue = new LinkedList<>();
queue.offer("A");     // 入队
queue.poll();         // 出队// 作为双端队列
Deque<String> deque = new LinkedList<>();
deque.offerFirst("A"); // 队头入
deque.offerLast("Z");  // 队尾入
deque.pollFirst();     // 队头出

3.3 四种遍历方式

// 1. for循环（效率最低）
for(int i=0; i<list.size(); i++) {System.out.println(list.get(i)); // 每次get都是O(n)
}// 2. 增强for循环（推荐）
for(String s : list) {System.out.println(s);
}// 3. 迭代器（最佳实践）
Iterator<String> it = list.iterator();
while(it.hasNext()) {System.out.println(it.next());
}// 4. 倒序迭代器（双向链表特有）
Iterator<String> dit = list.descendingIterator();
while(dit.hasNext()) {System.out.println(dit.next());
}

四、源码深度剖析

4.1 节点插入流程

// add(E e) 方法源码
public boolean add(E e) {linkLast(e); // 核心方法return true;
}void linkLast(E e) {final Node<E> l = last;      // 1. 获取当前尾节点final Node<E> newNode = new Node<>(l, e, null); // 2. 创建新节点last = newNode;              // 3. 更新尾指针if (l == null)               // 4. 处理空链表情况first = newNode;elsel.next = newNode;        // 5. 原尾节点指向新节点size++;                      // 6. 更新大小
}

4.2 随机访问优化

// get(int index) 源码
public E get(int index) {checkElementIndex(index); // 索引检查return node(index).item;  // 核心方法
}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;}
}

4.3 删除操作解析

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

五、实战应用案例

5.1 LRU缓存实现

class LRUCache<K, V> {private final int capacity;private final Map<K, V> map = new HashMap<>();private final LinkedList<K> list = new LinkedList<>();public LRUCache(int capacity) {this.capacity = capacity;}public V get(K key) {if (map.containsKey(key)) {// 移动到链表头部list.remove(key);list.addFirst(key);return map.get(key);}return null;}public void put(K key, V value) {if (map.containsKey(key)) {list.remove(key);} else if (map.size() >= capacity) {// 淘汰尾部数据K oldestKey = list.removeLast();map.remove(oldestKey);}list.addFirst(key);map.put(key, value);}
}

5.2 多项式相加

class Polynomial {static class Term {int coeff;int exp;Term(int coeff, int exp) {this.coeff = coeff;this.exp = exp;}}public static LinkedList<Term> add(LinkedList<Term> p1, LinkedList<Term> p2) {LinkedList<Term> result = new LinkedList<>();Iterator<Term> it1 = p1.iterator();Iterator<Term> it2 = p2.iterator();Term t1 = it1.hasNext() ? it1.next() : null;Term t2 = it2.hasNext() ? it2.next() : null;while (t1 != null || t2 != null) {if (t1 == null) {result.add(t2);t2 = it2.hasNext() ? it2.next() : null;} else if (t2 == null) {result.add(t1);t1 = it1.hasNext() ? it1.next() : null;} else if (t1.exp > t2.exp) {result.add(t1);t1 = it1.hasNext() ? it1.next() : null;} else if (t1.exp < t2.exp) {result.add(t2);t2 = it2.hasNext() ? it2.next() : null;} else {// 指数相同，系数相加int sum = t1.coeff + t2.coeff;if (sum != 0) {result.add(new Term(sum, t1.exp));}t1 = it1.hasNext() ? it1.next() : null;t2 = it2.hasNext() ? it2.next() : null;}}return result;}
}

5.3 音乐播放列表

class MusicPlayer {private final LinkedList<String> playlist = new LinkedList<>();private ListIterator<String> iterator;public void addSong(String song) {playlist.addLast(song);if (iterator == null) {iterator = playlist.listIterator();}}public void playNext() {if (iterator.hasNext()) {System.out.println("播放: " + iterator.next());} else {System.out.println("已到列表末尾");}}public void playPrevious() {if (iterator.hasPrevious()) {System.out.println("播放: " + iterator.previous());} else {System.out.println("已到列表开头");}}public void removeCurrent() {iterator.remove();System.out.println("歌曲已移除");}
}

六、经典面试题解析

6.1 链表反转（迭代法）

public static <E> LinkedList<E> reverse(LinkedList<E> list) {LinkedList<E> reversed = new LinkedList<>();for (E item : list) {reversed.addFirst(item); // 利用头插法实现反转}return reversed;
}

6.2 检测环形链表（快慢指针）

public static boolean hasCycle(LinkedList<?> list) {// 模拟快慢指针（实际LinkedList无环）if (list.isEmpty()) return false;Iterator<?> slow = list.iterator();Iterator<?> fast = list.iterator();while (fast.hasNext()) {slow.next(); // 慢指针走一步fast.next(); // 快指针走两步if (!fast.hasNext()) break;fast.next();// 如果相遇则有环if (slow == fast) return true;}return false;
}

6.3 合并有序链表

public static LinkedList<Integer> mergeSortedLists(LinkedList<Integer> list1, LinkedList<Integer> list2) {LinkedList<Integer> merged = new LinkedList<>();Iterator<Integer> it1 = list1.iterator();Iterator<Integer> it2 = list2.iterator();Integer num1 = it1.hasNext() ? it1.next() : null;Integer num2 = it2.hasNext() ? it2.next() : null;while (num1 != null || num2 != null) {if (num1 == null) {merged.add(num2);num2 = it2.hasNext() ? it2.next() : null;} else if (num2 == null) {merged.add(num1);num1 = it1.hasNext() ? it1.next() : null;} else if (num1 < num2) {merged.add(num1);num1 = it1.hasNext() ? it1.next() : null;} else {merged.add(num2);num2 = it2.hasNext() ? it2.next() : null;}}return merged;
}