JDK 8 LinkedList 源码详解（完整版带详细注释）

JDK 8 LinkedList 源码详解（完整版带详细注释）

1. 基本结构和常量定义

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
    
    // 序列化版本号
    private static final long serialVersionUID = 876323262645176354L;
    
    // 链表中元素的个数
    transient int size = 0;
    
    // 链表的第一个节点（头节点）
    transient Node<E> first;
    
    // 链表的最后一个节点（尾节点）
    transient Node<E> last;
    
    // 修改次数，用于快速失败机制
    transient int modCount = 0;
}

2. 节点类定义

/**
 * 双向链表节点
 * @param <E> 节点存储的元素类型
 */
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;
    }
}

3. 构造函数

/**
 * 无参构造函数
 * 构造一个空的列表
 */
public LinkedList() {
    // 所有字段都使用默认值，first和last都为null，size为0
}

/**
 * 从集合构造LinkedList
 * @param c 要构造LinkedList的集合
 * @throws NullPointerException 如果集合为null
 */
public LinkedList(Collection<? extends E> c) {
    this(); // 调用无参构造函数
    addAll(c); // 添加集合中的所有元素
}

4. 核心方法实现

4.1 链表操作辅助方法

/**
 * 在链表头部添加元素
 * @param e 要添加的元素
 * @return true（为了符合Collection接口规范）
 */
private void linkFirst(E e) {
    final Node<E> f = first; // 获取当前头节点
    // 创建新节点，prev为null，next为原头节点
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode; // 更新头节点为新节点
    
    if (f == null)
        // 如果原头节点为null，说明链表为空，新节点也是尾节点
        last = newNode;
    else
        // 否则将原头节点的prev指向新节点
        f.prev = newNode;
    
    size++; // 元素数量增加
    modCount++; // 修改次数增加
}

/**
 * 在链表尾部添加元素
 * @param e 要添加的元素
 * @return true（为了符合Collection接口规范）
 */
void linkLast(E e) {
    final Node<E> l = last; // 获取当前尾节点
    // 创建新节点，prev为原尾节点，next为null
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode; // 更新尾节点为新节点
    
    if (l == null)
        // 如果原尾节点为null，说明链表为空，新节点也是头节点
        first = newNode;
    else
        // 否则将原尾节点的next指向新节点
        l.next = newNode;
    
    size++; // 元素数量增加
    modCount++; // 修改次数增加
}

/**
 * 在指定节点之前插入元素
 * @param e 要插入的元素
 * @param succ 指定节点
 */
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev; // 获取指定节点的前驱节点
    // 创建新节点，prev为前驱节点，next为指定节点
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode; // 指定节点的prev指向新节点
    
    if (pred == null)
        // 如果前驱节点为null，说明是在头部插入
        first = newNode;
    else
        // 否则前驱节点的next指向新节点
        pred.next = newNode;
    
    size++; // 元素数量增加
    modCount++; // 修改次数增加
}

/**
 * 移除并返回第一个节点
 * @return 被移除的节点存储的元素
 */
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item; // 获取要移除节点的元素
    final Node<E> next = f.next; // 获取要移除节点的下一个节点
    f.item = null; // 帮助GC
    f.next = null; // 帮助GC
    first = next; // 更新头节点
    
    if (next == null)
        // 如果下一个节点为null，说明链表只有一个节点
        last = null;
    else
        // 否则将下一个节点的prev置为null
        next.prev = null;
    
    size--; // 元素数量减少
    modCount++; // 修改次数增加
    return element;
}

/**
 * 移除并返回最后一个节点
 * @return 被移除的节点存储的元素
 */
private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    final E element = l.item; // 获取要移除节点的元素
    final Node<E> prev = l.prev; // 获取要移除节点的前一个节点
    l.item = null; // 帮助GC
    l.prev = null; // 帮助GC
    last = prev; // 更新尾节点
    
    if (prev == null)
        // 如果前一个节点为null，说明链表只有一个节点
        first = null;
    else
        // 否则将前一个节点的next置为null
        prev.next = null;
    
    size--; // 元素数量减少
    modCount++; // 修改次数增加
    return element;
}

/**
 * 移除指定节点
 * @param x 要移除的节点
 * @return 被移除节点存储的元素
 */
E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item; // 获取要移除节点的元素
    final Node<E> next = x.next; // 获取下一个节点
    final Node<E> prev = x.prev; // 获取前一个节点
    
    if (prev == null) {
        // 如果前一个节点为null，说明是头节点
        first = next;
    } else {
        // 否则将前一个节点的next指向下一个节点
        prev.next = next;
        x.prev = null; // 帮助GC
    }
    
    if (next == null) {
        // 如果下一个节点为null，说明是尾节点
        last = prev;
    } else {
        // 否则将下一个节点的prev指向前一个节点
        next.prev = prev;
        x.next = null; // 帮助GC
    }
    
    x.item = null; // 帮助GC
    size--; // 元素数量减少
    modCount++; // 修改次数增加
    return element;
}

4.2 List接口方法实现

