LinkedList 源码分析，你想知道的都在这里("LinkedList 源码深度解析：你想了解的一切都在这里")

原创

ithorizon 7个月前 (10-20) 阅读数 15 #后端开发

LinkedList 源码深度解析：你想了解的一切都在这里

一、LinkedList 简介

LinkedList 是 Java 中一个非常重要的数据结构，它实现了 List 接口，同时也是一个双端队列（Deque）的实现。LinkedList 通过链表的形式存储元素，提供了高效的插入和删除操作。本文将深入分析 LinkedList 的源码，帮助大家更好地领会其工作原理和内部机制。

二、LinkedList 的数据结构

LinkedList 的数据结构首要由 Node 类构成，每个 Node 包含三个部分：元素（item）、前驱节点（prev）和后继节点（next）。


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

三、LinkedList 的核心方法

以下是 LinkedList 的几个核心方法及其源码解析：

3.1 add(E e)

向链表末尾添加一个元素。


public boolean add(E e) {
    linkLast(e);
    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++;
    modCount++;
}

3.2 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 / 2) {
        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;
    }
}
void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

3.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;
    }
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
    }
    x.item = null;
    x.next = null;
    x.prev = null;
    size--;
    modCount++;
    return element;
}

四、LinkedList 的迭代器

LinkedList 提供了 ListIterator 接口的实现，允许在双向链表上进行双向遍历。以下是 ListIterator 的部分源码：


private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned = null;
    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 (nextIndex == 0)
            throw new NoSuchElementException();
        next = next.prev;
        nextIndex--;
        lastReturned = next;
        return lastReturned.item;
    }
    // ... 其他方法
}