本文还有配套的精品资源，点击获取

简介：DoublyLinkedList.java 是为 Java 编程语言设计的双向链表实现，旨在帮助学生深入理解线性数据结构的核心概念与操作。该项目源于 cs2110 课程教学实践，涵盖节点结构设计、链表增删改查操作、面向对象编程应用及异常处理机制。双向链表支持前后指针遍历，具备高效的插入删除性能，适用于浏览器历史记录等双向操作场景。通过本项目，学习者可掌握数据结构的基本实现原理与 Java 面向对象特性，提升算法思维与编程实践能力。

1. 双向链表数据结构基本概念

在计算机科学中，链表是一种重要的线性数据结构，而双向链表（Doubly Linked List）作为其重要变种之一，具备前后双向链接的特性。每个节点包含三个部分：数据域、指向后继节点的 next 指针和指向前驱节点的 prev 指针，这使得链表支持高效的正向与反向遍历。

相较于数组，双向链表在插入和删除操作上具有 $O(1)$ 的时间优势（已知位置时），而随机访问则为 $O(n)$，适用于频繁修改的动态数据场景。与单向链表相比，其主要优势在于可通过 prev 指针直接访问前驱，避免重复遍历，提升操作灵活性。

// 节点结构示例（提前预览）
class Node {
    int data;
    Node next;
    Node prev;
}

该结构在内存中采用动态分配方式存储，节点间通过引用链接，逻辑顺序独立于物理地址，增强了数据组织的灵活性。后续章节将基于此模型展开节点设计与功能实现。

2. 节点设计：数据域、next 与 prev 指针实现

在双向链表的构建过程中， 节点（Node）作为整个数据结构的基本单元 ，其设计质量直接决定了链表操作的稳定性、可扩展性以及运行效率。不同于单向链表仅需维护一个指向后继节点的 next 指针，双向链表中的每个节点还需额外保存一个指向前驱节点的 prev 指针。这种双向引用机制使得链表支持前后双向遍历，但也对节点内部结构的设计提出了更高要求。

本章将围绕 Java 中 Node 类的完整设计与实现逻辑 展开深入剖析，涵盖从类结构定义到内存管理等多个层面。重点探讨如何通过泛型化处理提升通用性、如何合理初始化并维护两个方向指针以避免空指针异常，并结合 JVM 内存模型理解对象引用关系及其对垃圾回收的影响。此外，还将介绍基础方法的封装策略，如构造函数重载和调试输出方法的定制，从而为后续链表整体功能开发打下坚实基础。

2.1 节点类的设计原则与Java实现

设计一个高效且安全的节点类，是构建稳定双向链表的前提。良好的节点设计应遵循面向对象的基本原则： 单一职责、高内聚、低耦合、可复用性强 。在 Java 中，我们通常使用类（Class）来封装节点的状态与行为，确保外部无法随意修改其内部状态，同时提供必要的访问接口。

2.1.1 定义Node类及其成员变量

节点的核心组成部分包括三个部分：
- 数据域（data） ：用于存储实际的数据内容；
- next 指针 ：指向链表中下一个节点；
- prev 指针 ：指向前一个节点。

这三个字段共同构成了双向链表节点的基础结构。以下是标准的 Node<T> 类定义示例：

public class Node<T> {
    private T data;           // 数据域，支持任意类型
    private Node<T> next;     // 指向后继节点
    private Node<T> prev;     // 指向前驱节点

    // 构造函数
    public Node(T data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }

    // Getters and Setters
    public T getData() { return data; }
    public void setData(T data) { this.data = data; }

    public Node<T> getNext() { return next; }
    public void setNext(Node<T> next) { this.next = next; }

    public Node<T> getPrev() { return prev; }
    public void setPrev(Node<T> prev) { this.prev = prev; }
}

代码逻辑逐行解读分析：

行号	代码片段	解释说明
1	public class Node<T>	使用泛型 <T> 实现类型参数化，允许节点存储任意类型的对象，提高复用性。
2-4	private T data; ...	将所有字段设为 private ，体现封装性，防止外部直接访问破坏数据一致性。
7-10	构造函数	接收初始数据值，自动将 next 和 prev 初始化为 null ，表示尚未连接任何其他节点。这是防止空指针的关键一步。
13-24	Getter/Setter 方法	提供受控访问方式，便于在必要时加入校验逻辑（例如不允许设置 null 数据）。

该设计符合 Java Bean 规范，也为后续链表操作提供了清晰的操作入口。例如，在插入新节点时，可通过 setNext() 和 setPrev() 动态调整指针关系。

设计优势总结：

• 封装性良好 ：所有字段私有化，只能通过公共方法访问。
• 类型安全 ：借助泛型避免强制类型转换带来的风险。
• 扩展性强 ：未来可在 Node 中添加额外元信息（如时间戳、权重等），不影响现有结构。

2.1.2 数据域的泛型化处理以支持多种数据类型

在实际应用中，链表可能需要存储整数、字符串、自定义对象等多种类型的数据。若将 data 字段固定为某种具体类型（如 int 或 String ），则会严重限制链表的通用性。为此，必须采用 Java 泛型机制 来实现类型抽象。

泛型的优势与应用场景

特性	描述
类型安全	编译期检查类型匹配，避免运行时 ClassCastException
无需强制转换	获取数据时无需 (String) node.getData() 这样的显式转型
可重用代码	同一 Node 类可用于 Integer 链表、User 对象链表等不同场景

下面是一个使用泛型的实际例子：

// 存储用户信息的链表节点
Node<User> userNode = new Node<>(new User("Alice", 28));

// 存储整数的链表节点
Node<Integer> intNode = new Node<>(100);

// 存储字符串的链表节点
Node<String> strNode = new Node<>("Hello World");

泛型边界与通配符的应用（进阶）

当需要进行比较或复制操作时，可以限制泛型的上界。例如，若希望节点支持排序功能，则可限定 <T extends Comparable<T>> ：

public class Node<T extends Comparable<T>> {
    private T data;

    public int compareTo(Node<T> other) {
        return this.data.compareTo(other.data);
    }
}

这保证了 data 字段具备 compareTo 方法，可用于实现有序插入。

注意事项：泛型擦除与性能影响

Java 的泛型基于类型擦除（Type Erasure），即编译后泛型信息会被替换为 Object 。这意味着：

• 运行时无法获取真实类型（除非通过反射+保留签名）；
• 基本类型需使用包装类（如 Integer 而非 int ），带来一定装箱开销；
• 但总体而言，泛型带来的类型安全远大于轻微性能损耗。

因此，在工业级实现中，强烈推荐使用泛型而非 Object 类型。

2.2 双向指针机制详解

双向链表之所以能够实现高效的前后遍历，核心在于每个节点都维护了两个指针： next 和 prev 。正确理解和管理这两个指针的连接逻辑，是实现插入、删除等操作的关键所在。

2.2.1 next指针的作用与初始化策略

next 指针用于指向当前节点的直接后继节点。在空链表中，它初始化为 null ；随着节点的插入， next 将逐步形成一条从头到尾的单向链路。

初始化时机与默认值

public Node(T data) {
    this.data = data;
    this.next = null;   // 初始状态下无后继节点
    this.prev = null;   // 初始状态下无前驱节点
}

