上一篇	下一篇
在 C 语言结构体中再定义一个和自己一样的结构体

---

---

单链表（Singly Linked List）

1）什么是单链表？

单链表是一种线性动态数据结构，由一系列节点（Node） 组成。每个节点包含：

• 数据域（data）：存储实际数据
• 指针域（next）：指向下一个节点的地址

最后一个节点的 next 为 NULL，表示链表结束。

优点：动态大小、插入/删除高效（O(1) 若已知位置）
缺点：不能随机访问（必须从头遍历）、额外内存开销（指针）

2）核心结构定义

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

// 定义链表节点结构
struct ListNode {
    int data;                // 数据域（这里以 int 为例）
    struct ListNode* next;   // 指针域，指向下一个节点
};

// 通常用 typedef 简化类型名
typedef struct ListNode ListNode;

也可以写成：

typedef struct ListNode {
    int data;
    struct ListNode* next;
} ListNode;

3）关键操作及代码实现

3.1）创建新节点（辅助函数）

/* 假设前面已经定义过ListNode这个结构体类型了 */

ListNode* createNode(int value) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    if (!newNode) {
        fprintf(stderr, "内存分配失败！\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

用上述函数创建头节点（初始化）：

ListNode* HeadNode = createNode(0);

/* 如果不用函数创建的话，用如下代码 */
ListNode* HeadNode = (ListNode*)malloc(sizeof(ListNode));
HeadNode->data = 0;
HeadNode->next = NULL;

3.2）头插法（在链表头部插入）

头插法是从头插？还是每次都插在头节点的后一个？答案取决于你是否用了哨兵头节点：

链表类型	头插法实际插入位置	是否改变head指针
无哨兵（常见 C 实现）	成为新的第一个节点（即新 head）	✅ 是，head 要更新
有哨兵（dummy head）	插在哨兵节点的 next 位置（即第一个数据位置）	❌ 否，head 固定不变

哨兵节点 是一个不存储有效数据的虚拟节点，通常作为链表的固定头节点。它的作用是简化边界操作：因为链表永远非空（至少有哨兵），插入、删除等操作无需特殊处理空链表或头节点，代码更简洁统一。真实数据从哨兵的 next 开始。

注意：

① 头节点和哨兵节点不是一个概念， 链表的第一个节点都可以称为头节点，强调的是位置；哨兵节点不局限于位置，是强调功能上的 “哨兵” 作用；只是通常会将两者结合成哨兵头节点，即固定为头节点，且不存储有效数据，专用于简化边界操作；并且开发人员常常简称为头节点或哨兵节点。

② 在这个哨兵头节点之后的第一个具有有效数据的节点，通常被称为 “首元节点”。

① 无哨兵节点的普通单链表

无哨兵节点的话，那么头插法就是在链表的最开头处插入新节点，代码会将这个新插入的节点的 next 指向原来的头节点。

ListNode* insertAtHead(ListNode* head, int value) {
    ListNode* newNode = createNode(value);
    newNode->next = head;
    return newNode;  	// 新节点成为新的头
}

// 使用方式, 更新head: 
head = insertAtHead(head, 10);

注意：此函数返回新的头指针，调用时需更新 head。

② 有哨兵节点的单链表

/* 创建哨兵节点 */
ListNode* createSentinel() {
    ListNode* sentinel = (ListNode*)malloc(sizeof(ListNode));
    if (!sentinel) {
        fprintf(stderr, "内存分配失败！\n");
        exit(EXIT_FAILURE);
    }
    sentinel->data = 0;      // 值无意义，可设为任意值
    sentinel->next = NULL;   // 初始时链表为空
    return sentinel;         // 返回哨兵指针（即链表头）
}
ListNode* head = createSentinel();  // head 指向哨兵


/* 在哨兵节点后面插入新节点 */
void insertAtHeadWithSentinel(ListNode* head, int value) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->data = value;
    newNode->next = head->next;  // 新节点指向原第一个数据节点
    head->next = newNode;        // 哨兵的 next 指向新节点
}

3.3）尾插法（在链表尾部插入）

从链表头部开始遍历，找到最后一个节点（即 next 为 NULL 的节点），将新节点链接到其后，作为新的尾节点；

若链表为空，则新节点直接作为头节点。

/**
 * @brief:        insertAtTail（在单链表尾部插入新节点）
 * @param[in]:    head - 指向链表头节点的指针（可为 NULL，表示空链表）
 * 				  value - 要插入的新节点的数据值
 * @param[out]:   无（函数通过返回值传递新链表的头指针）
 * @return:       返回更新后的链表头指针（若原链表为空，则返回新节点；否则返回原 head）
 * @note:         本函数假设 createNode() 已正确实现并能分配内存；不修改原链表结构中的数据，仅追加节点。
 */
ListNode* insertAtTail(ListNode* head, int value) 
{
    // 创建包含指定值的新节点
    ListNode* newNode = createNode(value); 
    
    if (head == NULL) {
        return newNode;  // 空链表，新节点即为头节点，直接返回
    }

    /* 先获取尾节点 */
    ListNode* current = head;
    while (current->next != NULL) {  // 遍历至链表最后一个节点
        current = current->next;
    }
    
    /* 将新节点链接到尾部 */
    current->next = newNode;
    newNode->next = NULL;
    return head;  // 头节点未改变，返回原 head
}

3.4）按值查找节点

ListNode* find(ListNode* head, int target) {
    ListNode* current = head;
    while (current != NULL) {
        if (current->data == target) {
            return current;  // 找到，返回指针
        }
        current = current->next;
    }
    return NULL;  // 未找到
}

3.5）按值删除第一个匹配的节点

首先判断链表是否为空；若头节点即为目标，则更新头指针并释放原头；否则从头遍历，按值找到目标节点的前一个节点，将其 next 指向目标节点的下一个节点，并释放目标节点内存。若未找到，则链表不变。

/**
 * @brief:        deleteNode —— 删除单链表中第一个值等于 target 的节点
 * @param[in]:    head - 指向链表头节点的指针（可为 NULL）
 * 				  target - 要删除的目标数据值
 * @param[out]:   无（通过返回值返回更新后的头指针）
 * @return:       返回删除操作后链表的头指针（若删除的是原头节点，则返回新的头；否则返回原 head）
 * @note:         仅删除第一个匹配的节点；若未找到 target，链表保持不变；假定节点内存由 malloc 分配，使用 free 释放。
 */
ListNode* deleteNode(ListNode* head, int target) {
    if (head == NULL) return NULL;  // 空链表，直接返回

    // 特殊情况：要删除的是头节点
    if (head->data == target) {
        ListNode* temp = head;
        head = head->next;     // 更新头指针
        free(temp);            // 释放原头节点内存
        return head;           // 返回新的头节点
    }

    // 查找目标节点的前一个节点（prev 指向待删节点的前驱）
    ListNode* prev = head;
    while (prev->next != NULL && prev->next->data != target) {
        prev = prev->next;
    }

    // 如果找到了目标节点（即 prev->next 不为 NULL）
    if (prev->next != NULL) {
        ListNode* toDelete = prev->next;      // 待删除节点
        prev->next = toDelete->next;          // 跳过待删节点
        free(toDelete);                       // 释放内存
    }

    return head;  // 头节点未变（除非前面已处理头节点情况）
}

⚠️ 注意：删除后要 free 内存，并处理头节点被删的情况。

3.6）按位置删除指定位置的节点

按位置删除单链表中第 pos 个节点（从0开始计数）：先校验位置是否合法；若删除头节点（pos == 0），更新头指针并释放原头；否则遍历到第 pos-1 个节点，将其 next 指向待删节点的下一个节点，并释放目标节点。位置无效时返回原链表。

/**
 * @brief:        deleteNode —— 删除单链表中指定位置的节点（位置从0开始）
 * @param[in]:    head - 链表头指针（可为 NULL）
 *                pos  - 要删除节点的位置（0 表示头节点）
 * @return:       删除后链表的头指针；若 pos 无效或链表为空，返回原 head
 * @note:         假设节点由 malloc 分配，使用 free 释放内存。
 */
ListNode* deleteNode(ListNode* head, int pos) {
    if (head == NULL || pos < 0) {
        return head;  // 空链表或位置非法，直接返回
    }

    // 删除头节点（若pos == 0）
    if (pos == 0) {
        ListNode* temp = head;
        head = head->next;
        free(temp);
        return head;
    }

    // 遍历到第 pos-1 个节点（即待删节点的前驱）
    ListNode* prev = head;
    for (int i = 0; i < pos - 1 && prev != NULL; ++i) {
        prev = prev->next;
    }

    // 检查位置是否越界（prev 为 NULL 或 prev->next 为 NULL）
    if (prev == NULL || prev->next == NULL) {
        return head;  // 位置超出链表长度，不删除
    }

    // 执行删除
    ListNode* toDelete = prev->next;
    prev->next = toDelete->next;
    free(toDelete);

    return head;
}

3.7）遍历并打印链表

/**
 * @brief:        printList —— 遍历并打印单向链表的所有节点值，并返回链表长度
 * @param[in]:    head - 指向链表头节点的指针（可为 NULL）
 * @return:       链表中节点的个数（若链表为空，返回 0）
 * @note:         打印格式为 "链表: val1 -> val2 -> ... -> NULL"；
 *                即使使用哨兵节点，也会将其 data 打印（调用者需确保语义合理）。
 */
int printList(ListNode* head) {
    ListNode* current = head;          // 从头节点开始遍历
    int length = 0;                    // 初始化长度计数器

    if (current == NULL) {
        printf("链表为空。\n");
        return 0;                      // 空链表，长度为 0
    }

    printf("链表: ");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
        length++;                      // 每访问一个节点，长度加 1
    }
    printf("NULL\n");

    return length;                     // 返回链表总长度
}

