【单链表的模拟实现Java】

单链表是一种基本的数据结构，它由一系列节点构成，每个节点包含数据部分和指向下一个节点的指针。在Java中，我们可以通过自定义类来模拟单链表的实现。下面我们将详细讲解单链表的基本操作，包括插入、删除、查找和遍历等，同时提供相关的代码示例。

单链表的节点类

首先，需要定义单链表的节点类。每个节点都包含一个数据域和一个指向下一个节点的引用。

class Node {
    int data; // 数据部分
    Node next; // 指向下一个节点的指针

    Node(int data) {
        this.data = data;
        this.next = null; // 初始化时指向null
    }
}

单链表类

接下来，我们需要定义一个单链表类，包含基本的操作方法，如插入、删除、查找和遍历。

class SinglyLinkedList {
    private Node head; // 表示链表的头节点

    public SinglyLinkedList() {
        this.head = null; // 初始化时链表为空
    }

    // 插入节点
    public void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode; // 如果链表为空，直接将新节点作为头节点
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next; // 遍历到链表的最后一个节点
            }
            current.next = newNode; // 将新节点插入到链表末尾
        }
    }

    // 删除节点
    public void delete(int key) {
        Node current = head;
        Node previous = null;

        // 如果头节点是目标节点
        if (current != null && current.data == key) {
            head = current.next; // 更改头节点
            return;
        }

        // 查找需要删除的节点
        while (current != null && current.data != key) {
            previous = current;
            current = current.next;
        }

        // 如果未找到节点
        if (current == null) {
            System.out.println("节点 " + key + " 不存在.");
            return;
        }

        // 解除当前节点的连接
        previous.next = current.next;
    }

    // 查找节点
    public boolean search(int key) {
        Node current = head;
        while (current != null) {
            if (current.data == key) {
                return true; // 找到节点
            }
            current = current.next;
        }
        return false; // 未找到节点
    }

    // 遍历链表
    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

示例代码

下面是如何使用上述单链表类的示例代码：

public class LinkedListDemo {
    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();

        // 插入节点
        list.insert(10);
        list.insert(20);
        list.insert(30);

        // 遍历链表
        System.out.println("链表内容:");
        list.display(); // 输出: 10 -> 20 -> 30 -> null

        // 查找节点
        System.out.println("查找 20: " + list.search(20)); // 输出: true
        System.out.println("查找 40: " + list.search(40)); // 输出: false

        // 删除节点
        list.delete(20);
        System.out.println("删除 20 后的链表:");
        list.display(); // 输出: 10 -> 30 -> null
    }
}

总结

通过以上实现，可以看到单链表的基本操作都是比较简单的。单链表在许多应用中非常有用，例如动态数组的替代方案、实现栈和队列等。掌握单链表的构建与操作，对学习更复杂的数据结构如双向链表、红黑树等都有着基础性的作用。