该初始化策略确保了新建节点处于“孤立”状态，不会意外连接到已有链表中，有效防止指针污染。

next指针的变化过程（图示）

使用 Mermaid 流程图展示节点插入时 next 指针的变化：

graph LR
    A[New Node: data=5] -->|setNext(head)| B[Old Head: data=3]
    B --> C[Next Node: data=7]
    style A fill:#f9f,stroke:#333
    style B fill:#bbf,stroke:#333
    style C fill:#bbf,stroke:#333

说明：当执行头插法时，新节点的 next 被设置为原 head ，从而将其纳入链表前端。

操作示例：头插法中 next 指针更新

// 假设 head 指向第一个节点
Node<T> newNode = new Node<>(value);
newNode.setNext(head);  // 新节点的 next 指向原 head
if (head != null) {
    head.setPrev(newNode); // 原 head 的 prev 指向新节点
}
head = newNode;         // 更新 head 引用

⚠️ 关键点：必须先设置 newNode.next = head ，再让 head.prev = newNode ，否则会导致断链。

2.2.2 prev指针的连接逻辑与边界维护

prev 指针使双向链表具备反向遍历能力。与 next 不同的是， prev 的管理更易出错，尤其是在边界条件处理上，如插入首节点或删除尾节点时。

prev指针的典型使用场景

场景	prev 操作
头部插入	新节点的 prev = null ，原 head 的 prev = 新节点
尾部插入	新节点的 prev = 原 tail ，原 tail 的 next = 新节点
删除中间节点	node.prev.next = node.next ， node.next.prev = node.prev

边界情况处理表格

情况	prev 是否为 null	说明
首节点	是	prev == null ，代表链表起点
中间节点	否	正常连接前后节点
尾节点	否	next == null ，但 prev != null
空链表	N/A	所有节点为空，head/tail 为 null

示例代码：尾部插入中的 prev 维护

public void addLast(T value) {
    Node<T> newNode = new Node<>(value);
    if (tail == null) { // 空链表
        head = tail = newNode;
    } else {
        newNode.setPrev(tail);    // 新节点 prev 指向原 tail
        tail.setNext(newNode);    // 原 tail next 指向新节点
        tail = newNode;           // 移动 tail 指针
    }
}

✅ 逻辑分析 ：
1. newNode.prev = tail ：建立前向链接；
2. tail.next = newNode ：建立后向链接；
3. tail = newNode ：更新尾指针位置。

三步缺一不可，否则会造成链断裂或指针错乱。

2.2.3 空指针异常的预防与null值管理

由于链表依赖引用传递， null 值的处理不当极易引发 NullPointerException 。特别是在访问 node.next 或 node.prev 之前未做判空检查时，程序将崩溃。

常见空指针触发点

操作	可能发生 NPE 的位置
遍历	while (current != null && current.getNext() != null)
删除节点	current.getPrev().setNext(...) —— 若 current 是头节点则 prev 为 null
获取前驱数据	node.getPrev().getData() —— 必须先判断是否为首节点

安全访问模式（Guarded Access Pattern）

public void printPreviousData(Node<T> node) {
    if (node != null && node.getPrev() != null) {
        System.out.println("Previous node's data: " + node.getPrev().getData());
    } else {
        System.out.println("No previous node.");
    }
}

✅ 最佳实践建议 ：
- 在调用 .getPrev() 或 .getNext() 后立即使用前，务必检查返回值是否为 null ；
- 在链表主类中封装安全遍历方法，屏蔽底层细节；
- 使用 Optional 提升代码健壮性（Java 8+）：

public Optional<Node<T>> getPrevSafe(Node<T> node) {
    return Optional.ofNullable(node).map(Node::getPrev);
}

2.3 内存布局与对象引用分析

理解节点在 JVM 堆内存中的分布及引用关系，有助于优化资源管理和预防内存泄漏。

2.3.1 JVM堆中节点对象的创建与销毁过程

每次调用 new Node<>(value) 时，JVM 会在堆（Heap）中分配一块内存空间用于存放该对象，包含其字段 data 、 next 、 prev 的引用。

对象生命周期阶段

阶段	描述
创建	new 指令触发对象分配，调用构造函数初始化字段
使用	链表操作中频繁读写节点数据和指针
不可达	当没有强引用指向该节点时，进入待回收状态
回收	GC 在适当时候释放内存

示例：节点创建流程

Node<String> n1 = new Node<>("A");
Node<String> n2 = new Node<>("B");
n1.setNext(n2);
n2.setPrev(n1);

此时内存布局如下：

内存地址	节点	data	next	prev
0x1000	n1	“A”	→ 0x1010	null
0x1010	n2	“B”	null	→ 0x1000

两个节点相互持有对方引用，构成双向连接。

2.3.2 引用关系对垃圾回收的影响

尽管 Java 具备自动垃圾回收机制，但双向链表中复杂的引用关系可能导致 内存泄漏 ，尤其在删除节点时未能彻底断开所有引用。

问题示例：未清理引用导致无法回收

// 错误做法：只断开一侧链接
public void removeWrong(Node<T> node) {
    node.getPrev().setNext(node.getNext());
    // 忘记设置 node.next = null 和 node.prev = null
}

此时 node 虽已脱离主链，但仍被自身 next 或 prev 指向的对象间接引用，GC 无法判定其为“不可达”。

正确做法：完全解绑

public void remove(Node<T> node) {
    if (node.getPrev() != null) {
        node.getPrev().setNext(node.getNext());
    }
    if (node.getNext() != null) {
        node.getNext().setPrev(node.getPrev());
    }
    // 主动清除引用，帮助 GC
    node.setNext(null);
    node.setPrev(null);
    node.setData(null);
}

✅ 效果 ： node 所有引用置空，变为“孤岛”，GC 可安全回收。

GC Root 可达性分析（Mermaid 图）

graph TD
    A[Stack: head ref] --> B((Node A))
    B --> C((Node B))
    C --> D((Node C))
    D -.-> E((Orphan Node))

    style E stroke-dasharray:5,5,stroke:#f00

说明：E 节点虽有内部引用，但无 GC Root 可达路径，最终被回收——前提是所有外部引用均已断开。

2.4 节点操作的基础方法封装

为了提升开发效率和调试便利性，应对节点类进行基础方法封装。

2.4.1 构造函数重载以适应不同初始化需求

除了基本构造函数外，可根据需要添加多个重载版本：

public class Node<T> {
    private T data;
    private Node<T> next;
    private Node<T> prev;

    // 默认构造函数
    public Node() {}

    // 单参数构造函数
    public Node(T data) {
        this(data, null, null);
    }

    // 全参构造函数
    public Node(T data, Node<T> next, Node<T> prev) {
        this.data = data;
        this.next = next;
        this.prev = prev;
    }

    // Copy 构造函数
    public Node(Node<T> other) {
        this.data = other.data;
        this.next = other.next;
        this.prev = other.prev;
    }
}

✅ 适用场景 ：
- Node() ：用于哨兵节点或临时占位；
- Node(data, next, prev) ：批量构建链表时非常高效；
- Node(other) ：深拷贝准备（注意需递归复制才算真正深拷贝）。

2.4.2 toString()方法用于调试输出

重写 toString() 方法可大幅提升调试效率：

