Java 自定义链表数据结构实现指南

1. 概述

与数组不同，数组分配连续内存块进行顺序存储，而链表将元素分散在非连续内存位置，每个节点通过引用指向下一个节点。这种结构使链表支持动态扩容，在插入操作中效率极高。

本文将教你如何在 Java 中实现自定义单向链表，包含插入、删除、检索和计数功能。

⚠️ 注意：Java 标准库已提供LinkedList实现，我们自行实现仅用于学习目的。

2. 理解链表

链表由节点集合组成，每个节点存储值和指向序列中下一个节点的引用。链表的最小单位是单个节点。

典型单向链表中：

第一个节点称为头节点（head）
最后一个节点称为尾节点（tail）
尾节点的 next 引用始终为 null，标记链表结束

常见链表类型：

单向链表：每个节点仅指向下一个节点
双向链表：每个节点同时持有前后节点的引用
循环链表：尾节点引用指向头节点形成闭环（分单向/双向）

3. 创建节点

创建 Node 类：

class Node<T> {
    T value;
    Node<T> next;

    public Node(T value) {
        this.value = value; 
        this.next = null;
    }
}

这个类代表链表中的单个元素，包含两个字段：

value – 存储节点数据
next – 指向链表中的下一个节点

通过使用泛型（**），确保链表可存储任意指定类型的数据。

4. 创建并链接节点

演示节点如何链接：

Node<Integer> node0 = new Node<>(1);
Node<Integer> node1 = new Node<>(2);
Node<Integer> node2 = new Node<>(3);
node0.next = node1;
node1.next = node2;

创建三个 Integer 类型节点，通过 next 引用链接。用断言验证结构：

assertEquals(1, node0.value);
assertEquals(2, node0.next.value);
assertEquals(3, node0.next.next.value);

这些断言确认每个节点正确指向序列中的下一个节点。

❌ 尝试链接不同类型节点会导致编译错误。

5. 实现链表操作

基于前面的 Node 类，构建自定义单向链表。

5.1. 定义 CustomLinkedList 类

创建 CustomLinkedList 类：

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

    public CustomLinkedList() {
        head = null;
        tail = null;
        size = 0;
    }

    // ...
}

类中维护：

head 和 tail 节点引用
size 记录节点数量（初始为0）

创建空链表时，head 和 tail 均设为 null。

5.2. 在尾部插入元素

实现尾部插入方法：

public void insertTail(T value) {
    if (size == 0) {
        head = tail = new Node<>(value);
    } else {
        tail.next = new Node<>(value);
        tail = tail.next;
    }
    size++;
}

逻辑：

空链表时：head 和 tail 指向新节点
非空链表：新节点链接到当前 tail，然后更新 tail

5.3. 在头部插入元素

实现头部插入方法：

public void insertHead(T value) {
    Node<T> newNode = new Node<>(value);
    newNode.next = head;
    head = newNode;

    if (size == 0) {
        tail = newNode;
    }

    size++;
}

操作步骤：

新节点指向当前 head
head 更新为新节点
空链表时需同步更新 tail

5.4. 检索元素

实现按索引获取值：

public T get(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Index out of bounds");
    }

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

    return current.value;
}

关键点：

先校验索引有效性
遍历链表到指定索引
返回节点存储的值

5.5. 删除头节点

移除首元素只需更新 head 引用：

public void removeHead() {
    if (head == null) {
        return;
    }
    head = head.next;
    if (head == null) {
        tail = null;
    }
    size--;
}

处理逻辑：

head 指向下一个节点，原头节点被移除
链表变空时需将 tail 设为 null

5.6. 按索引删除节点

实现指定位置删除：

public void removeAtIndex(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Index out of bounds");
    }

    if (index == 0) {
        removeHead();
        return;
    }

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

    if (current.next == tail) {
        tail = current;
    }

    current.next = current.next.next;
    size--;
}

操作流程：

索引为0时复用 removeHead()
遍历到目标节点的前驱节点
更新 next 引用跳过目标节点
删除尾节点时更新 tail

5.7. 返回链表大小

添加获取链表长度方法：

public int size() {
    return size;
}

直接返回维护的 size 字段，该值在增删节点时自动更新。

6. 总结

本文实现了与 Java 内置 LinkedList 功能相似的自定义链表，包含： ✅ 头部/尾部插入 ✅ 按索引检索和删除 ✅ 动态大小维护

通过这个实践，深入理解了链表的底层实现机制，对后续优化或扩展数据结构大有裨益。

Persistence

REST

Security