2025-05-30

链表

C 语言中的链表节点定义

在 C 语言中，我们通常使用结构体（struct）来定义链表的节点。

#include <stdio.h>
#include <stdlib.h> // 包含 malloc 和 free 函数

// 定义链表节点结构体
typedef struct Node {
    int data;          // 数据域，这里以整型为例，也可以是其他类型
    struct Node *next; // 指针域，指向下一个节点的指针
} Node;

// 为了方便，我们经常定义一个指向 Node 的指针类型
// typedef struct Node* LinkList; // 另一种定义方式

链表的基本操作

1 创建新节点

创建新节点是链表操作的基础。我们需要使用 malloc 为新节点分配内存，并初始化其数据和指针。

// 创建一个新节点
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // 分配内存
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(1); // 退出程序
    }
    newNode->data = value; // 设置数据
    newNode->next = NULL;  // 新节点的next指针初始为NULL
    return newNode;
}

2 链表的初始化（创建空链表）

空链表通常用一个 NULL 指针表示。

// 初始化一个空链表（头指针）
Node* initLinkedList() {
    return NULL; // 空链表的头指针指向NULL
}

3 在链表头部插入节点

这是最简单的插入操作。

// 在链表头部插入节点
Node* insertAtHead(Node* head, int value) {
    Node* newNode = createNode(value);
    newNode->next = head; // 新节点的next指向原来的头节点
    return newNode;        // 返回新节点作为新的头节点
}

4 在链表尾部插入节点

需要遍历链表找到尾节点，然后将其 next 指针指向新节点。

// 在链表尾部插入节点
Node* insertAtTail(Node* head, int value) {
    Node* newNode = createNode(value);
    if (head == NULL) { // 如果链表为空，新节点就是头节点
        return newNode;
    }

    Node* current = head;
    while (current->next != NULL) { // 遍历到链表尾部
        current = current->next;
    }
    current->next = newNode; // 尾节点的next指向新节点
    return head;             // 返回原来的头节点
}

5 遍历链表并打印数据

这是最常用的操作之一，用于查看链表中的所有元素。

// 打印链表所有节点的数据
void printLinkedList(Node* head) {
    Node* current = head;
    printf("链表内容：");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

6 查找节点

根据数据查找特定节点。

// 查找链表中是否存在某个值的节点
Node* findNode(Node* head, int value) {
    Node* current = head;
    while (current != NULL) {
        if (current->data == value) {
            return current; // 找到，返回该节点指针
        }
        current = current->next;
    }
    return NULL; // 未找到
}

7 删除节点

删除指定值的节点。这里我们处理了三种情况：删除头节点、删除中间节点、删除不存在的节点。

// 删除链表中指定值的节点
Node* deleteNode(Node* head, int value) {
    if (head == NULL) {
        return NULL; // 链表为空
    }

    // 如果要删除的是头节点
    if (head->data == value) {
        Node* temp = head;
        head = head->next; // 新的头节点是原头节点的next
        free(temp);        // 释放原头节点内存
        return head;
    }

    Node* current = head;
    while (current->next != NULL && current->next->data != value) {
        current = current->next;
    }

    // 找到要删除的节点（current->next）
    if (current->next != NULL) {
        Node* temp = current->next; // 待删除节点
        current->next = temp->next; // current的next指向待删除节点的next
        free(temp);                 // 释放待删除节点内存
    } else {
        printf("未找到值为 %d 的节点进行删除。\n", value);
    }
    return head;
}

8 释放链表内存

完成链表操作后，务必释放所有节点的内存，避免内存泄漏。

// 释放链表所有节点的内存
void freeLinkedList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        Node* temp = current; // 临时保存当前节点
        current = current->next; // 移动到下一个节点
        free(temp); // 释放当前节点内存
    }
    printf("链表内存已释放。\n");
}

完整示例代码

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构体
typedef struct Node {
    int data;
    struct Node *next;
} Node;

// 创建一个新节点
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

// 在链表头部插入节点
Node* insertAtHead(Node* head, int value) {
    Node* newNode = createNode(value);
    newNode->next = head;
    return newNode;
}

// 在链表尾部插入节点
Node* insertAtTail(Node* head, int value) {
    Node* newNode = createNode(value);
    if (head == NULL) {
        return newNode;
    }
    Node* current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
    return head;
}

