C语言——链表
在C语言中，链表是一种常见的数据结构，用于存储一系列的元素，但不同于数组，链表中的元素在内存中不是连续存储的，而是通过指针将这些元素链接起来。链表具有动态大小的特点，可以方便地进行插入和删除操作。
链表的基本结构通常包括节点（Node）和头指针（Head Pointer）。每个节点包含两部分：一部分是存储数据的域（Data Field），另一部分是存储指向下一个节点的指针（Pointer Field）。
链表具有几个显著的特点：
- 动态大小：链表可以根据需要动态地增加或减少节点，这使得链表在处理未知大小的数据集时非常有用。
- 高效的插入和删除：在链表中插入或删除节点通常只需要改变相关节点的指针，而不需要移动大量的数据。
- 内存使用：由于链表中的节点是单独分配的，因此可能存在内存碎片的问题。同时，每个节点都需要额外的指针存储空间。
链表类型
在C语言中，链表可以分为单向链表（Singly Linked List）和双向链表（Doubly Linked List）等类型。
- 单向链表：每个节点只包含一个指向下一个节点的指针。
- 双向链表：每个节点包含两个指针，一个指向下一个节点，另一个指向前一个节点。这使得在双向链表中向任意方向遍历都变得容易。
链表操作
下面是一个简单的单向链表（Singly Linked List）的实现示例：
1. 定义节点结构
#include <stdio.h>
#include <stdlib.h>
// 定义节点结构
struct Node {
int data;
struct Node* next;
};2. 创建新节点
使用malloc或calloc等内存分配函数为节点分配内存，并初始化节点的数据域和指针域。
// 创建新节点并返回其指针
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (!newNode) {
printf("内存分配失败\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}3. 插入节点
在链表头部插入节点
创建一个新节点，将其指针域指向当前的头节点，然后更新头指针指向新节点。
// 在链表头部插入新节点
void insertAtHead(struct Node** head, int data) {
struct Node* newNode = createNode(data);
newNode->next = *head;
*head = newNode;
}在链表尾部插入节点
遍历链表找到最后一个节点，将其指针域指向新节点。如果链表为空，则新节点成为头节点。
// 在链表尾部插入新节点
void insertAtTail(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}在指定节点后面插入节点
在指定节点后面插入节点时，我们使用当前节点的数据域作为判断条件，插入新的节点时，新的节点需要指向指定节点原本指向的那个节点。而新的节点是插在指定节点的后面，指定节点的指向需要更改为新的节点，这样链表就完整连接起来了。
void insertFromBehind(struct Test *head,int data,struct Test *new)
{
struct Test *p = head;
while(1){
if(p != NULL){
if(p->data == data){
new->next = p->next;
p->next = new;
}
p = p->next;
}else{
break;
}
}
}
在指定节点前面插入节点
在指定节点前面插入节点时，我们要拿当前节点的下一个节点的数据作为判断条件，这样才能保证插入新的节点时，新的节点前面的那个节点可以指向新的节点。而新的节点是插在指定节点的前面，新的节点可以直接指向指定节点，这样链表就前后连接起来了。
struct Test* insertFromForward(struct Test *head,int data,struct Test *new)
{
struct Test *p = head;
if(data == p->data){
new->next = p;
return new;
}
while(p->next != NULL){
if(p->next->data == data){
new->next = p->next;
p->next = new;
return head;
}else{
p = p->next;
}
}
return 0;
}
4. 删除节点
删除头部节点
更新头指针指向当前头节点的下一个节点，并释放头节点的内存。
// 删除链表头部节点
struct Test* delteNode(struct Test* head,int data)
{
struct Test *p = head;
if(p->data == data){
head = head->next;
// free(p);
return head;
}
}删除指定值的节点
遍历链表找到要删除的节点的前一个节点，然后更新其指针域跳过要删除的节点，并释放该节点的内存。
// 删除链表中第一个值为key的节点
void deleteNode(struct Node** head, int key) {
struct Node* temp = *head;
struct Node* prev = NULL;
// 如果头节点就是要删除的节点
if (temp != NULL && temp->data == key) {
*head = temp->next;
free(temp);
return;
}
// 查找要删除的节点
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
// 如果没有找到
if (temp == NULL) return;
// 解除节点并释放内存
prev->next = temp->next;
free(temp);
}struct Test* delteNode(struct Test* head,int data)
{
struct Test *p = head;
//删除头节点
if(p->data == data){
head = head->next;
// free(p);
return head;
}
//查找要删除的节点
while(p->next != NULL){
//找到后进行删除
if(p->next->data == data){
//struct Test *temp = p;
p->next = p->next->next;
//free(temp);释放配p以避免内存泄漏
return head;
}
//没找到继续往下找
p = p->next;
}//遍历完整个链表找不到后返回头节点
return head;
}
5. 遍历链表
从头节点开始，使用指针域依次访问每个节点，直到达到链表的末尾（即指针域为NULL的节点）。
// 打印链表中的所有元素
void printLink(struct Test *head)
{
while(1){
if(head != NULL){
printf("%d ",head->data);
head = head->next;
}else{
putchar('\n');
break;
}
}
}
6. 释放链表内存
遍历链表，逐个释放每个节点的内存。这是防止内存泄漏的重要步骤。
// 释放链表的所有节点
void freeList(struct Node* head) {
struct Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
}