/**
 * 获取第一个元素
 * @return 第一个元素
 * @throws NoSuchElementException 如果列表为空
 */
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

/**
 * 获取最后一个元素
 * @return 最后一个元素
 * @throws NoSuchElementException 如果列表为空
 */
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

/**
 * 移除并返回第一个元素
 * @return 第一个元素
 * @throws NoSuchElementException 如果列表为空
 */
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

/**
 * 移除并返回最后一个元素
 * @return 最后一个元素
 * @throws NoSuchElementException 如果列表为空
 */
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

/**
 * 在列表开头插入元素
 * @param e 要插入的元素
 */
public void addFirst(E e) {
    linkFirst(e);
}

/**
 * 在列表末尾插入元素
 * @param e 要插入的元素
 */
public void addLast(E e) {
    linkLast(e);
}

/**
 * 判断列表是否包含指定元素
 * @param o 要查找的元素
 * @return 如果包含返回true
 */
public boolean contains(Object o) {
    return indexOf(o) != -1;
}

/**
 * 返回列表中元素的数量
 */
public int size() {
    return size;
}

/**
 * 在列表末尾添加元素
 * @param e 要添加的元素
 * @return true（为了符合Collection接口规范）
 */
public boolean add(E e) {
    linkLast(e);
    return true;
}

/**
 * 移除列表中第一次出现的指定元素
 * @param o 要移除的元素
 * @return 如果成功移除返回true
 */
public boolean remove(Object o) {
    if (o == null) {
        // 处理null元素
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        // 处理非null元素
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

/**
 * 清空列表
 */
public void clear() {
    // 将所有节点的引用置为null，帮助GC
    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; // 头尾节点置为null
    size = 0; // 元素数量置为0
    modCount++; // 修改次数增加
}

4.3 位置访问操作

/**
 * 获取指定位置的元素
 * @param index 元素的索引
 * @return 指定位置的元素
 * @throws IndexOutOfBoundsException 如果索引越界
 */
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

/**
 * 替换指定位置的元素
 * @param index 要替换元素的索引
 * @param element 新元素
 * @return 被替换的旧元素
 * @throws IndexOutOfBoundsException 如果索引越界
 */
public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

/**
 * 在指定位置插入元素
 * @param index 插入位置的索引
 * @param element 要插入的元素
 * @throws IndexOutOfBoundsException 如果索引越界
 */
public void add(int index, E element) {
    checkPositionIndex(index);
    
    if (index == size)
        // 如果在末尾插入，调用linkLast方法
        linkLast(element);
    else
        // 否则在指定节点前插入
        linkBefore(element, node(index));
}

/**
 * 移除指定位置的元素
 * @param index 要移除元素的索引
 * @return 被移除的元素
 * @throws IndexOutOfBoundsException 如果索引越界
 */
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

/**
 * 检查元素索引是否有效
 * @param index 要检查的索引
 */
private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
 * 检查位置索引是否有效（用于添加元素）
 * @param index 要检查的索引
 */
private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
 * 判断索引是否是有效的元素索引
 * @param index 要判断的索引
 * @return 如果索引有效返回true
 */
private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}

/**
 * 判断索引是否是有效的位置索引
 * @param index 要判断的索引
 * @return 如果索引有效返回true
 */
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

/**
 * 构造越界异常信息
 * @param index 越界的索引
 * @return 异常信息字符串
 */
private String outOfBoundsMsg(int index) {
    return "Index: "+index+", Size: "+size;
}

/**
 * 返回指定索引位置的节点
 * @param index 节点的索引
 * @return 指定索引位置的节点
 */
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.4 查找操作

/**
 * 返回指定元素第一次出现的索引
 * @param o 要查找的元素
 * @return 元素第一次出现的索引，如果不存在返回-1
 */
public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        // 查找null元素
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        // 查找非null元素
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

/**
 * 返回指定元素最后一次出现的索引
 * @param o 要查找的元素
 * @return 元素最后一次出现的索引，如果不存在返回-1
 */
public int lastIndexOf(Object o) {
    int index = size;
    if (o == null) {
        // 查找null元素
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (x.item == null)
                return index;
        }
    } else {
        // 查找非null元素
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}

5. Deque接口方法实现（双端队列）

/**
 * 在队列头部添加元素（Deque接口方法）
 */
public void push(E e) {
    addFirst(e);
}

/**
 * 移除并返回队列头部的元素（Deque接口方法）
 */
public E pop() {
    return removeFirst();
}

/**
 * 在队列尾部添加元素（Deque接口方法）
 */
public boolean offer(E e) {
    return add(e);
}

/**
 * 在队列头部添加元素（Deque接口方法）
 */
public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

/**
 * 在队列尾部添加元素（Deque接口方法）
 */
public boolean offerLast(E e) {
    addLast(e);
    return true;
}

/**
 * 获取但不移除队列头部的元素（Deque接口方法）
 */
public E peekFirst() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

/**
 * 获取但不移除队列尾部的元素（Deque接口方法）
 */
public E peekLast() {
    final Node<E> l = last;
    return (l == null) ? null : l.item;
}

/**
 * 获取并移除队列头部的元素（Deque接口方法）
 */
public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

/**
 * 获取并移除队列尾部的元素（Deque接口方法）
 */
public E pollLast() {
    final Node<E> l = last;
    return (l == null) ? null : unlinkLast(l);
}

6. 迭代器实现

/**
 * 返回列表迭代器
 */
public ListIterator<E> listIterator(int index) {
    checkPositionIndex(index);
    return new ListItr(index);
}

/**
 * 列表迭代器实现
 */
private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned; // 上次返回的节点
    private Node<E> next;         // 下一个节点
    private int nextIndex;        // 下一个节点的索引
    private int expectedModCount = modCount; // 期望的修改次数

    ListItr(int index) {
        // 根据索引确定起始位置
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }

    public boolean hasNext() {
        return nextIndex < size;
    }

    public E next() {
        checkForComodification();
        if (!hasNext())
            throw new NoSuchElementException();

        lastReturned = next;
        next = next.next;
        nextIndex++;
        return lastReturned.item;
    }

    public boolean hasPrevious() {
        return nextIndex > 0;
    }

    public E previous() {
        checkForComodification();
        if (!hasPrevious())
            throw new NoSuchElementException();

        // 确定前一个节点
        lastReturned = next = (next == null) ? last : next.prev;
        nextIndex--;
        return lastReturned.item;
    }

    public int nextIndex() {
        return nextIndex;
    }

    public int previousIndex() {
        return nextIndex - 1;
    }

    public void remove() {
        checkForComodification();
        if (lastReturned == null)
            throw new IllegalStateException();

        Node<E> lastNext = lastReturned.next;
        unlink(lastReturned);
        if (next == lastReturned)
            next = lastNext;
        else
            nextIndex--;
        lastReturned = null;
        expectedModCount++;
    }

    public void set(E e) {
        if (lastReturned == null)
            throw new IllegalStateException();
        checkForComodification();
        lastReturned.item = e;
    }

    public void add(E e) {
        checkForComodification();
        lastReturned = null;
        if (next == null)
            linkLast(e);
        else
            linkBefore(e, next);
        nextIndex++;
        expectedModCount++;
    }

    /**
     * 检查并发修改
     */
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

7. 其他重要方法

7.1 clone方法

/**
 * 克隆方法
 */
public Object clone() {
    LinkedList<E> clone = superClone();
    clone.first = clone.last = null;
    clone.size = 0;
    clone.modCount = 0;
    
    // 逐个添加元素
    for (Node<E> x = first; x != null; x = x.next)
        clone.add(x.item);
    
    return clone;
}

/**
 * 浅拷贝
 */
private LinkedList<E> superClone() {
    try {
        return (LinkedList<E>) super.clone();
    } catch (CloneNotSupportedException e) {
        throw new InternalError(e);
    }
}

7.2 toArray方法

/**
 * 返回包含所有元素的数组
 */
public Object[] toArray() {
    Object[] result = new Object[size];
    int i = 0;
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;
    return result;
}

/**
 * 返回包含所有元素的指定类型数组
 */
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
    if (a.length < size)
        a = (T[])java.lang.reflect.Array.newInstance(
                            a.getClass().getComponentType(), size);
    int i = 0;
    Object[] result = a;
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;

    if (a.length > size)
        a[size] = null;

    return a;
}