@Override
public String toString() {
    StringBuilder sb = new StringBuilder();
    sb.append("Node{");
    sb.append("data=").append(data);
    sb.append(", prev=").append(prev != null ? prev.data : "null");
    sb.append(", next=").append(next != null ? next.data : "null");
    sb.append('}');
    return sb.toString();
}

输出示例：

Node<String> n1 = new Node<>("A");
Node<String> n2 = new Node<>("B");
n1.setNext(n2);
n2.setPrev(n1);

System.out.println(n1); // Node{data=A, prev=null, next=B}
System.out.println(n2); // Node{data=B, prev=A, next=null}

该信息直观展示了节点之间的连接状态，极大方便了单元测试和故障排查。

3. Java 类封装双向链表逻辑

在实现双向链表的过程中，节点类的设计只是构建整个数据结构的基础。要真正形成一个可复用、可维护且具备完整功能的数据容器，必须通过面向对象的方式将多个节点组织成一个整体，并对外提供统一的操作接口。本章重点围绕 DoublyLinkedList 主类的封装设计展开，深入探讨如何利用 Java 的类机制实现对链表状态的有效管理，包括成员变量定义、构造方法初始化、核心 API 规划以及封装性保障等关键环节。

良好的类设计不仅提升了代码的可读性和健壮性，还为后续扩展（如迭代器支持、泛型增强或线程安全）打下坚实基础。尤其在企业级开发中，合理的封装是模块化编程和团队协作的前提。因此，本章内容不仅是技术实现层面的指导，更是软件工程思想的具体体现。

3.1 DoublyLinkedList主类结构设计

3.1.1 成员变量定义：head与tail哨兵节点的选择

在双向链表的主类中，最关键的两个引用是 head 和 tail ，它们分别指向链表的第一个有效节点和最后一个有效节点。但在实际工程实践中，存在两种主流设计方式： 普通指针模式 和 带哨兵节点（Sentinel Node）的环形结构 。

设计方式	特点	适用场景
普通 head/tail 指针	初始值为 null，插入第一个节点时需特殊处理	教学示例、简单实现
哨兵节点（Sentinel）	引入虚拟头尾节点，始终存在，简化边界判断	高频增删操作、生产环境

采用哨兵节点的优势在于可以统一所有插入和删除操作的逻辑，避免频繁检查 null 值带来的冗余条件分支。例如，在头插法中无需再判断是否为空链表：

public class DoublyLinkedList<E> {
    private Node<E> head; // 虚拟头节点
    private Node<E> tail; // 虚拟尾节点
    private int size;

    // 内部节点类已在第二章定义
    private static class Node<E> {
        E data;
        Node<E> next;
        Node<E> prev;

        Node(E data) { this.data = data; }
    }

    public DoublyLinkedList() {
        head = new Node<>(null);
        tail = new Node<>(null);
        head.next = tail;
        tail.prev = head;
        size = 0;
    }
}

上述代码展示了使用哨兵节点的经典初始化方式。 head 和 tail 并不存储真实数据，仅作为边界锚点。当链表为空时， head.next == tail 且 tail.prev == head ，这一特性极大简化了插入与删除操作中的指针调整逻辑。

逻辑分析：

• 第 8–9 行：创建两个不携带业务数据的 Node 实例，作为虚拟节点；
• 第 10–11 行：建立双向连接关系，使 head ↔ tail 构成初始空链结构；
• 第 12 行： size 初始化为 0，表示当前无有效元素；
• 所有真实节点都将被插入到 head 和 tail 之间。

该设计虽然多占用两个节点空间，但换来的是更清晰、更少出错的算法逻辑，特别适合复杂操作场景。

3.1.2 size计数器的引入与同步更新机制

为了高效获取链表长度，必须引入一个整型变量 size 来实时记录有效节点数量。若每次调用 length() 都遍历链表统计节点数，则时间复杂度为 O(n)，严重影响性能。因此， size 的引入是必要的优化手段。

然而， size 的价值依赖于其准确性——每发生一次插入或删除操作，都必须确保 size 被正确增减。这要求开发者在每个修改结构的方法中显式维护该字段。

private void addAfter(Node<E> prevNode, E element) {
    Node<E> newNode = new Node<>(element);
    Node<E> nextNode = prevNode.next;

    // 插入新节点
    newNode.next = nextNode;
    newNode.prev = prevNode;
    prevNode.next = newNode;
    nextNode.prev = newNode;

    size++; // 唯一位置递增 size
}

参数说明：

• prevNode ：已存在的前驱节点，新节点将插入其后；
• element ：待插入的数据；
• newNode ：新建节点，包含数据并初始化指针；
• nextNode ：原 prevNode.next ，用于重建链接。

逐行逻辑解读：

1. 创建新节点 newNode ，数据域赋值为 element ；
2. 缓存 prevNode.next 到局部变量 nextNode ，防止后续操作丢失引用；
3. 设置 newNode.next = nextNode ，连接向后；
4. 设置 newNode.prev = prevNode ，连接向前；
5. 更新 prevNode.next 指向 newNode ，完成前驱链接；
6. 更新 nextNode.prev 指向 newNode ，完成后继反向链接；
7. 最后执行 size++ ，保证计数与结构变更同步。

此方法体现了“先连后断”的安全链表操作原则：在切断原有链接之前，先建立新节点与前后节点的完整连接，从而避免中间状态导致的断链问题。

此外， size 的维护应严格限制在私有工具方法内部，避免暴露给外部直接修改，破坏封装性。

3.2 构造方法与初始化流程

3.2.1 无参构造函数实现空链表初始化

无参构造函数是最基本的初始化入口，负责创建一个逻辑上为空的双向链表实例。结合前文所述的哨兵节点设计，其实现如下：

/**
 * 构造一个空的双向链表，使用哨兵节点简化边界处理
 */
public DoublyLinkedList() {
    head = new Node<>(null);
    tail = new Node<>(null);
    head.next = tail;
    tail.prev = head;
    size = 0;
}

该构造函数执行完毕后，链表处于稳定空状态。可通过以下 Mermaid 流程图展示初始化后的内存结构关系：

graph LR
    A[head] --> B[tail]
    B --> C[null]
    C --> D[null]
    D --> A
    style A fill:#f9f,stroke:#333
    style B fill:#bbf,stroke:#333
    subgraph "双向链接"
        A -- next --> B
        B -- prev --> A
    end

图中 head 和 tail 互为邻居，构成闭环结构，任何真实数据节点都将插入其间。这种结构使得无论从头部还是尾部插入，都不需要额外判断链表是否为空。

更重要的是，该设计天然支持双向遍历：
- 正向遍历：从 head.next 开始，直到遇到 tail 结束；
- 反向遍历：从 tail.prev 开始，直到遇到 head 结束。

3.2.2 带初始容量或集合参数的扩展构造

为进一步提升实用性，可在主类中提供带参数的构造函数，允许用户传入已有集合进行批量初始化：

/**
 * 根据给定集合构造双向链表
 * @param collection 初始元素集合
 */
public DoublyLinkedList(Collection<? extends E> collection) {
    this(); // 复用无参构造初始化哨兵结构
    if (collection != null) {
        for (E item : collection) {
            addLast(item); // 尾插法依次添加
        }
    }
}