// 打印链表所有节点的数据
void printLinkedList(Node* head) {
    Node* current = head;
    printf("链表内容：");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// 查找链表中是否存在某个值的节点
Node* findNode(Node* head, int value) {
    Node* current = head;
    while (current != NULL) {
        if (current->data == value) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

// 删除链表中指定值的节点
Node* deleteNode(Node* head, int value) {
    if (head == NULL) {
        printf("链表为空，无法删除。\n");
        return NULL;
    }

    // 如果要删除的是头节点
    if (head->data == value) {
        Node* temp = head;
        head = head->next;
        free(temp);
        printf("成功删除头节点 %d。\n", value);
        return head;
    }

    Node* current = head;
    while (current->next != NULL && current->next->data != value) {
        current = current->next;
    }

    // 找到要删除的节点（current->next）
    if (current->next != NULL) {
        Node* temp = current->next;
        current->next = temp->next;
        free(temp);
        printf("成功删除节点 %d。\n", value);
    } else {
        printf("未找到值为 %d 的节点进行删除。\n", value);
    }
    return head;
}

// 释放链表所有节点的内存
void freeLinkedList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        Node* temp = current;
        current = current->next;
        free(temp);
    }
    printf("链表内存已释放。\n");
}

int main() {
    Node* head = NULL; // 初始化空链表

    printf("------ 插入操作 ------\n");
    head = insertAtHead(head, 10); // 10 -> NULL
    printLinkedList(head);
    
    head = insertAtTail(head, 20); // 10 -> 20 -> NULL
    printLinkedList(head);
    
    head = insertAtHead(head, 5);  // 5 -> 10 -> 20 -> NULL
    printLinkedList(head);

    head = insertAtTail(head, 30); // 5 -> 10 -> 20 -> 30 -> NULL
    printLinkedList(head);

    printf("\n------ 查找操作 ------\n");
    if (findNode(head, 10) != NULL) {
        printf("找到了值为 10 的节点。\n");
    } else {
        printf("未找到值为 10 的节点。\n");
    }

    if (findNode(head, 100) != NULL) {
        printf("找到了值为 100 的节点。\n");
    } else {
        printf("未找到值为 100 的节点。\n");
    }

    printf("\n------ 删除操作 ------\n");
    head = deleteNode(head, 5); // 删除头节点
    printLinkedList(head);
    
    head = deleteNode(head, 20); // 删除中间节点
    printLinkedList(head);

    head = deleteNode(head, 100); // 删除不存在的节点
    printLinkedList(head);

    head = deleteNode(head, 30); // 删除最后一个节点
    printLinkedList(head);
    
    head = deleteNode(head, 10); // 删除最后一个节点（现在是头节点）
    printLinkedList(head);


    printf("\n------ 内存释放 ------\n");
    // 再次插入一些节点用于测试内存释放
    head = insertAtTail(head, 1);
    head = insertAtTail(head, 2);
    printLinkedList(head);
    freeLinkedList(head); // 释放所有内存
    head = NULL; // 释放后将头指针设为NULL，避免野指针
    
    // 尝试打印已释放的链表，会输出NULL
    printLinkedList(head); 

    return 0;
}

链表的变种

除了上面介绍的单向链表，还有其他几种常见的链表类型：

双向链表（Doubly Linked List）： 每个节点除了指向下一个节点的指针 next 外，还包含一个指向前一个节点的指针 prev。这使得链表可以双向遍历，但需要额外的空间存储 prev 指针。
循环链表（Circular Linked List）： 链表的最后一个节点的 next 指针不是 NULL，而是指向头节点，形成一个环。

双向链表

什么是双向链表？

双向链表，顾名思义，就是每个节点不仅知道“下一个”是谁，也知道“上一个”是谁。它在单向链表的基础上，为每个节点额外增加了一个指向前一个节点的指针。

双向链表节点的结构：

#include <stdio.h>
#include <stdlib.h>

// 定义双向链表节点结构体
typedef struct DoublyNode {
    int data;                 // 数据域
    struct DoublyNode *prev;  // 指向前一个节点的指针
    struct DoublyNode *next;  // 指向下一个节点的指针
} DoublyNode;

特点：

双向遍历： 可以从头到尾遍历，也可以从尾到头遍历。
插入和删除更灵活： 在已知待操作节点的情况下，其前驱和后继节点都可以直接访问，从而简化了插入和删除操作（特别是删除指定节点）。
空间开销增加： 每个节点需要额外存储一个 prev 指针，因此比单向链表占用更多内存。

双向链表的基本操作

我们将重点展示与单向链表不同的或更高效的操作。

创建新节点

// 创建一个双向链表新节点
DoublyNode* createDoublyNode(int value) {
    DoublyNode* newNode = (DoublyNode*)malloc(sizeof(DoublyNode));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    newNode->data = value;
    newNode->prev = NULL; // 新节点的prev和next初始都为NULL
    newNode->next = NULL;
    return newNode;
}

在链表头部插入节点

// 在双向链表头部插入节点
DoublyNode* insertDoublyAtHead(DoublyNode* head, int value) {
    DoublyNode* newNode = createDoublyNode(value);
    if (head == NULL) { // 如果链表为空
        return newNode;
    }
    newNode->next = head; // 新节点指向原来的头节点
    head->prev = newNode; // 原头节点的prev指向新节点
    return newNode;       // 返回新节点作为新的头节点
}

在链表尾部插入节点

// 在双向链表尾部插入节点
DoublyNode* insertDoublyAtTail(DoublyNode* head, int value) {
    DoublyNode* newNode = createDoublyNode(value);
    if (head == NULL) { // 如果链表为空
        return newNode;
    }
    DoublyNode* current = head;
    while (current->next != NULL) { // 遍历到链表尾部
        current = current->next;
    }
    current->next = newNode; // 尾节点的next指向新节点
    newNode->prev = current; // 新节点的prev指向原来的尾节点
    return head;
}

在指定节点后插入

这是双向链表的一个便利之处，单向链表需要找到前驱节点。

// 在指定节点后面插入新节点
void insertAfterNode(DoublyNode* node, int value) {
    if (node == NULL) {
        printf("无法在空节点后插入。\n");
        return;
    }
    DoublyNode* newNode = createDoublyNode(value);
    newNode->next = node->next; // 新节点指向node的下一个节点
    newNode->prev = node;       // 新节点指向node

    if (node->next != NULL) { // 如果node不是最后一个节点
        node->next->prev = newNode; // node的下一个节点的prev指向新节点
    }
    node->next = newNode;       // node的next指向新节点
}

删除指定节点（已知节点指针）

这也是双向链表删除操作的优势。

// 删除指定节点（给定节点指针）
// 注意：如果删除的是头节点，需要更新头指针
DoublyNode* deleteGivenDoublyNode(DoublyNode* head, DoublyNode* nodeToDelete) {
    if (head == NULL || nodeToDelete == NULL) {
        return head; // 链表为空或待删除节点为空
    }

    if (nodeToDelete == head) { // 删除头节点
        head = nodeToDelete->next;
        if (head != NULL) {
            head->prev = NULL;
        }
    } else {
        nodeToDelete->prev->next = nodeToDelete->next; // 前驱节点的next指向待删除节点的next
        if (nodeToDelete->next != NULL) { // 如果不是尾节点
            nodeToDelete->next->prev = nodeToDelete->prev; // 后继节点的prev指向待删除节点的prev
        }
    }
    free(nodeToDelete); // 释放内存
    return head;
}

遍历双向链表（正向和反向）

// 正向打印双向链表
void printDoublyLinkedListForward(DoublyNode* head) {
    DoublyNode* current = head;
    printf("双向链表（正向）：");
    while (current != NULL) {
        printf("%d <-> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// 反向打印双向链表
void printDoublyLinkedListBackward(DoublyNode* head) {
    if (head == NULL) {
        printf("双向链表（反向）：NULL\n");
        return;
    }
    DoublyNode* current = head;
    while (current->next != NULL) { // 先找到尾节点
        current = current->next;
    }
    printf("双向链表（反向）：");
    while (current != NULL) {
        printf("%d <-> ", current->data);
        current = current->prev;
    }
    printf("NULL\n");
}

释放双向链表内存

// 释放双向链表所有节点的内存
void freeDoublyLinkedList(DoublyNode* head) {
    DoublyNode* current = head;
    while (current != NULL) {
        DoublyNode* temp = current;
        current = current->next;
        free(temp);
    }
    printf("双向链表内存已释放。\n");
}

循环链表（Circular Linked List）

什么是循环链表？

循环链表是一种特殊的单向链表（也可以是双向的）。它的最后一个节点的 next 指针不是指向 NULL，而是指向链表的头节点，形成一个环。

循环链表节点的结构（与单向链表相同）：

// 定义循环链表节点结构体 (与单向链表相同)
typedef struct CircularNode {
    int data;
    struct CircularNode *next;
} CircularNode;

特点：

无“尾”概念： 链表中没有真正的“尾节点”（其 next 指向 NULL 的节点），遍历可以无限进行下去，直到回到起点。
从任何节点开始遍历： 从链表中的任何一个节点开始，都可以遍历到所有节点。
插入删除无需特殊处理头尾： 插入和删除操作相对单向链表在处理头尾时更统一。
遍历需要停止条件： 需要额外的逻辑来判断是否已经遍历了一圈，避免无限循环。

2 循环链表的基本操作

由于循环链表的结构与单向链表相似，许多操作逻辑是类似的，但需要注意“环”的特性。为了简化，我们通常会维护一个指向尾节点的指针，而不是头节点。因为通过尾节点，可以 O(1) 时间访问到头节点（tail->next 就是头节点）。

创建新节点（与单向链表相同）

// 创建一个循环链表新节点
CircularNode* createCircularNode(int value) {
    CircularNode* newNode = (CircularNode*)malloc(sizeof(CircularNode));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = NULL; // 初始时指向NULL
    return newNode;
}

循环链表的初始化（返回尾指针）

// 初始化一个空循环链表（返回尾指针）
CircularNode* initCircularLinkedList() {
    return NULL; // 空循环链表的尾指针指向NULL
}

在链表头部插入节点

// 在循环链表头部插入节点 (tail指向尾节点)
CircularNode* insertCircularAtHead(CircularNode* tail, int value) {
    CircularNode* newNode = createCircularNode(value);
    if (tail == NULL) { // 链表为空时，新节点就是头也是尾
        newNode->next = newNode; // 自己指向自己
        return newNode;
    } else {
        newNode->next = tail->next; // 新节点指向原来的头节点
        tail->next = newNode;       // 尾节点指向新节点
        return tail;                // 返回尾节点
    }
}

在链表尾部插入节点

// 在循环链表尾部插入节点 (tail指向尾节点)
CircularNode* insertCircularAtTail(CircularNode* tail, int value) {
    CircularNode* newNode = createCircularNode(value);
    if (tail == NULL) { // 链表为空时，新节点就是头也是尾
        newNode->next = newNode;
    } else {
        newNode->next = tail->next; // 新节点指向头节点
        tail->next = newNode;       // 原尾节点指向新节点
    }
    return newNode; // 返回新节点作为新的尾节点
}

遍历循环链表并打印数据

需要一个额外的条件来判断是否已经回到起点。

// 打印循环链表所有节点的数据 (tail指向尾节点)
void printCircularLinkedList(CircularNode* tail) {
    if (tail == NULL) {
        printf("循环链表内容：NULL\n");
        return;
    }
    CircularNode* head = tail->next; // 头节点
    CircularNode* current = head;
    printf("循环链表内容：");
    do {
        printf("%d -> ", current->data);
        current = current->next;
    } while (current != head); // 遍历直到回到头节点
    printf("... (循环回到 %d)\n", head->data);
}

删除节点（已知尾节点和待删除值）

删除循环链表节点需要更细致的判断，特别是当只剩一个节点或删除头/尾节点时。

// 删除循环链表中指定值的节点 (tail指向尾节点)
CircularNode* deleteCircularNode(CircularNode* tail, int value) {
    if (tail == NULL) {
        printf("循环链表为空，无法删除。\n");
        return NULL;
    }

    CircularNode* head = tail->next; // 获取头节点

    // 如果只有一个节点且是待删除节点
    if (head == tail && head->data == value) {
        free(head);
        printf("成功删除唯一节点 %d。\n", value);
        return NULL; // 链表变空
    }

    // 删除头节点
    if (head->data == value) {
        tail->next = head->next; // 尾节点指向新的头节点
        free(head);
        printf("成功删除头节点 %d。\n", value);
        return tail; // 返回原来的尾节点
    }

    // 删除中间或尾部节点
    CircularNode* current = head;
    while (current->next != head && current->next->data != value) { // 遍历直到找到或遍历一圈
        current = current->next;
    }

    if (current->next->data == value) { // 找到了要删除的节点
        CircularNode* temp = current->next;
        current->next = temp->next;
        if (temp == tail) { // 如果删除的是尾节点，更新tail
            tail = current;
        }
        free(temp);
        printf("成功删除节点 %d。\n", value);
    } else {
        printf("未找到值为 %d 的节点进行删除。\n", value);
    }
    return tail;
}

释放循环链表内存

// 释放循环链表所有节点的内存 (tail指向尾节点)
void freeCircularLinkedList(CircularNode* tail) {
    if (tail == NULL) {
        printf("循环链表已空，无需释放。\n");
        return;
    }
    CircularNode* head = tail->next;
    CircularNode* current = head;
    do {
        CircularNode* temp = current;
        current = current->next;
        free(temp);
    } while (current != head); // 遍历直到回到头节点
    printf("循环链表内存已释放。\n");
}

Title:链表

Author:

Created:2025-05-30, 20:04:51

Updated:2025-05-30, 20:48:02

Full URL:http://example.com/2025/05/30/%E9%93%BE%E8%A1%A8/

License: "CC BY-NC-SA 4.0" Keep Link & Author if Distribute.