3.8）释放整个链表（避免内存泄漏）

void freeList(ListNode* head) {
	// ListNode* current = head->next;		// 如果想保留头节点，那么就用此行代码
    ListNode* current = head;		// 删除所有节点，包括头节点
    while (current != NULL) {
        ListNode* next = current->next;
        free(current);
        current = next;
    }
}

4）完整示例程序

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

typedef struct ListNode {
    int data;
    struct ListNode* next;
} ListNode;

// 创建新节点
ListNode* createNode(int value) {
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    if (!node) {
        fprintf(stderr, "内存分配失败！\n");
        exit(EXIT_FAILURE);
    }
    node->data = value;
    node->next = NULL;
    return node;
}

// 头插
ListNode* insertAtHead(ListNode* head, int value) {
    ListNode* newNode = createNode(value);
    newNode->next = head;
    return newNode;
}

// 尾插
ListNode* insertAtTail(ListNode* head, int value) {
    if (head == NULL) return createNode(value);
    ListNode* cur = head;
    while (cur->next) cur = cur->next;
    cur->next = createNode(value);
    return head;
}

// 查找
ListNode* find(ListNode* head, int target) {
    while (head) {
        if (head->data == target) return head;
        head = head->next;
    }
    return NULL;
}

// 删除第一个匹配值
ListNode* deleteNode(ListNode* head, int target) {
    if (!head) return NULL;
    if (head->data == target) {
        ListNode* tmp = head;
        head = head->next;
        free(tmp);
        return head;
    }

    ListNode* prev = head;
    while (prev->next && prev->next->data != target) {
        prev = prev->next;
    }

    if (prev->next) {
        ListNode* tmp = prev->next;
        prev->next = tmp->next;
        free(tmp);
    }
    return head;
}

