Java 双向链表完整实现指南

结果或目标

实现一个支持泛型数据的双向链表结构，具备以下能力：

• 动态维护链表长度及头尾节点引用。
• 支持在链表头部、尾部及指定位置前后进行元素插入。
• 提供按索引获取、按值替换、按值移除及存在性判断功能。
• 确保在链表为空或单节点等极端情况下的代码健壮性。

准备条件

需要基础的 Java 面向对象编程知识，了解类、内部静态类、泛型（Generics）的基本语法。无需额外依赖库，使用标准 JDK 即可运行。

真实操作顺序

第1步：定义节点内部类

目的：构建双向链表的基本单元，每个节点需存储数据和指向相邻节点的指针。

1. 在 DoubleNodeList 内部定义私有静态内部类 Node。
2. 声明三个字段：perv（前驱节点）、next（后继节点）和 data（泛型数据）。
3. 提供构造函数初始化 data 字段。

private static class Node<T> {
    Node<T> perv;
    Node<T> next;
    T data;

    public Node(T t) {
        this.data = t;
    }
}

第2步：初始化链表结构与成员变量

目的：设置链表的状态标记，包括头节点、尾节点、备用临时节点及当前长度。

核心字段说明：

• head：指向首节点，null 时链表为空（但在本实现中为简化逻辑，有时用哨兵节点或直接置空）。
• last：指向尾节点，优化尾部插入操作的时间复杂度至 O(1)。
• other：用于遍历过程中的临时引用，避免每次循环都创建新变量。
• length：记录当前元素个数，替代 O(n) 长度的遍历计算。

private Node<T> head;
private Node<T> last;
private Node<T> other;
private int length;

提供两个构造器：

• 无参构造：初始化空链表，head 指向一个包含 null 数据的头节点，length 设为 0。
• 含参构造：传入初始数据，创建首个节点作为 head 和 last，长度设为 1。

第3步：实现尾部插入（add 方法）

入口：public void add(T data) 动作：

1. 检查 isEmpty()。若为空，直接复用含参构造逻辑，将 data 赋给 head 和 last。
2. 若非空，执行**尾插法**：
   • 新建节点 other 并赋值 data。
   • 建立双向链接：other.perv = last，last.next = other。
   • 更新尾指针：last = other。
   • 长度自增。

第4步：实现指定位置前后插入

入口：addAfter(T data, T insertData) 和 addBefore(T data, T insertData) 动作：

1. 遍历链表寻找目标节点 data。
2. 后插 (addAfter)：
   • 新节点 t 的 perv 指向原节点，next 指向原节点的 next。
   • 原节点 next 指向 t。
   • 关键判断：若 t.next == null（即插在末尾），需同步更新 last = t。
3. 前插 (addBefore)：
   • 新节点 t 的 perv 指向原节点的 perv，next 指向原节点。
   • 原节点的前驱节点的 next 指向 t。

第5步：实现查询、更新与移除

get(int index)：校验索引范围，从头节点开始步进至索引位置，返回 other.data。

set(T oldValue, T newValue)：遍历查找匹配 oldValue 的节点，直接修改其 data 字段。

remove(T data)：

1. 找到包含 data 的节点。
2. 断开连接：other.perv.next = other.next。
3. 注意：原文代码中移除操作未处理尾指针 last 和前驱为空的情况，实际使用中若删除的是尾节点或头节点，需补充相应指针修正逻辑以保证链表一致性。
4. 长度减一。

完成判断

调用 printList() 可验证节点输出是否正确；通过 getSize() 确认长度统计准确；使用 contains() 验证查找逻辑。所有公开方法均需保证在链表为空或操作无效时不抛出不可控异常（如索引越界有明确抛错，移除不存在元素返回 false）。

简要总结

以上是对 Java 双向链表实现的详细内容，更多关于 Java 数据结构与算法的资料请关注本站其它相关文章！