参数说明：

• collection ：实现了 Collection 接口的任意集合类型（如 ArrayList , HashSet 等）；
• 使用泛型通配符 ? extends E 支持协变，允许子类型传入；
• addLast() 方法需已在类中实现（将在第四章详述）；

执行流程分析：

1. 调用 this() 完成基础结构初始化；
2. 判空保护，防止传入 null 导致 NullPointerException ；
3. 使用增强 for 循环遍历集合，逐个调用 addLast() 插入元素；
4. 每次插入自动触发 size++ ，最终 size 等于集合大小。

此构造方式显著提高了类的易用性，尤其适用于需要将数组或其他集合快速转换为双向链表的场景。

3.3 核心API接口规划

3.3.1 方法命名规范与功能职责划分

一个高质量的链表类应当具备清晰、一致的公共 API。建议遵循 Java 集合框架的命名惯例，提高语义一致性：

功能类别	推荐方法名	说明
插入	addFirst(E) / addLast(E) / add(int, E)	区分位置插入
删除	removeFirst() / removeLast() / remove(int) / remove(Object)	支持多种删除策略
查询	getFirst() / getLast() / get(int) / indexOf(Object) / contains(Object)	提供丰富查找能力
状态	isEmpty() / size() / clear()	基础状态控制

这些方法构成了完整的 CRUD 接口体系，便于与其他组件集成。例如：

public boolean contains(Object o) {
    return indexOf(o) != -1;
}

public int indexOf(Object o) {
    int index = 0;
    for (Node<E> x = head.next; x != tail; x = x.next) {
        if (equals(o, x.data)) return index;
        index++;
    }
    return -1;
}

其中 equals 是一个安全比较工具方法，能处理 null 值：

private boolean equals(Object a, Object b) {
    return (a == null) ? (b == null) : a.equals(b);
}

3.3.2 public与private方法的合理使用

公共方法应聚焦于对外服务，而复杂的底层操作应封装为私有工具方法。例如，插入操作可抽象出通用辅助方法：

private void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(e);

    newNode.next = succ;
    newNode.prev = pred;
    pred.next = newNode;
    succ.prev = newNode;
    size++;
}

该方法可在 add(int index, E element) 中调用，根据索引定位目标节点 succ 后插入。

通过拆分职责，既减少了重复代码，又增强了可测试性与可维护性。

3.4 封装性的保障措施

3.4.1 成员变量私有化与getter/setter控制

所有成员变量必须声明为 private ，禁止外部直接访问：

private Node<E> head;
private Node<E> tail;
private int size;

即便提供 getter 方法，也应谨慎暴露内部结构：

public int size() { return size; }
public boolean isEmpty() { return size == 0; }
// 不建议暴露 head/tail 引用！

暴露原始节点引用可能导致外部绕过 API 直接修改链表结构，破坏封装性甚至引发崩溃。

3.4.2 内部工具方法提取以提升代码复用性

常见的工具方法包括：

/**
 * 根据索引获取对应节点，自动选择前半或后半遍历
 */
