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

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

#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 -> NULLdeleteNode(&list1, 10);traverseList(list1); // 输出: 20 -> NULLfreeList(&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 -> NULLdeleteNode(&list2, 200);traverseList(&list2); // 输出: 100 -> NULLfreeList(&list2);return 0;}

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

1. 插入操作的分类

插入方式	适用场景	时间复杂度
头插法	快速在链表头部插入	O(1)
尾插法	在链表尾部追加数据	O(n)
中间插入	在指定值或位置后插入	O(n)（查找时间）
按索引插入	类似数组操作，按位置插入	O(n)

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

操作	不带表头链表	带表头链表
头插法	需直接修改外部头指针	操作头节点的 next，无需修改外部指针
尾插法	需要处理空链表（头指针为NULL）	直接从 head->next 开始遍历
按索引插入	插入位置0需特殊处理头指针	统一从头节点开始计算位置
错误处理	需检查头指针是否为NULL	头节点始终存在，无需额外判空

3. 边界条件处理

• 空链表插入：

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

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

• 越界插入：

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

• 重复值处理：

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

4. 内存管理

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

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

总结

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

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

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

深度解析

1. 带表头 vs 不带表头

特性	不带表头链表	带表头链表
头指针	指向第一个数据节点	指向头节点（不存储数据）
插入/删除头节点	需要特殊处理头指针	统一操作，无需修改头指针
代码简洁性	需要较多条件判断	代码更统一，减少边界条件
内存占用	节省一个头节点内存	多一个头节点的内存占用
适用场景	简单场景或内存敏感环境	需要频繁操作头节点的情况

2. 关键操作分析

• 插入操作：

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

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

• 删除操作：

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

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

• 内存管理：

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

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

    总结

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

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

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

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