java实现单链表

java实现单链表|从零构建完整数据结构模型

⚡ 为什么选择单链表作为入门核心?

单链表(Singly Linked List)是线性表的链式存储结构,其核心在于节点(Node)通过指针顺序连接形成逻辑序列。相比数组,单链表在插入删除操作上具有O(1)时间复杂度优势(已知位置前提下),但随机访问性能为O(n)。在java实现单链表过程中,开发者需深入理解引用(Reference)语义、内存布局及空指针安全处理,是掌握JVM对象模型与内存管理的绝佳实践路径。

尤其在面试高频考点中,“反转链表”“环检测”“快慢指针”等算法均以单链表为载体,其变形题型(如合并K个有序链表、LRU缓存底层)广泛用于考察数据结构建模能力。本文将从零实现一个健壮、可复用的单链表类,并深入解析其与java.util.LinkedList设计差异、性能边界及常见陷阱。

特别说明:本实现严格遵循JDK设计哲学,但刻意简化以突出教学目的,适用于初学者构建完整认知框架。所有代码均经JDK 8+验证通过,支持泛型、迭代器、自定义异常等工程化特性。

〔 核心概念速览 〕

  • 节点(Node):包含数据域(data)与指针域(next)的封装对象
  • 头结点(head):链表首节点引用,空链表时为null
  • 尾节点(tail):最后一个节点,其next恒为null
  • 长度(size):节点总数,维护动态计数避免遍历统计
  • 空指针安全:所有操作前必须校验节点非空,防止NullPointerException
  • 内存开销:每个节点需额外存储指针,空间复杂度为O(n)但常数因子大于数组

⚙️ 单链表类结构设计

〈 设计原则与类图 〉

我们采用面向对象设计,将单链表抽象为SingleLinkedList<E>泛型类,满足以下原则:

  • 封装性:节点类Node设为私有静态内部类,隐藏实现细节
  • 接口一致性:实现Iterable<E>支持for-each循环
  • 异常安全:非法索引抛出自定义IndexOutOfBoundsException
  • 线程安全:当前设计为非线程安全,多线程场景需外部同步

【 节点类定义 】

private static class Node<E> {
    E data;
    Node<E> next;
    Node(E data) {
        this.data = data;
    }
}

关键点解析:Node类使用泛型参数E确保类型安全,static修饰避免持有外部类引用,减少内存泄漏风险。数据域直接暴露(非getter/setter)因仅内部访问,提升性能。

〔 主类成员与构造 〕

SingleLinkedList主类维护三个核心字段:

  • private Node<E> head; 头结点引用
  • private int size; 动态长度计数
  • private static final String INDEX_OUT_OF_BOUNDS_MSG = "索引越界:"; 统一异常提示

【 构造器实现 】

public SingleLinkedList() {
    this.head = null;
    this.size = 0;
}

构造器初始化空链表,所有字段为私有属性,通过方法访问保证封装性。注意:未实现带初始容量的构造器,因链表动态扩容无需预分配内存。

〔 基础操作实现 〕

添加节点
删除节点
访问节点
搜索节点

⚡ 头插法与尾插法对比

添加节点(add)支持三种模式:头插(addFirst)、尾插(addLast)、按索引插入(add)。核心差异在于指针重连策略:

【 头插法实现 】

public void addFirst(E element) {
    Node<E> newNode = new Node<>(element);
    newNode.next = head;
    head = newNode;
    size++;
}

步骤说明:
① 创建新节点newNode;
② 新节点next指向原head;
③ 更新head为新节点;
④ 增加size计数。
时间复杂度O(1),适用于实现栈(Stack)或处理紧急任务队列。

【 尾插法实现 】

public void addLast(E element) {
    Node<E> newNode = new Node<>(element);
    if (head == null) {
        head = newNode;
    } else {
        Node<E> current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }
    size++;
}

需遍历至尾节点,时间复杂度O(n)。优化方案:维护tail指针实现O(1)尾插(但增加内存开销与复杂度,本设计未采用以保持简洁性)。

〔 删除节点的关键路径 〕

删除操作需处理三种场景:删除头节点、删除中间节点、删除尾节点。核心在于找到待删节点的前驱节点(prev)。

【 删除指定索引节点 】

public E remove(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException(INDEX_OUT_OF_BOUNDS_MSG + index);
    }
    Node<E> current = head;
    if (index == 0) {
        head = head.next;
    } else {
        for (int i = 0; i < index - 1; i++) {
            current = current.next;
        }
        current.next = current.next.next;
    }
    size--;
    return current.next != null ? current.next.data : null;
}

