数据结构中的链表详解（Java实现）

链表（Linked List）是一种基础但极其重要的数据结构，适用于动态数据存储和高效插入/删除操作。本文将从基础概念讲起，逐步深入单链表、双链表、循环链表等结构，并辅以Java代码示例和逻辑图示。

---

一、链表与数组的对比

• 数组：内存连续，支持快速随机访问（时间复杂度O(1)），但插入/删除需要移动元素（时间复杂度O(n)）。
• 链表：内存非连续，通过指针连接节点，插入/删除仅需修改指针（时间复杂度O(1)），但访问元素需遍历（时间复杂度O(n)）。

---

二、单链表（Singly Linked List）

1. 结构

• 每个节点包含两部分：数据域和指针域（指向下一个节点）。
• 头节点（Head）是链表的入口，尾节点（Next）指向null。

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

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

2. 基本操作

• 插入节点：
  • 头部插入：新节点指向原头节点，更新头节点。
  • 中间插入：找到插入位置的前驱节点，修改指针。
  • 尾部插入：遍历到尾节点，修改尾节点的指针。

// 头部插入示例
public void addFirst(T data) {
    Node<T> newNode = new Node<>(data);
    newNode.next = head;
    head = newNode;
}

• 删除节点：
  • 头部删除：头节点指向下一个节点。
  • 中间/尾部删除：找到前驱节点，修改指针。

// 删除指定值的节点
public void remove(T data) {
    if (head == null) return;
    if (head.data.equals(data)) {
        head = head.next;
        return;
    }
    Node<T> current = head;
    while (current.next != null && !current.next.data.equals(data)) {
        current = current.next;
    }
    if (current.next != null) {
        current.next = current.next.next;
    }
}

3. 逻辑图示

Head -> [A|next] -> [B|next] -> [C|next] -> null

---

三、双链表（Doubly Linked List）

1. 结构

• 每个节点包含前驱指针（prev）、数据域和后继指针（next）。
• 支持双向遍历，但占用更多内存。

class DNode<T> {
    T data;
    DNode<T> prev;
    DNode<T> next;

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

2. 插入与删除

• 插入节点：需修改前驱和后继节点的指针。
• 删除节点：需修改相邻节点的指针。

// 在指定节点后插入新节点
public void insertAfter(DNode<T> node, T data) {
    DNode<T> newNode = new DNode<>(data);
    newNode.prev = node;
    newNode.next = node.next;
    if (node.next != null) {
        node.next.prev = newNode;
    }
    node.next = newNode;
}

3. 逻辑图示

null <-> [A|prev|next] <-> [B|prev|next] <-> [C|prev|next] <-> null

---

四、循环链表（Circular Linked List）

1. 单循环链表

• 尾节点的next指向头节点，形成环。
• 适用于轮询调度（如操作系统进程调度）。

// 单循环链表的尾部插入
public void addLast(T data) {
    Node<T> newNode = new Node<>(data);
    if (head == null) {
        head = newNode;
        head.next = head; // 指向自己
    } else {
        Node<T> current = head;
        while (current.next != head) {
            current = current.next;
        }
        current.next = newNode;
        newNode.next = head;
    }
}

2. 双循环链表

• 头节点的prev指向尾节点，尾节点的next指向头节点。

Head <-> [A] <-> [B] <-> [C] <-> Head

---

五、链表的应用场景

1. 单链表：实现栈、队列、简单缓存。
2. 双链表：浏览器历史记录（前进/后退）、LRU缓存。
3. 循环链表：音乐播放列表循环、约瑟夫问题。

---

六、时间复杂度总结

操作	单链表	双链表
插入/删除	O(1)*	O(1)*
访问	O(n)	O(n)
搜索	O(n)	O(n)

*假设已定位到操作位置，否则需O(n)时间查找。

---

七、完整Java示例（单链表）

public class SinglyLinkedList<T> {
    private Node<T> head;

    // 节点类
    private static class Node<T> {
        T data;
        Node<T> next;
        public Node(T data) {
            this.data = data;
            this.next = null;
        }
    }

    // 头部插入
    public void addFirst(T data) {
        Node<T> newNode = new Node<>(data);
        newNode.next = head;
        head = newNode;
    }

    // 尾部插入
    public void addLast(T data) {
        Node<T> newNode = new Node<>(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node<T> current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    // 删除节点
    public void remove(T data) {
        if (head == null) return;
        if (head.data.equals(data)) {
            head = head.next;
            return;
        }
        Node<T> current = head;
        while (current.next != null && !current.next.data.equals(data)) {
            current = current.next;
        }
        if (current.next != null) {
            current.next = current.next.next;
        }
    }

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

    public static void main(String[] args) {
        SinglyLinkedList<Integer> list = new SinglyLinkedList<>();
        list.addFirst(3);
        list.addFirst(2);
        list.addFirst(1);
        list.addLast(4);
        list.print(); // 输出: 1 -> 2 -> 3 -> 4 -> null
        list.remove(3);
        list.print(); // 输出: 1 -> 2 -> 4 -> null
    }
}

---

通过理解链表的核心思想，掌握指针操作技巧，并结合实际场景选择不同链表类型，您将能够高效解决各类动态数据处理问题！