enyang

Menu

enyang
enyang
Published on 2025-11-27 / 2 Visits
0
0

数据结构<2>——链表

#Data Structures

1 链表的定义

1.1 什么是链表

链表（Linked List）是一种非连续存储的数据结构，由若干节点通过指针连接组成。
每个节点通常包含两部分：

  1. 数据域（Data）：存储节点数据。

  2. 指针域（Next）：存储指向下一个节点的引用。

在 Java 中，一个单向链表节点可以定义为：

class Node {
    int data;  // 存储数据
    Node next; // 指向下一个节点

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

链表与数组不同，它在内存中不要求连续空间。访问第 k 个元素时，需要从头节点依次遍历。

1.2 链表的特点

  1. 动态内存

    • 链表的节点可以按需创建，不需要提前确定链表长度。

  2. 高效插入与删除

    • 在链表中插入或删除节点，只需修改指针即可，不需要移动大量元素。

    • 当有前驱节点时，时间复杂度为 O(1)。

  3. 顺序访问

    • 链表不支持随机访问，需要从头节点依次遍历。

    • 查找第 k 个元素的时间复杂度为 O(n)。

  4. 额外空间开销

    • 每个节点都需要存储指针，因此相比数组有一定内存开销。

1.3 链表的分类

1.3.1 单向链表（Singly Linked List）

  • 每个节点只包含一个指针，指向下一个节点。

  • 只能从头到尾顺序访问。

Java 单向链表节点定义：

class Node {
    int data;
    Node next;

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

1.3.2 双向链表（Doubly Linked List）

  • 每个节点包含两个指针，分别指向前一个节点和下一个节点。

  • 可以从头或尾遍历链表。

Java 双向链表节点定义：

class DoublyNode {
    int data;
    DoublyNode prev; // 指向前一个节点
    DoublyNode next; // 指向下一个节点