8. 总结

8.1 LinkedList的特点

1. 底层实现：基于双向链表实现
2. 动态大小：可以根据需要动态增长和收缩
3. 双向访问：可以从头部或尾部开始遍历
4. 有序性：保持元素的插入顺序
5. 允许重复：可以存储重复元素
6. 允许null：可以存储null元素
7. 非线程安全：不是线程安全的
8. 实现多个接口：实现了List、Deque、Cloneable、Serializable接口

8.2 时间复杂度分析

• 访问元素：O(n) - 需要遍历链表
• 搜索元素：O(n) - 需要遍历链表
• 插入元素：
  • 头部/尾部插入：O(1)
  • 中间插入：O(n) - 需要先找到插入位置
• 删除元素：
  • 头部/尾部删除：O(1)
  • 中间删除：O(n) - 需要先找到删除位置
• 随机访问：O(n) - 需要遍历到指定位置

8.3 空间复杂度

• 存储空间：O(n) - n为存储的元素个数
• 额外空间：每个节点需要额外的prev和next指针空间

8.4 使用建议

1. 适用场景：

   • 需要在列表开头或结尾频繁插入/删除元素
   • 需要实现栈或队列功能
   • 不需要频繁随机访问元素
   • 元素数量变化较大

2. 不适用场景：

   • 需要频繁随机访问元素（考虑使用ArrayList）
   • 内存空间紧张（链表需要额外的指针空间）

3. 性能优化：

   • node()方法中的优化：根据索引位置选择从头部或尾部开始遍历
   • 对于头部和尾部的操作都是O(1)时间复杂度

LinkedList作为Java集合框架中的重要实现，提供了灵活的链表操作，在需要频繁插入删除的场景下具有优势。