Java:理解单链表实现

单链表是一种常见的数据结构，它由一系列节点组成，每个节点包含两部分：数据和指向下一个节点的引用。单链表的特点是只能从头到尾进行遍历，不像数组那样可以通过索引直接访问元素。

基础概念

节点（Node）：链表的基本单位，包含数据域和指针域。

数据域：存储数据。
指针域：存储下一个节点的地址。

头节点（Head）：指向链表第一个有效节点的指针。

尾节点（Tail）：指向链表最后一个有效节点的指针，其指针域为空（null）。

实现单链表的优势

动态大小：链表的大小可以动态改变，不需要预先分配内存。
插入和删除效率高：在已知位置的情况下，插入和删除操作的时间复杂度为O(1)。
内存利用率高：不需要连续的内存空间，可以充分利用内存碎片。

类型

单向链表：每个节点只有一个指向下一个节点的指针。
双向链表：每个节点有两个指针，分别指向前一个和后一个节点。

应用场景

实现栈和队列：链表可以用来实现栈（LIFO）和队列（FIFO）。
动态数组：当数组大小需要频繁变化时，链表是一个很好的选择。
图的邻接表表示：在图论中，链表常用于表示图的邻接表。

示例代码：Java实现单链表

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class SinglyLinkedList {
    Node head;

    // 在链表末尾添加节点
    public void append(int data) {
        if (head == null) {
            head = new Node(data);
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = new Node(data);
    }

    // 在链表头部添加节点
    public void prepend(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    // 删除指定数据的节点
    public void delete(int data) {
        if (head == null) return;
        if (head.data == data) {
            head = head.next;
            return;
        }
        Node current = head;
        while (current.next != null && current.next.data != data) {
            current = current.next;
        }
        if (current.next != null) {
            current.next = current.next.next;
        }
    }

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

public class Main {
    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        list.append(1);
        list.append(2);
        list.append(3);
        list.prepend(0);
        list.printList(); // 输出: 0 -> 1 -> 2 -> 3 -> null
        list.delete(2);
        list.printList(); // 输出: 0 -> 1 -> 3 -> null
    }
}