Java链表创建与遍历方法详解

Java链表是用节点和引用关系模拟链式存储结构，核心操作包括定义节点类、创建链表、遍历、插入与删除节点。1. 节点类包含数据和指向下一节点的引用，使用泛型支持多种数据类型；2. 创建链表可通过append方法逐步添加节点；3. 遍历链表可使用循环或递归方式；4. 插入节点需找到前一节点并调整引用；5. 删除节点同样需调整引用以跳过目标节点；6. 链表适合频繁插入删除场景，数组适合频繁访问场景；7. 检测链表环可使用快慢指针法；8. 链表可用于实现栈和队列，具备动态扩展优势。

Java链表，说白了，就是用Java代码模拟链式存储结构。核心在于节点（Node）和节点间的引用关系。创建链表就是构建这些节点，遍历则是沿着引用关系访问每个节点。

首先，定义节点类。接着，实现链表的增删改查等操作。最后，通过遍历验证链表的正确性。

链表节点类的定义

链表是由一个个节点组成的，每个节点包含数据和指向下一个节点的引用。

class Node {
    T data;
    Node next;

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

这里使用了泛型T，使得链表可以存储各种类型的数据。next 属性指向下一个节点，初始值为 null。

创建链表

创建链表的方式有很多种，可以从空链表开始逐步添加节点，也可以直接用数组或其他数据结构初始化。

class LinkedList {
    Node head; // 链表的头节点

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

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

这段代码实现了append方法，用于在链表末尾添加节点。如果链表为空，则将新节点设置为头节点；否则，遍历到链表末尾，将新节点添加到末尾。

链表遍历的几种方法

遍历链表就是访问链表中的每个节点。常用的方法有循环遍历和递归遍历。

循环遍历

public void printList() {
    Node current = head;
    while (current != null) {
        System.out.print(current.data + " ");
        current = current.next;
    }
    System.out.println();
}

这种方式简单直接，易于理解。从头节点开始，依次访问每个节点，直到到达链表末尾。

递归遍历

public void printListRecursive(Node node) {
    if (node == null) {
        return;
    }
    System.out.print(node.data + " ");
    printListRecursive(node.next);
}

// 调用递归遍历
public void printListRecursive() {
    printListRecursive(head);
    System.out.println();
}

递归方式更简洁，但需要注意避免栈溢出，特别是对于长链表。

如何在链表中插入节点

插入节点需要找到插入位置的前一个节点，然后修改引用关系。

public void insertAfter(Node prevNode, T data) {
    if (prevNode == null) {
        System.out.println("Previous node cannot be null");
        return;
    }
    Node newNode = new Node<>(data);
    newNode.next = prevNode.next;
    prevNode.next = newNode;
}

这段代码实现了在指定节点后插入新节点的功能。

如何从链表中删除节点

删除节点也需要找到待删除节点的前一个节点，然后修改引用关系。

public void deleteNode(T key) {
    Node current = head, prev = null;

    // 如果头节点就是要删除的节点
    if (current != null && current.data.equals(key)) {
        head = current.next; // Changed head
        return;
    }

    // 找到要删除的节点
    while (current != null && !current.data.equals(key)) {
        prev = current;
        current = current.next;
    }

    // 如果没找到
    if (current == null) {
        return;
    }

    // 删除节点
    prev.next = current.next;
}

这段代码实现了删除链表中指定值的节点的功能。

链表与数组的性能比较：何时使用链表更合适

数组在内存中是连续存储的，可以通过索引快速访问元素，但在插入和删除元素时需要移动大量元素。链表则相反，插入和删除元素只需要修改引用关系，但访问元素需要从头节点开始遍历。

因此，如果需要频繁进行插入和删除操作，且对访问速度要求不高，链表更合适。如果需要频繁访问元素，且插入和删除操作较少，数组更合适。

如何检测链表是否存在环

检测链表是否存在环是一个经典问题，常用的方法是快慢指针（Floyd 算法）。

public boolean hasCycle() {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true; // 存在环
        }
    }
    return false; // 不存在环
}

快指针每次移动两步，慢指针每次移动一步。如果链表存在环，快慢指针最终会相遇。

链表的常见应用场景：栈和队列的实现

链表可以用来实现栈和队列。栈是一种后进先出（LIFO）的数据结构，队列是一种先进先出（FIFO）的数据结构。

用链表实现栈

class LinkedStack {
    private Node top;

    public void push(T data) {
        Node newNode = new Node<>(data);
        newNode.next = top;
        top = newNode;
    }

    public T pop() {
        if (top == null) {
            return null;
        }
        T data = top.data;
        top = top.next;
        return data;
    }
}

用链表实现队列

class LinkedQueue {
    private Node head, tail;

    public void enqueue(T data) {
        Node newNode = new Node<>(data);
        if (tail == null) {
            head = tail = newNode;
            return;
        }
        tail.next = newNode;
        tail = newNode;
    }

    public T dequeue() {
        if (head == null) {
            return null;
        }
        T data = head.data;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        return data;
    }
}

链表实现的栈和队列在动态扩展方面具有优势，不需要预先分配固定大小的内存空间。