《数据结构笔记三》：单链表（创建、插入、遍历、删除、释放内存等核心操作）

 不带头节点的单链表：（不带表头）

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//定义一个链表节点结构体
typedef struct Node
{
    /* data */
    int   data;           //表示节点数据域
    struct Node *next;    //表示节点指针域
}Node;

//链表类型 （头指针）
typedef Node  *LinkedList;

void initList(LinkedList  *list)
{
     *list = NULL;
}

//插入新节点  头插法
void insertAtHead(LinkedList *list  int value)
{
    Node *newnode  = (Node*) malloc (sizeof(Node)); //为新节点开辟堆内存空间
    if(!newnode)//判断是否存在新节点
    {
        perror("内存分配失败！");
        exit(EXIT_FAILURE);
    }
    newNode -> data = value;
    newNode -> next = *list;    //新节点指向原头节点
    *list = Newnode;           //头指针指向新节点 
}

//遍历链表
void traverseList(LinkedList list)
{
    Node *current = list;
    printf("链表元素：")；
    while (current  !=  NULL)
    {
        /* code */
        printf("%d ->",current -> data);
        current = currenr -> next;
    }
    printf("NULL\n");
}

//删除节点
//删除第一个值为vulue的节点
void deleteNode(LinkedList *list , int value)
{
    if ( *list= NULL)  //判断是否为空链表
    {
        /* code */
        return ;
    }
    Node *current  = *list;
    Node *prev =  NULL;
    //查找待删除节点
    while (current != NULL && current->data != value)
    {
        /* code */
        prev = current;
        current = current->next;
    }
    if(current = NULL)  return; //空值表示未查找到
    if (prev = NULL)
    {
        *list = current->next;
    }else{
        prev->next = current->next;
    }
    free(current); //释放节点内存
}

//释放内存
void freeList(Linkedlist *list)
{
    Node *current = *list;
    while (current != NULL)
    {
        Node *temp = current;
        current = current->next;
        free(temp);    
    }
     *list = NULL; // 头指针置空
}

int main() {
    // 测试不带表头链表
    LinkedList list1;
    initList(&list1);
    insertAtHead(&list1, 10);
    insertAtHead(&list1, 20);
    traverseList(list1); // 输出: 20 -> 10 -> NULL
    deleteNode(&list1, 10);
    traverseList(list1); // 输出: 20 -> NULL
    freeList(&list1);

    return 0;
}

 带头节点的单链表：（带表头）

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

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

// 链表类型（固定头节点）
typedef struct {
    Node *head;  // 头节点（不存储数据 NULL）
} LinkedList;

//创建链表，初始化
void initList(LinkedList *list) {
    list->head = (Node *)malloc(sizeof(Node)); // 分配头节点
    if (!list->head) {
        perror("内存分配失败");
        exit(EXIT_FAILURE);
    }
    list->head->next = NULL; // 头节点的next初始化为NULL
}

//插入节点（头插法）
void insertAtHead(LinkedList *list, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (!newNode) {
        perror("内存分配失败");
        exit(EXIT_FAILURE);
    }
    newNode->data = value;
    newNode->next = list->head->next; // 新节点指向原第一个节点
    list->head->next = newNode;       // 头节点指向新节点
}

//遍历节点
void traverseList(LinkedList *list) {
    Node *current = list->head->next; // 跳过头节点
    printf("链表元素: ");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

//删除节点
void deleteNode(LinkedList *list, int value) {
    Node *prev = list->head;
    Node *current = prev->next;

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

    if (current != NULL) {
        prev->next = current->next;
        free(current);
    }
}

//释放内存
void freeList(LinkedList *list) {
    Node *current = list->head->next;
    while (current != NULL) {
        Node *temp = current;
        current = current->next;
        free(temp);
    }
    free(list->head);     // 释放头节点
    list->head = NULL;
}

int main()
{
    // 测试带表头链表
    LinkedList list2;
    initList(&list2);
    insertAtHead(&list2, 100);
    insertAtHead(&list2, 200);
    traverseList(&list2); // 输出: 200 -> 100 -> NULL
    deleteNode(&list2, 200);
    traverseList(&list2); // 输出: 100 -> NULL
    freeList(&list2);

    return 0;

}

插入操作，除了头插法，还有：中间插入、任意一位置插入（索引插入），尾插法。 

1. 插入操作的分类

2. 带表头 vs 不带表头的差异

3. 边界条件处理

• 空链表插入：

  • 不带表头：头指针为NULL时，尾插法直接赋值。

  • 带表头：头节点的 next 为NULL时，尾插法插入到 head->next。

• 越界插入：

  • 按索引插入时，若 pos 超过链表长度，需提示错误并释放未使用的节点内存。

• 重复值处理：

  • 中间插入时，若有多个相同值的节点，默认操作第一个匹配的节点。

4. 内存管理

• 内存分配失败：统一检查 malloc 返回值，避免程序崩溃。

• 未使用的节点：在插入失败时（如越界），需释放已分配的节点内存。

总结

• 插入灵活性：单链表的插入操作灵活，但需注意指针修改顺序（先连接新节点，再断开旧链接）。

• 代码鲁棒性：始终处理边界条件（如空链表、越界位置）和内存分配失败。

• 性能权衡：头插法最快（O(1)），尾插法和中间插入需要遍历（O(n)）。

深度解析

1. 带表头 vs 不带表头

2. 关键操作分析

• 插入操作：

  • 不带表头链表插入头节点时，必须修改外部头指针（需传递二级指针）。

  • 带表头链表插入头节点时，只需修改头节点的 next 指针，外部头指针不变。

• 删除操作：

  • 不带表头链表删除头节点时，需更新头指针，否则会访问已释放的内存。

  • 带表头链表删除头节点时，只需处理头节点的 next 指针，无需关心外部指针。

• 内存管理：

  • 释放链表时，带表头链表需额外释放头节点。

  • 不带表头链表需确保头指针被正确置空，避免野指针。

    总结

  • 不带表头链表：适合简单场景，但需处理头指针的特殊情况。

  • 带表头链表：代码更简洁，适合需要频繁操作头节点的场景。

  • 通过对比实现，可以深入理解链表的核心逻辑和指针操作的精髓。

  • 共同注意点：确保内存正确释放，避免内存泄漏；操作指针时注意边界条件。