private Node<E> node(int index) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);

    if (index < (size >> 1)) {
        // 前半段：从前向后遍历
        Node<E> x = head.next;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        // 后半段：从后向前遍历
        Node<E> x = tail.prev;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

性能优势分析：

• 当 index < size/2 时，从前遍历更快；
• 否则从后遍历，最多只需 (size+1)/2 次跳转；
• 时间复杂度仍为 O(n)，但平均访问成本降低近半。

此方法广泛用于 get(index) 、 set(index, e) 、 remove(index) 等操作中，是性能优化的关键支点。

综上所述， DoublyLinkedList 类的封装不仅仅是简单的字段组合，而是涉及结构设计、行为抽象、边界控制和性能权衡的系统工程。通过科学的类结构布局与方法分层设计，不仅能实现功能完整性，更能为后续的高级特性（如并发控制、序列化支持）预留扩展空间。

4. 头插法、尾插法与指定位置插入操作

在双向链表的实际应用中，插入操作是构建数据结构的核心手段之一。与数组不同，链表无需预先分配固定大小的内存空间，其动态扩展能力依赖于灵活的节点插入机制。本章将深入探讨三种典型的插入方式： 头部插入（addFirst） 、 尾部插入（addLast） 和 指定索引插入（addAtIndex） ，并结合 Java 实现详细解析每种操作背后的指针链接逻辑、边界控制策略以及性能优化技巧。

通过系统性地分析这些插入方法的设计原理，不仅可以掌握双向链表的基础操作流程，还能理解如何在复杂场景下避免断链、空指针异常等常见问题。此外，还将引入异常处理机制，确保 API 接口具备良好的健壮性和可维护性，为后续删除、查找等功能模块打下坚实基础。

4.1 头部插入（addFirst）的实现原理

头部插入是最高效的插入方式之一，因其时间复杂度为 O(1)，常用于需要频繁在起始位置添加元素的场景，如栈结构的 push 操作或最近访问记录优先存储等业务模型。该操作的关键在于正确维护 head 指针与新节点之间的双向连接关系，并保证原有链表结构不被破坏。

4.1.1 新节点与原头节点的链接顺序

在执行头部插入时，必须严格遵循“先建立连接，再更新指针”的原则，以防止出现断链现象。假设当前链表非空，存在一个有效的 head 节点，此时插入新节点 newNode 的步骤如下：

1. 设置 newNode.next = head ，使其指向原头节点；
2. 设置 head.prev = newNode ，完成反向链接；
3. 更新 head = newNode ，使头指针指向新节点；
4. 若原链表为空，则还需同步设置 tail = newNode 。

这一过程体现了双向链表特有的对称性特征：每个节点既要向前看（prev），也要向后看（next）。若任意一环断裂，都将导致遍历失败或内存泄漏。

以下是一个典型实现代码示例：

public void addFirst(E data) {
    Node<E> newNode = new Node<>(data);
    if (head == null) { // 空链表情况
        head = tail = newNode;
    } else {
        newNode.next = head;     // 步骤1：新节点指向原头
        head.prev = newNode;     // 步骤2：原头回指新节点
        head = newNode;          // 步骤3：更新头指针
    }
    size++;
}

代码逻辑逐行解读与参数说明：

• 第2行 ：创建一个新的泛型节点对象 newNode ，封装传入的数据 data 。此处使用了泛型设计，支持多种数据类型。
• 第4–6行 ：判断当前链表是否为空。如果是首次插入，则 head 和 tail 均指向 newNode ，形成单节点闭环。
• 第8行 ：将新节点的 next 指针指向当前 head ，建立正向连接。
• 第9行 ：关键步骤——让原 head 的 prev 指针回指 newNode ，这是区别于单向链表的重要一步。
• 第10行 ：移动 head 指针至 newNode ，完成逻辑上的“头插”。
• 第11行 ： size 计数器递增，保持链表长度同步。

⚠️ 注意：若省略第9行（即未设置 head.prev = newNode ），会导致从新节点出发能访问后续节点，但从旧头节点无法返回前驱，破坏了双向一致性。

为了更直观展示该过程的变化，下面使用 Mermaid 流程图描述插入前后节点关系的演变：

graph LR
    subgraph 插入前
        A[head] --> B[tail]
        B --> A
    end

    subgraph 插入后
        C[newNode] --> D[原head/tail]
        D --> C
        head((head)) -.-> C
        tail((tail)) -.-> D
    end

    style C fill:#e0f7fa,stroke:#006064
    style D fill:#bbdefb,stroke:#1565c0
    style head fill:#ffcc80,stroke:#ef6c00
    style tail fill:#ffcc80,stroke:#ef6c00

该图清晰展示了从单节点状态插入新头节点后的结构变化，其中颜色标注帮助区分新旧节点及指针归属。

4.1.2 head指针更新与边界条件判断

虽然 addFirst 操作通常高效稳定，但在实现过程中仍需特别关注边界条件的处理，尤其是空链表和并发访问场景。

边界情况	判断条件	处理方式
链表为空	head == null	同时设置 head 和 tail
数据为 null	data == null	可允许或抛出异常，依设计需求而定
多线程环境	并发调用 addFirst	需加锁或采用线程安全容器

例如，在某些严格规范的系统中，可能不允许插入 null 值。此时可在方法入口处加入检测：

if (data == null) {
    throw new IllegalArgumentException("Data cannot be null");
}

这种防御式编程思想有助于提升系统的可靠性。

另外，考虑极端情况下的性能表现：即使链表已包含百万级节点， addFirst 依然只需常量时间完成插入，这正是链表优于数组的关键优势之一——无需整体搬移数据。

综上所述，头部插入不仅是技术实现中最简洁的操作之一，更是体现双向链表灵活性与高效性的典范。合理组织指针更新顺序、严谨处理边界条件，是确保此类操作正确性的核心所在。

4.2 尾部插入（addLast）的操作细节

相较于头部插入，尾部插入适用于那些要求保持数据原始顺序的应用场景，如队列的 enqueue 操作、日志追加记录等。尽管两者的时间复杂度均为 O(1)，但尾插法依赖 tail 指针的存在才能实现真正的常量时间性能；否则每次都需要遍历到最后一个节点，退化为 O(n)。

4.2.1 判断空链表状态并初始化head与tail

尾部插入的第一步仍然是判断当前链表是否为空。如果 head == null ，说明链表尚未有任何节点，此时插入的新节点既是头也是尾。

Java 实现如下：

public void addLast(E data) {
    Node<E> newNode = new Node<>(data);

    if (tail == null) { // 等价于 head == null
        head = tail = newNode;
    } else {
        tail.next = newNode;     // 原尾节点的 next 指向新节点
        newNode.prev = tail;     // 新节点的 prev 指向原尾
        tail = newNode;          // 更新 tail 指针
    }
    size++;
}

代码逻辑逐行解读与参数说明：

• 第2行 ：创建新节点，封装输入数据。
• 第4行 ：使用 tail == null 作为判空依据。由于双向链表中 head 与 tail 应始终同步更新，因此也可写作 head == null 。
• 第5–6行 ：对于空链表，新节点同时成为 head 和 tail 。
• 第8行 ：原 tail 的 next 指针指向 newNode ，建立正向连接。
• 第9行 ： newNode 的 prev 指针回指 tail ，完成双向链接。
• 第10行 ：将 tail 指针前移至 newNode ，表示新的末尾位置。
• 第11行 ： size++ 维护链表长度。

值得注意的是，上述实现依赖于 tail 指针的有效维护。一旦 tail 指向错误位置（如因删除操作未及时更新），则可能导致新节点插入到错误位置甚至引发 NullPointerException 。

4.2.2 tail节点的连接与移动

为了验证该操作的正确性，可通过表格形式对比插入前后各指针状态的变化：

操作阶段	head 指向	tail 指向	新节点(prev→next)	原 tail.next
插入前	Node A	Node A	-	null
插入后	Node A	Node B	A → B	B

可见， head 保持不变， tail 成功迁移至新节点，且所有指针均正确链接。

进一步地，可以使用 Mermaid 图形化展示插入过程：

flowchart TD
    A[原tail: Node A] -- tail.next = newNode --> B[NewNode: Node B]
    B -- newNode.prev = tail --> A
    C[tail pointer] -.-> B
    D[head pointer] -.-> A

此流程图明确表达了指针赋值的先后顺序与最终结构形态。

此外，在高并发或多线程环境下，若多个线程同时调用 addLast ，可能出现 tail 指针竞争问题。为此，可在类级别添加 synchronized 关键字或使用 ReentrantLock 进行同步控制：

public synchronized void addLast(E data) { ... }

虽然会牺牲一定性能，但在保障数据一致性的前提下是必要的权衡。

4.3 指定索引插入（addAtIndex）算法设计

相比头插和尾插，按索引插入提供了更高的灵活性，允许开发者在任意合法位置插入新节点。然而，这也带来了更高的实现复杂度，尤其是在遍历定位目标位置和处理边界条件方面。

4.3.1 索引合法性校验：0 ≤ index ≤ size

在执行插入前，必须对传入的索引进行严格校验：

• 若 index < 0 或 index > size ，应抛出 IndexOutOfBoundsException ；
• 允许 index == size ，表示在末尾插入，等同于 addLast ；
• 允许 index == 0 ，等同于 addFirst 。

具体实现如下：

public void addAtIndex(int index, E data) {
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }

    if (index == 0) {
        addFirst(data);
        return;
    }
    if (index == size) {
        addLast(data);
        return;
    }

    Node<E> current = getNodeAt(index); // 获取目标位置的当前节点
    Node<E> newNode = new Node<>(data);

    newNode.next = current;
    newNode.prev = current.prev;
    current.prev.next = newNode;
    current.prev = newNode;

    size++;
}

参数说明与逻辑分析：

• index ：插入位置，范围 [0, size] 。
• data ：待插入元素，支持泛型。
• 使用 getNodeAt(index) 辅助方法获取目标位置的节点引用。

代码逐行解读：

• 第2–4行 ：索引越界检查，防止非法访问。
• 第6–9行 ：特例处理，复用已有方法提高代码复用性。
• 第11行 ：调用内部工具方法 getNodeAt(index) 定位目标节点。
• 第13–16行 ：四步链接操作：
  1. newNode.next = current
  2. newNode.prev = current.prev
  3. current.prev.next = newNode
  4. current.prev = newNode

✅ 关键点：第3、4步顺序不能颠倒！否则会导致 current.prev 被提前修改，造成断链。

4.3.2 遍历策略优化：从前半段或后半段逼近目标位置

由于双向链表支持双向遍历，可以在查找目标节点时根据索引位置选择最优路径：

• 若 index < size / 2 ，从 head 开始正向遍历；
• 否则从 tail 开始反向遍历。

该优化可将平均遍历距离缩短一半，显著提升大链表中的插入效率。

private Node<E> getNodeAt(int index) {
    Node<E> current;
    if (index < size / 2) {
        current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
    } else {
        current = tail;
        for (int i = size - 1; i > index; i--) {
            current = current.prev;
        }
    }
    return current;
}

索引位置	遍历方向	时间复杂度
0 ~ size/2	从 head 出发	O(index)
size/2 ~ size	从 tail 出发	O(size - index)

该策略使得最坏情况仍为 O(n)，但实际运行中平均性能接近 O(n/2)，优于单向链表。