// 打印
void printList(ListNode* head) {
    if (!head) {
        printf("链表为空。\n");
        return;
    }
    printf("链表: ");
    while (head) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

// 释放
void freeList(ListNode* head) {
    while (head) {
        ListNode* next = head->next;
        free(head);
        head = next;
    }
}

// 主函数演示
int main() {
    ListNode* head = NULL;

    // 尾插：1 -> 2 -> 3
    head = insertAtTail(head, 1);
    head = insertAtTail(head, 2);
    head = insertAtTail(head, 3);
    printList(head);  // 输出: 1 -> 2 -> 3 -> NULL

    // 头插：0 -> 1 -> 2 -> 3
    head = insertAtHead(head, 0);
    printList(head);  // 输出: 0 -> 1 -> 2 -> 3 -> NULL

    // 查找
    if (find(head, 2)) {
        printf("找到了值 2\n");
    }

    // 删除值为 1 的节点
    head = deleteNode(head, 1);
    printList(head);  // 输出: 0 -> 2 -> 3 -> NULL

    // 删除头节点（0）
    head = deleteNode(head, 0);
    printList(head);  // 输出: 2 -> 3 -> NULL

    // 释放内存
    freeList(head);
    head = NULL;

    printf("链表已释放。\n");
    return 0;
}

运行结果如下：

链表: 1 -> 2 -> 3 -> NULL
链表: 0 -> 1 -> 2 -> 3 -> NULL
找到了值 2
链表: 0 -> 2 -> 3 -> NULL
链表: 2 -> 3 -> NULL
链表已释放。

5）注意事项

1. 内存管理：每次 malloc 都要对应 free，避免内存泄漏。
2. 空指针检查：操作前判断 head == NULL。
3. 头指针更新：插入/删除头节点时，必须更新 head。
4. 不要访问已释放内存：free 后最好将指针置为 NULL。
5. 效率：尾插、查找、删除都是 O(n)，头插/删是 O(1)。

---