本文共 2527 字，大约阅读时间需要 8 分钟。

一、整体理解

LinkedList的底层结构是一个双向链表，每个节点都可以向前向后追溯。在双向链表中，头节点称为first，尾节点称为last。当链表为空时，first和last都指向null。每个节点包含prev和next属性，分别指向前驱节点和后继节点。

节点类通过内置类Node定义，通过初始化参数布局确定前、自身、后三个节点的关系。该结构使得节点之间的链接操作简单快速，链表的增删操作效率较高。

二、源码分析

1. 节点添加操作

在链表操作中，新增节点的方式主要有两种：追加到尾部（默认行为）或追加到头部（addFirst方法）。add方法默认从尾部进行节点的追加。

代码示例如下： ```java public boolean add(E e) { linkLast(e); return true; } ``` linkLast方法实现具体逻辑： ```java void linkLast(E e) { final Node l = last; final Node newNode = new Node(l, e, null); last = newNode; if (l == null) { first = newNode; } else { l.next = newNode; } size++; modCount++; } ```

2. 节点删除操作

与新增操作类似，删除操作可以从头或尾部进行，删除时将节点的前后引用置null以便垃圾回收。

代码示例如下： ```java private E unlinkFirst(Node f) { final E element = f.item; final Node next = f.next; f.item = null; f.next = null; first = next; if (next == null) { last = null; } else { next.prev = null; } size--; modCount++; return element; } ```

3. 节点查询

LinkedList的查询方式采用了优化策略：根据索引位置判断是通过头部查找还是尾部查找。当索引位于前半部分时，采用头部遍历的方式；当位于后半部分时，采用尾部遍历的方式。

代码示例如下： ```java private Node node(int index) { if (index < (size > 1 ? (size >>> 1) : size)) { Node x = first; for (int i = 0; i < index; i++) { x = x.next; } return x; } else { Node x = last; for (int i = size - 1; i > index; i--) { x = x.prev; } return x; } } ```

4. 迭代器实现

LinkedList支持双向迭代访问，通过ListIterator接口实现。ListIterator类内部维护了lastReturned、next和nextIndex变量，分别对应上一次访问的节点、下一个访问的节点以及节点的索引位置。

具体实现代码如下： ```java private class ListItr implements ListIterator { private Node lastReturned; private Node next; private int nextIndex; private int expectedModCount = modCount;

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 void remove() {
    checkForComodification();
    if (lastReturned == null) {
        throw new IllegalStateException();
    }
    final Node lastNext = lastReturned.next;
    unlink(lastReturned);
    if (next == lastReturned) {
        next = lastNext;
    } else {
        nextIndex--;
    }
    lastReturned = null;
    expectedModCount++;
}

}

该实现支持从头到尾和从尾到头两种迭代方向，删除操作支持通过迭代器执行，删除节点后调整索引位置以确保链表的正确性。