深入解析 LinkedList

、链表基础概念

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

链表类型对比：

• 与数组的对比：

  特性	数组(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 时间复杂度全景图

三、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;
    else
        l.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;            // 帮助GC
    size--;
    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;
}

七、使用场景建议

• 推荐使用：

  • 频繁在头尾增删元素（队列/栈操作）
  • 不需要随机访问的场景
  • 元素数量变化大的场景
  • 实现特殊数据结构（LRU缓存等）

• 避免使用：

  • 需要频繁随机访问（超过总操作20%）
  • 内存敏感场景（每个元素额外消耗24字节指针）
  • CPU缓存优化要求高的场景