特别注意:
• 删除头节点时,直接更新head = head.next;
• 删除其他节点时,循环至index-1位置;
• 返回被删节点数据前需校验current.next非空;
• 最后必须执行size--保持计数同步。

▲ 按索引访问与修改

单链表不支持随机访问,需从头遍历至目标位置,时间复杂度O(n)。实现时可加入优化:当索引在后半段时,从尾部反向遍历(需维护tail指针),但本设计保持简单性。

【 获取节点数据 】

public E get(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException(INDEX_OUT_OF_BOUNDS_MSG + index);
    }
    Node<E> current = head;
    for (int i = 0; i < index; i++) {
        current = current.next;
    }
    return current.data;
}

典型应用:遍历链表时避免重复查找,可缓存前驱节点引用提升性能。

⚡ 高频算法实战:单链表核心操作

〔 反转链表 〕

反转链表是面试必考题,需原地操作(空间复杂度O(1))。核心思想是逐个断开节点连接并反向指针,使用三个指针(prev、current、next)协作完成。

【 迭代法实现 】

public void reverse() {
    Node<E> prev = null;
    Node<E> current = head;
    while (current != null) {
        Node<E> next = current.next; // 暂存下一节点
        current.next = prev;         // 反转当前节点指针
        prev = current;              // 移动prev指针
        current = next;              // 移动current指针
    }
    head = prev; // 更新头结点
}

执行过程图解:
初始:1→2→3→null
第1步:prev=1, current=2→null → 1←2 3→null
第2步:prev=2←1, current=3→null → 1←2←3
结束:head=3←2←1

【 环检测与入口点 〕

判断链表是否存在环(Cycle Detection)的经典算法是Floyd判圈法(快慢指针)。慢指针每次移动1步,快指针移动2步,若存在环则必相遇。

【 环存在性检测 】

public boolean hasCycle() {
    Node<E> slow = head;
    Node<E> fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

数学证明:设环长为C,入口点距头节点距离为D,快慢指针相遇时慢指针走了D + x步,快指针走了D + x + nC步(n为圈数)。因快指针速度是2倍,得D + x = nC ⇒ D = nC - x,即入口点距相遇点距离等于D,故从头与相遇点同步移动可定位入口。

〔 链表排序:归并排序优化 〕

链表排序首选归并排序(Merge Sort),因其随机访问慢但分割与合并高效。时间复杂度O(n log n),空间复杂度O(1)(自底向上实现)。

【 主排序逻辑 】

public void sort() {
    if (head == null || head.next == null) return;
    // 找中点
    Node<E> mid = getMiddle(head);
    Node<E> right = mid.next;
    mid.next = null; // 断开链表
    // 递归排序
    SingleLinkedList<E> leftList = new SingleLinkedList<>();
    leftList.head = head;
    leftList.size = size / 2;
    SingleLinkedList<E> rightList = new SingleLinkedList<>();
    rightList.head = right;
    rightList.size = size - leftList.size;
    leftList.sort();
    rightList.sort();
    // 合并
    head = merge(leftList.head, rightList.head);
}

合并函数实现(升序):

private Node<E> merge(Node<E> a, Node<E> b) {
    if (a == null) return b;
    if (b == null) return a;
    Node<E> result;
    if ((a.data == null && b.data != null) ||
        (a.data != null && b.data != null && ((Comparable<E>)a.data).compareTo(b.data) <= 0)) {
        result = a;
        result.next = merge(a.next, b);
    } else {
        result = b;
        result.next = merge(a, b.next);
    }
    return result;
}

〔 网友高频问题答疑 〕

⑴ 为什么Java内置LinkedList底层是双向链表而非单链表?

双向链表(Doubly Linked List)支持O(1)时间复杂度的尾插/尾删操作,且可反向遍历,更适合实现队列(Queue)与双端队列(Deque)。单链表仅在删除头节点时为O(1),而双向链表头/尾操作均为O(1)。JDK选择双向链表是为平衡通用性与性能,但单链表在内存受限场景仍有价值(如嵌入式开发)。

⑵ 单链表删除节点时为何要维护前驱节点?

单链表节点仅含next指针,无法反向追溯。删除节点B时,必须修改前驱节点A的next指向B的后继节点C(即A.next = C.next),否则链表断裂。若仅知B节点引用(如LeetCode“删除链表中的节点”题),需将B.next的数据复制到B,再删除B.next,实现“伪删除”。

⑶ 空指针异常常见于哪些操作?

典型场景:
• 访问空链表的head.next;
• 未处理尾节点next为null的情况;
• 在循环中未检查current是否为null;
• equals比较时未处理null值(应使用Objects.equals()或显式判空)。
解决方案:所有操作前添加空值校验,使用Objects.requireNonNull()明确参数要求。