4.3.3 节点连接顺序的安全性保障（避免断链）

在多指针环境中，操作顺序至关重要。以下表格对比了正确的与错误的连接顺序：

步骤	正确顺序（推荐）	错误顺序（危险）
1	newNode.next = current	current.prev = newNode
2	newNode.prev = current.prev	newNode.next = current
3	current.prev.next = newNode	newNode.prev = current.prev
4	current.prev = newNode	current.prev.next = newNode

错误顺序可能导致中间状态丢失前驱引用，从而切断链表连接。

4.4 插入操作的异常处理机制

健壮的 API 设计离不开完善的异常处理机制。双向链表在插入过程中主要面临两类异常风险：索引越界与 null 值输入。

4.4.1 IndexOutOfBoundsException抛出条件

当用户请求在无效索引处插入时，必须及时反馈错误信息：

if (index < 0 || index > size) {
    throw new IndexOutOfBoundsException("Invalid index: " + index);
}

该异常属于运行时异常，由 JVM 自动传播，便于调试定位。

4.4.2 null值输入检测与响应策略

关于是否允许 null 值插入，取决于具体应用场景：

• 允许 null ：提供更大灵活性，但需在 equals() 比较时小心处理；
• 禁止 null ：增强安全性，防止后续操作出现 NPE。

建议提供配置选项或文档说明：

// 可选策略：拒绝 null 输入
if (data == null) {
    throw new NullPointerException("Element cannot be null");
}

最终，完整的插入体系应当具备如下特性：

• ✅ 支持头、尾、任意位置插入
• ✅ 时间复杂度分别为 O(1)、O(1)、O(n)
• ✅ 指针链接安全无断链
• ✅ 异常处理完善，反馈明确

通过本章的学习，读者不仅掌握了三大插入操作的具体实现，还理解了底层指针操作的精妙之处，为构建完整、可靠的双向链表奠定了坚实基础。

5. 按值或位置删除节点实现与查找功能设计

在双向链表的完整生命周期中，除了插入操作外，删除与查找是另外两个核心操作。它们不仅决定了数据结构的灵活性和实用性，也直接影响程序运行时的效率与稳定性。尤其在实际工程场景中，如缓存淘汰、历史记录清理、条件过滤等，都需要高效的节点移除机制和精准的数据定位能力。本章将深入剖析基于索引和基于值的删除策略，并系统性地构建查找功能模块，确保双向链表具备完整的增删查改（CRUD）能力。

5.1 按索引删除（removeAtIndex）实现

5.1.1 边界检查与特殊情形处理（首尾节点）

在执行任何删除操作前，必须对输入参数进行合法性校验。对于按索引删除而言，首要任务是判断传入的 index 是否处于有效范围 [0, size) 内。若超出该区间，则应抛出 IndexOutOfBoundsException ，防止非法内存访问或逻辑错误。

特别需要注意的是，当链表为空（ size == 0 ）时，任何删除请求都应被拒绝；而当链表仅含一个节点时，删除操作会导致 head 和 tail 同时置空，需统一更新状态。此外，删除头节点（ index = 0 ）和尾节点（ index = size - 1 ）属于边界情况，其指针调整方式不同于中间节点，需要单独处理。

为提升性能，可以结合双向链表的对称特性，在遍历时选择从头部还是尾部开始逼近目标节点。具体策略如下表所示：

条件	遍历起点	理由
index < size / 2	从 head 开始正向遍历	更接近头部，减少遍历次数
index >= size / 2	从 tail 开始反向遍历	更接近尾部，利用 prev 指针

这种优化可将平均遍历时间降低约一半，显著提高大链表下的操作效率。

flowchart TD
    A[开始 removeAtIndex(index)] --> B{index 是否合法?}
    B -- 否 --> C[抛出 IndexOutOfBoundsException]
    B -- 是 --> D{index == 0?}
    D -- 是 --> E[调用 removeFirst()]
    D -- 否 --> F{index == size-1?}
    F -- 是 --> G[调用 removeLast()]
    F -- 否 --> H[定位目标节点 node]
    H --> I[断开 node 前后连接]
    I --> J[释放 node 引用]
    J --> K[size -= 1]
    K --> L[返回被删值]

上述流程图清晰展示了删除操作的整体控制流，体现了条件分支与复用已有方法的设计思想。

5.1.2 前后节点指针重连的原子性操作

在找到目标节点后，关键在于安全地将其从前驱和后继节点中“摘除”，同时保持链表整体结构不断裂。这一过程涉及四个指针的修改：

• node.prev.next = node.next
• node.next.prev = node.prev

这两个赋值操作必须成对出现且顺序不可颠倒，否则可能导致临时断链或空指针异常。例如，若先设置 node.next.prev = node.prev 而此时 node.next 为 null ，就会触发 NullPointerException 。

以下为 Java 实现代码示例：

public T removeAtIndex(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }

    Node<T> nodeToRemove;
    if (index == 0) {
        return removeFirst(); // 复用头删逻辑
    } else if (index == size - 1) {
        return removeLast(); // 复用尾删逻辑
    } else {
        nodeToRemove = (index < size / 2) ?
                traverseForward(index) : traverseBackward(index);
    }

    // 断开前后连接（关键步骤）
    nodeToRemove.prev.next = nodeToRemove.next;
    nodeToRemove.next.prev = nodeToRemove.prev;

    // 保存值用于返回
    T value = nodeToRemove.data;

    // 清理被删节点引用，防止内存泄漏
    nodeToRemove.data = null;
    nodeToRemove.prev = null;
    nodeToRemove.next = null;

    size--;
    return value;
}

private Node<T> traverseForward(int index) {
    Node<T> current = head;
    for (int i = 0; i < index; i++) {
        current = current.next;
    }
    return current;
}

private Node<T> traverseBackward(int index) {
    Node<T> current = tail;
    for (int i = size - 1; i > index; i--) {
        current = current.prev;
    }
    return current;
}

逐行逻辑分析：

• 第2–4行 ：边界检查，确保索引合法。
• 第6–8行 ：若为首尾节点，直接调用已封装的方法，增强代码复用性和可维护性。
• 第9–13行 ：根据索引位置决定遍历方向，体现性能优化策略。
• 第16–17行 ：通过修改前后节点的指针完成“摘除”操作，这是删除的核心逻辑。
• 第20–23行 ：主动清空被删节点的所有引用，避免因残留强引用导致垃圾回收器无法回收对象。
• 第25行 ：同步更新链表长度计数器。

参数说明：
- index ：待删除节点的位置，从0开始计数。
- 返回类型 T ：泛型数据，表示被删除节点所存储的原始值。

此实现保证了删除操作的线程安全性（在单线程环境下），并通过精细化的指针管理避免了常见陷阱。

5.2 按值删除（removeByValue）搜索与移除

5.2.1 遍历比较equals方法的正确使用

与按索引删除不同，按值删除依赖于内容匹配而非位置定位。这意味着必须遍历整个链表，逐一调用元素的 .equals() 方法进行比较。此处的关键在于不能使用 == 判断引用相等，而应使用 equals() 以支持语义相等性判断，尤其是在处理字符串、自定义对象等类型时。

Java 中推荐写法如下：

(data == null ? otherData == null : data.equals(otherData))