    public DoublyNode(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

1.3.3 循环链表（Circular Linked List）

  • 链表尾节点指向头节点，形成环形结构。

  • 可以单向或双向循环遍历，常用于循环队列或游戏中。

Java 单向循环链表示例：

class CircularNode {
    int data;
    CircularNode next;

    public CircularNode(int data) {
        this.data = data;
        this.next = this; // 指向自身，形成循环
    }
}

1.4 链表与数组对比

  • 内存：数组连续，链表非连续。

  • 插入/删除：数组移动元素 O(n)，链表修改指针 O(1)。

  • 查找：数组支持随机访问 O(1)，链表只能顺序访问 O(n)。

  • 空间开销：数组少，链表每个节点需要额外指针。

2 链表的结构与基本操作

2.1 链表结构

链表由节点组成，每个节点至少包含数据和指针域。链表通常需要一个**头节点（head）**来标记链表的起始位置。

Java 单向链表类示例：

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

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

这里的 Node 是之前定义的单向链表节点：

class Node {
    int data;
    Node next;

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

  • head：指向链表的第一个节点，如果链表为空，head 为 null。

  • next：指向下一个节点，如果是最后一个节点，next 为 null。

2.2 头插法（在链表头部插入节点）

头插法是指将新节点插入到链表的最前端。

  1. 创建新节点 newNode。

  2. 将新节点的 next 指向当前 head。

  3. 更新 head 为新节点。

public void insertAtHead(int data) {
    Node newNode = new Node(data);
    newNode.next = head; // 新节点指向原来的头节点
    head = newNode;      // 更新头节点为新节点
}

  • 时间复杂度：O(1)

  • 特点：操作简单、效率高，不需要遍历链表。

2.3 尾插法（在链表尾部插入节点）

尾插法是将新节点插入到链表的末尾。

  1. 创建新节点 newNode。

  2. 如果链表为空，将 head 指向新节点。

  3. 否则，从头遍历链表找到最后一个节点。

  4. 将最后一个节点的 next 指向新节点。

public void insertAtTail(int 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; // 最后节点指向新节点
}

  • 时间复杂度：O(n)

  • 特点：适合追加节点，但需要遍历整个链表。

2.4 在指定位置插入节点

可以在链表中任意位置插入节点（位置从0开始计数）。

  1. 如果位置为0，使用头插法。

  2. 遍历到第 k−1 个节点。

  3. 将新节点的 next 指向第 k 个节点。

  4. 将第 k−1 个节点的 next 指向新节点。

public void insertAtPosition(int data, int index) {
    if (index < 0) return;

    if (index == 0) {
        insertAtHead(data);
        return;
    }

    Node newNode = new Node(data);
    Node current = head;
    int count = 0;

    while (current != null && count < index - 1) {
        current = current.next;
        count++;
    }

    if (current == null) return; // 超过链表长度

    newNode.next = current.next;
    current.next = newNode;
}

  • 时间复杂度：O(n)

  • 特点：可以灵活控制插入位置。

2.5 删除节点

按值删除链表中的节点。

  1. 如果头节点就是要删除的节点，直接更新 head。

  2. 遍历链表找到要删除节点的前驱节点。

  3. 修改前驱节点的 next 指向要删除节点的下一个节点。

public void deleteNode(int key) {
    if (head == null) return;

    if (head.data == key) {
        head = head.next; // 删除头节点
        return;
    }

    Node current = head;
    while (current.next != null && current.next.data != key) {
        current = current.next;
    }

    if (current.next != null) {
        current.next = current.next.next; // 删除节点
    }
}

  • 时间复杂度：O(n)

  • 特点：链表删除灵活，不需要移动元素。

2.6 查找节点

在链表中查找值为 key 的节点。

public boolean search(int key) {
    Node current = head;
    while (current != null) {
        if (current.data == key) return true;
        current = current.next;
    }
    return false;
}

  • 时间复杂度：O(n)

  • 返回 true 表示找到，false 表示未找到。

2.7 遍历链表

依次访问链表的每个节点并输出数据。

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

  • 时间复杂度：O(n)

  • 用于打印或处理链表中的所有元素。

3 双向链表和循环链表

3.1 双向链表（Doubly Linked List）

双向链表是链表的一种变体，每个节点包含两个指针：

  • prev 指向前一个节点

  • next 指向下一个节点

相比单向链表，双向链表可以从前往后或从后往前遍历，更加灵活。

3.1.1 双向链表节点定义

class DoublyNode {
    int data;
    DoublyNode prev;
    DoublyNode next;

    public DoublyNode(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

3.1.2 双向链表结构

class DoublyLinkedList {
    DoublyNode head;

    public DoublyLinkedList() {
        head = null;
    }
}

3.1.3 双向链表的插入操作

头插法
public void insertAtHead(int data) {
    DoublyNode newNode = new DoublyNode(data);
    if (head != null) {
        newNode.next = head;
        head.prev = newNode;
    }
    head = newNode;
}
尾插法
public void insertAtTail(int data) {
    DoublyNode newNode = new DoublyNode(data);
    if (head == null) {
        head = newNode;
        return;
    }
    DoublyNode current = head;
    while (current.next != null) {
        current = current.next;
    }
    current.next = newNode;
    newNode.prev = current;
}
指定位置插入
public void insertAtPosition(int data, int index) {
    if (index < 0) return;
    if (index == 0) {
        insertAtHead(data);
        return;
    }

    DoublyNode current = head;
    int count = 0;
    while (current != null && count < index - 1) {
        current = current.next;
        count++;
    }
    if (current == null) return;

    DoublyNode newNode = new DoublyNode(data);
    newNode.next = current.next;
    newNode.prev = current;

    if (current.next != null) {
        current.next.prev = newNode;
    }
    current.next = newNode;
}

3.1.4 双向链表删除节点

public void deleteNode(int key) {
    if (head == null) return;

    DoublyNode current = head;
    while (current != null && current.data != key) {
        current = current.next;
    }
    if (current == null) return;

    if (current.prev != null) {
        current.prev.next = current.next;
    } else {
        head = current.next; // 删除头节点
    }

    if (current.next != null) {
        current.next.prev = current.prev;
    }
}

3.1.5 遍历双向链表

从头到尾
public void traverseForward() {
    DoublyNode current = head;
    while (current != null) {
        System.out.print(current.data + " ");
        current = current.next;
    }
    System.out.println();
}
从尾到头
public void traverseBackward() {
    if (head == null) return;
    DoublyNode current = head;
    while (current.next != null) {
        current = current.next;
    }
    while (current != null) {
        System.out.print(current.data + " ");
        current = current.prev;
    }
    System.out.println();
}

3.2 循环链表（Circular Linked List）

循环链表是链表的一种特殊形式，尾节点指向头节点，形成环形结构。

  • 单向循环链表：每个节点只指向下一个节点

  • 双向循环链表：每个节点同时有 prev 和 next 指针，尾节点指向头节点，头节点的 prev 指向尾节点

3.2.1 单向循环链表节点定义

class CircularNode {
    int data;
    CircularNode next;

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

3.2.2 单向循环链表插入

尾插法
class CircularLinkedList {
    CircularNode head;

    public CircularLinkedList() {
        head = null;
    }

    public void insertAtTail(int data) {
        CircularNode newNode = new CircularNode(data);
        if (head == null) {
            head = newNode;
            head.next = head; // 自己指向自己
            return;
        }
        CircularNode current = head;
        while (current.next != head) {
            current = current.next;
        }
        current.next = newNode;
        newNode.next = head;
    }
}

3.2.3 遍历循环链表

public void traverse() {
    if (head == null) return;
    CircularNode current = head;
    do {
        System.out.print(current.data + " ");
        current = current.next;
    } while (current != head);
    System.out.println();
}

  • 注意循环链表遍历需要用 do-while 防止跳过头节点或无限循环。

4 链表的应用与常见面试题

链表不仅是基础数据结构，在实际编程中也有广泛应用。常见应用包括：栈、队列、LRU 缓存、图的邻接表等。同时，链表题目在面试中非常常见，例如反转链表、合并链表、判断环等。

4.1 反转单向链表

将链表从头到尾的顺序反转。

思路

  • 使用三个指针：prev、current、next

  • 遍历链表，将 current.next 指向 prev

  • 遍历完成后，head 指向 prev

Java 实现

public Node reverseList(Node head) {
    Node prev = null;
    Node current = head;
    while (current != null) {
        Node next = current.next; // 保存下一个节点
        current.next = prev;      // 反转指针
        prev = current;
        current = next;
    }
    return prev; // 返回新头节点
}

  • 时间复杂度：O(n)

  • 空间复杂度：O(1)

4.2 判断链表是否有环

判断链表是否形成环（循环链表）。

思路（快慢指针法）

  • 设置两个指针：slow 每次走一步，fast 每次走两步

  • 如果链表有环，fast 会追上 slow

Java 实现

public boolean hasCycle(Node head) {
    if (head == null) return false;
    Node slow = head;
    Node fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

  • 时间复杂度：O(n)

  • 空间复杂度：O(1)

4.3 合并两个有序链表

将两个按升序排列的链表合并为一个有序链表。

思路

  • 创建虚拟头节点 dummy

  • 用指针 current 指向当前节点

  • 遍历两个链表，将较小的节点接入 current.next

Java 实现

public Node mergeTwoLists(Node l1, Node l2) {
    Node dummy = new Node(0);
    Node current = dummy;

    while (l1 != null && l2 != null) {
        if (l1.data < l2.data) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }

    if (l1 != null) current.next = l1;
    if (l2 != null) current.next = l2;

    return dummy.next;
}

  • 时间复杂度：O(n + m)

  • 空间复杂度：O(1)

4.4 删除链表倒数第 n 个节点

删除链表中倒数第 n 个节点。

思路（双指针）

  • 设置两个指针：first 和 second

  • first 先走 n 步，然后 first 和 second 同步前进

  • 当 first 到达末尾时，second.next 就是要删除节点

Java 实现

public Node removeNthFromEnd(Node head, int n) {
    Node dummy = new Node(0);
    dummy.next = head;
    Node first = dummy;
    Node second = dummy;

    for (int i = 0; i <= n; i++) {
        first = first.next;
    }

    while (first != null) {
        first = first.next;
        second = second.next;
    }

    second.next = second.next.next;
    return dummy.next;
}

  • 时间复杂度：O(n)

  • 空间复杂度：O(1)

4.5 链表的实际应用

  1. 栈和队列

    • 栈可用单链表头插法实现

    • 队列可用单链表尾插法和头删除实现

  2. LRU缓存

    • 用双向链表和 HashMap 实现 O(1) 时间复杂度的访问和删除

  3. 图的邻接表

    • 用链表存储每个顶点的邻接节点

  4. 内存管理

    • 操作系统管理空闲内存块时也可使用链表

数据结构<3>——栈
数据结构<1>——数组

Comment