Java 集合学习日记：Day2 - LinkedList底层原理

一、LinkedList 类继承体系

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

继承 / 实现作用

1. AbstractSequentialList：顺序集合抽象父类，提供迭代器骨架

2. List：具备 List 集合规范（增删改查、下标操作）

3. Deque：双向队列，可当栈、普通队列、双端队列用

4. Cloneable：支持克隆

5. Serializable：支持序列化

二、核心成员变量

// 集合实际元素个数
transient int size = 0;
// 头节点
transient Node<E> first;
// 尾节点
transient Node<E> last;

三、内部私有节点类 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;
    }
}

四、构造方法源码

1. 无参构造

public LinkedList() {
}

2.有参构造（传入集合）

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

先创建空链表，再把传入集合全部元素添加到链表尾部。

五、核心私有辅助方法

1.linkFirst (E e) 头插法

private void linkFirst(E e) {
    final Node<E> f = first;
    // 新建节点：前驱null，元素e，后继是原头节点f
    final Node<E> newNode = new Node<>(null, e, f);
    // 新节点变成新头节点
    first = newNode;
    if (f == null)
        // 原链表为空，尾节点也指向新节点
        last = newNode;
    else
        // 原头节点的前驱指向新节点
        f.prev = newNode;
    size++;
    modCount++;
}

2.linkLast (E e) 尾插法

void linkLast(E e) {
    final Node<E> l = last;
    // 新节点：前驱是原尾节点，后继null
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

3. unlinkFirst(Node<E> f) 删除头节点

4. unlinkLast(Node<E> l) 删除尾节点

5. unlink(Node<E> x) 删除指定中间节点

六、对外常用 API

1.add (E e) 追加到末尾

public boolean add(E e) {
    linkLast(e);
    return true;
}

2.addFirst (E e) 插头部

public void addFirst(E e) {
    linkFirst(e);
}

3.addLast (E e) 插尾部

public void addLast(E e) {
    linkLast(e);
}

4.get (int index) 根据下标查元素

public E get(int index) {
    checkIndex(index);
    return node(index).item;
}

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

七、modCount 快速失败机制

transient int modCount = 0;

八、LinkedList 核心特点

1. 底层：双向链表，内存不连续

2. 没有容量限制，动态扩容，无需像 ArrayList 扩容移位

3. 增删元素只修改节点引用指向，效率高

4. 按下标查询慢，但 node() 做了二分遍历优化

5. 实现 Deque 接口，可做：普通队列、栈、双端队列

6. 非线程安全，多线程环境用 ConcurrentLinkedQueue

7. 允许元素为 null，可重复