这能正确处理 null 值比较，避免空指针异常。

此外，用户通常有两种需求模式：
1. 删除第一个匹配项；
2. 删除所有匹配项。

因此，API 设计上应提供两个版本： remove(Object value) 删除首个匹配项， removeAll(Object value) 删除全部。

5.2.2 删除首个匹配项还是全部匹配项的策略选择

以下表格对比了两种策略的应用场景与实现复杂度：

策略	适用场景	时间复杂度	实现难度	是否中断遍历
删除首个匹配项	缓存去重、唯一实体删除	O(n) 最坏	简单	是
删除所有匹配项	批量清洗日志、清除重复事件	O(n) 固定	中等	否

推荐优先实现 remove(Object value) ，即删除首个匹配项。

public boolean remove(T value) {
    Node<T> current = head;
    while (current != null) {
        if (isEqual(current.data, value)) {
            unlink(current);
            return true; // 成功删除一项即返回
        }
        current = current.next;
    }
    return false; // 未找到
}

private boolean isEqual(T a, T b) {
    return (a == null && b == null) || (a != null && a.equals(b));
}

private void unlink(Node<T> node) {
    if (node.prev == null) {
        head = node.next; // 删除的是头节点
    } else {
        node.prev.next = node.next;
    }

    if (node.next == null) {
        tail = node.prev; // 删除的是尾节点
    } else {
        node.next.prev = node.prev;
    }

    // 清理资源
    node.data = null;
    node.prev = null;
    node.next = null;
    size--;
}

逐行逻辑分析：

• 第2–6行 ：从头开始遍历，直到找到满足 isEqual 条件的节点。
• 第7行 ：调用私有方法 unlink 统一处理指针解绑，提升代码内聚性。
• 第13–26行 ： unlink 方法全面覆盖头、尾、中间三种情况，避免遗漏边界。
• 第28–31行 ：主动断开被删节点的所有引用，符合 JVM 内存管理最佳实践。

参数说明：
- value ：要删除的目标值，允许为 null 。
- 返回 boolean ：删除成功返回 true ，否则 false 。

该设计通过提取通用解绑逻辑，增强了代码的可读性和扩展性，也为后续实现 removeAll 提供了基础。

5.3 查找功能（indexOf, contains）算法实现

5.3.1 正向遍历实现indexOf返回索引位置

indexOf(T value) 方法用于定位某个值首次出现的索引位置，若不存在则返回 -1 。其实现依赖于从 head 出发的正向遍历，并在每一步进行值比较。

考虑到泛型兼容性，仍需使用前述 isEqual 辅助方法来处理 null 值。

public int indexOf(T value) {
    Node<T> current = head;
    int index = 0;
    while (current != null) {
        if (isEqual(current.data, value)) {
            return index;
        }
        current = current.next;
        index++;
    }
    return -1;
}

逻辑分析：
- 使用 index 计数器跟踪当前位置。
- 遍历过程中一旦匹配成功立即返回当前索引，保证“首次出现”的语义。
- 若遍历结束仍未匹配，返回 -1 表示未找到。

5.3.2 boolean查询contains提升判断效率

虽然 indexOf(value) != -1 可用于判断存在性，但 contains 方法更为语义清晰且便于优化。其内部实现与 indexOf 类似，但无需维护索引变量，可在找到后立刻终止。

public boolean contains(T value) {
    return indexOf(value) != -1;
}

此实现复用了 indexOf ，减少了代码冗余。但在高频调用场景下，可考虑独立实现以省略索引累加开销。

方法	功能	返回值	典型用途
indexOf(T)	定位值的位置	int（-1表示无）	定位、调试
contains(T)	判断是否存在	boolean	条件判断、去重

5.4 删除后的资源清理与size更新

5.4.1 断开被删节点的所有引用防止内存泄漏

尽管 Java 具备自动垃圾回收机制，但如果被删除的节点仍被其他强引用持有，或其自身保留对链表节点的反向引用，则可能造成内存泄漏。因此，在 unlink 或 remove 操作完成后，必须显式将被删节点的 data 、 next 、 prev 设置为 null 。

这样做有两个好处：
1. 加速 GC 回收：使对象进入不可达状态；
2. 防止误操作：即使外部仍持有该节点引用，也无法再访问链表内部结构。

// 示例：手动触发GC前的状态清理
protected void finalizeRemoval(Node<T> removedNode) {
    removedNode.data = null;
    removedNode.prev = null;
    removedNode.next = null;
}

注意：不应依赖 finalize() 方法，而是应在业务逻辑中主动调用清理。

5.4.2 size变量递减与空链表状态重置

每次成功删除后， size 计数器必须同步减一。更重要的是，当 size == 0 时，应确保 head == null && tail == null ，以维持链表一致性。

可通过断言或单元测试验证：

assert (size == 0) == (head == null && tail == null);

此外，在实现 clear() 方法时，建议遍历所有节点并逐一断开引用，而不是简单设置 head = tail = null ，以确保每个节点都能被及时回收。

public void clear() {
    Node<T> current = head;
    while (current != null) {
        Node<T> next = current.next;
        current.data = null;
        current.prev = null;
        current.next = null;
        current = next;
    }
    head = null;
    tail = null;
    size = 0;
}

这种方式虽耗时 O(n)，但更安全可靠，适用于对内存敏感的系统级应用。

综上所述，删除与查找功能不仅是双向链表的基础能力，更是保障其健壮性与高效性的关键所在。通过合理设计指针操作、遍历策略与资源管理机制，能够构建出既稳定又高效的链表实现，为后续在真实项目中的集成打下坚实基础。

6. 双向链表综合应用与性能分析

6.1 正向与反向遍历功能设计

在双向链表中，得益于每个节点同时持有 next 和 prev 指针，我们可以高效地实现正向和反向遍历。这种能力在某些应用场景（如文本编辑器的撤销/重做、浏览器历史记录）中极为关键。

6.1.1 使用迭代器模式实现forwardIterator

Java 中推荐使用 Iterator<T> 接口来封装遍历逻辑。以下是一个自定义正向迭代器的实现：

import java.util.Iterator;
import java.util.NoSuchElementException;

public class ForwardIterator<T> implements Iterator<T> {
    private Node<T> current;

    public ForwardIterator(Node<T> head) {
        this.current = head;
    }

    @Override
    public boolean hasNext() {
        return current != null;
    }

    @Override
    public T next() {
        if (!hasNext()) throw new NoSuchElementException();
        T data = current.data;
        current = current.next;
        return data;
    }
}

• 参数说明 ：
• current : 当前指向的节点，初始为 head
• hasNext() : 判断是否还有下一个元素
• next() : 返回当前元素并移动指针

调用方式示例：

DoublyLinkedList<String> list = new DoublyLinkedList<>();
list.addLast("A"); list.addLast("B"); list.addLast("C");

Iterator<String> it = new ForwardIterator<>(list.getHead());
while (it.hasNext()) {
    System.out.print(it.next() + " "); // 输出: A B C
}

6.1.2 reverseIterator 的逆序访问机制

反向迭代器从 tail 开始，利用 prev 指针逐个回退：

public class ReverseIterator<T> implements Iterator<T> {
    private Node<T> current;

    public ReverseIterator(Node<T> tail) {
        this.current = tail;
    }

    @Override
    public boolean hasNext() {
        return current != null;
    }

    @Override
    public T next() {
        if (!hasNext()) throw new NoSuchElementException();
        T data = current.data;
        current = current.prev;
        return data;
    }
}

测试代码：

Iterator<String> rit = new ReverseIterator<>(list.getTail());
while (rit.hasNext()) {
    System.out.print(rit.next() + " "); // 输出: C B A
}

遍历方式	起点	移动方向	时间复杂度
正向遍历	head	next →	O(n)
反向遍历	tail	prev ←	O(n)

注：两种遍历均无需额外空间，且支持流式处理。

6.2 时间复杂度分析与操作效率评估

我们对常见操作进行系统性性能评估：

操作类型	方法名	最佳情况	平均情况	最坏情况	空间复杂度
头部插入	addFirst	O(1)	O(1)	O(1)	O(1)
尾部插入	addLast	O(1)	O(1)	O(1)	O(1)
中间插入	addAtIndex	O(1)*	O(n)	O(n)	O(1)
头部删除	removeFirst	O(1)	O(1)	O(1)	O(1)
尾部删除	removeLast	O(1)	O(1)	O(1)	O(1)
按索引删除	removeAtIndex	O(1)*	O(n)	O(n)	O(1)
查找元素	indexOf / contains	O(1)	O(n)	O(n)	O(1)
正/反向遍历	iterator	O(n)	O(n)	O(n)	O(1)

*仅当插入位置已知时可达 O(1)，否则需遍历定位。

6.2.1 O(1)级别的插入删除优势解析

由于双向链表不需要像数组那样移动元素， 在已知节点位置的前提下 ，任意位置的插入和删除都可以通过修改前后指针完成：

// 在节点 node 后插入 new_node
new_node.next = node.next;
new_node.prev = node;
if (node.next != null) {
    node.next.prev = new_node;
}
node.next = new_node;

该过程不依赖于链表长度，因此是常数时间操作。

6.2.2 O(n)查找瓶颈及优化思路探讨

尽管插入删除高效，但查找仍需遍历。优化策略包括：

1. 双向逼近查找 ：根据索引靠近头部还是尾部决定遍历方向
   java Node<T> getNode(int index) { if (index < size / 2) { // 从前向后 Node<T> x = head; for (int i = 0; i < index; i++) x = x.next; return x; } else { // 从后向前 Node<T> x = tail; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
2. 缓存热点数据 ：维护最近访问节点引用（类似LRU）
3. 结合哈希表 ：构建 HashMap<T, Node<T>> 实现 O(1) 值查找（牺牲空间换时间）

6.3 实际应用场景建模：浏览器历史记录管理

6.3.1 前进与后退功能依赖prev/next指针实现

模拟浏览器“前进”、“后退”行为：

public class BrowserHistory {
    private DoublyLinkedList<String> history;
    private Node<String> current;

    public void back() {
        if (current != null && current.prev != null) {
            current = current.prev;
            System.out.println("Back to: " + current.data);
        }
    }

    public void forward() {
        if (current != null && current.next != null) {
            current = current.next;
            System.out.println("Forward to: " + current.data);
        }
    }

    public void visit(String url) {
        Node<String> newNode = new Node<>(url);
        if (current == null) {
            history.addFirst(url);
            current = history.getHead();
        } else {
            // 断开后续历史（Chrome 行为）
            if (current.next != null) {
                current.next.prev = null;
                current.next = null;
            }
            newNode.prev = current;
            current.next = newNode;
            current = newNode;
        }
    }
}

6.3.2 当前指针定位与状态同步机制

使用 current 指针标记当前位置，所有导航操作基于此指针进行移动。当用户访问新页面时，自动清除“前进”历史（符合主流浏览器逻辑）。

flowchart LR
    A["首页"] --> B["文章页"]
    B --> C["评论页"]
    C --> D["用户资料"]
    D -- 后退 --> C
    C -- 后退 --> B
    B -- 访问新文章 --> E["新文章页"]
    style D stroke:#f66,stroke-width:2px
    style E stroke:#6f6,stroke-width:2px

上图展示了访问路径变化与指针移动关系。

6.4 面向对象编程思想的体现

6.4.1 封装性在API设计中的实践

将内部结构隐藏，对外暴露简洁接口：

public class DoublyLinkedList<T> {
    private Node<T> head;
    private Node<T> tail;
    private int size;

    public void addFirst(T data) { /* 实现细节隐藏 */ }
    public T removeLast() { /* 内部逻辑封装 */ }

    // 不暴露原始节点
    public Node<T> getHead() { throw new UnsupportedOperationException(); }
}

6.4.2 继承扩展可能性：从DoublyLinkedList派生新类

可继承实现特定功能列表：

public class ObservableList<T> extends DoublyLinkedList<T> {
    private List<ChangeListener<T>> listeners;

    @Override
    public void addLast(T data) {
        super.addLast(data);
        fireChange(data, "ADD");
    }
}

6.4.3 多态支持下的接口统一调用

实现 List<T> 接口后，可在统一接口下切换不同实现：

List<String> list = new DoublyLinkedList<>(); // 多态赋值
list.add("item");
list.remove(0);

6.5 项目级完整实现流程总结

6.5.1 单元测试编写验证各方法正确性

使用 JUnit 编写测试用例：

@Test
public void testAddRemoveSequence() {
    DoublyLinkedList<Integer> list = new DoublyLinkedList<>();
    list.addLast(1); list.addLast(2); list.addLast(3);
    assertEquals(3, list.size());
    assertEquals(Integer.valueOf(2), list.get(1));
    list.removeAtIndex(1);
    assertEquals(Integer.valueOf(3), list.get(1));
}

6.5.2 边界测试用例覆盖空链表、单节点等极端情况

测试场景	输入动作	预期结果
空链表删除	removeFirst()	抛出NoSuchElementException
单节点添加删除	add→remove→size()	size=0
索引越界插入	addAtIndex(-1, x)	抛出IndexOutOfBoundsException
null值插入	addFirst(null)	允许或抛出异常（依设计而定）
连续反向遍历	reverseIterator多次调用	正确输出倒序

6.5.3 Java课程项目集成建议与代码提交规范

建议采用如下工程结构：

src/
├── structure/
│   └── DoublyLinkedList.java
├── iterator/
│   ├── ForwardIterator.java
│   └── ReverseIterator.java
├── util/
│   └── ChangeListener.java
test/
└── DoublyLinkedListTest.java

提交前执行：

javac -Xlint:unchecked *.java   # 检查泛型警告
java org.junit.runner.JUnitCore DoublyLinkedListTest

本文还有配套的精品资源，点击获取

简介：DoublyLinkedList.java 是为 Java 编程语言设计的双向链表实现，旨在帮助学生深入理解线性数据结构的核心概念与操作。该项目源于 cs2110 课程教学实践，涵盖节点结构设计、链表增删改查操作、面向对象编程应用及异常处理机制。双向链表支持前后指针遍历，具备高效的插入删除性能，适用于浏览器历史记录等双向操作场景。通过本项目，学习者可掌握数据结构的基本实现原理与 Java 面向对象特性，提升算法思维与编程实践能力。

本文还有配套的精品资源，点击获取