C语言——链表

大神文献：https://blog.csdn.net/weixin_73588765/article/details/128356985

目录

一、链表概念

1. 什么是链表？

1.1 链表的构成

2. 链表和数组的区别

数组的特点：

链表的特点：               

二者对比：

二、链表静态添加和遍历

三、统计链表节点个数、链表查询及修改节点

四、在指定节点插入新的节点

1.在指定节点后插入新的节点

2.在指定节点的前方插入新节点

1.第一个节点之前插入新的节点；

2.在中间的节点插入新的节点；

完整代码：

五、删除指定节点

1.删除第一个节点

2.删除中间的节点

完整代码：

六、动态创建节点 

头插法

尾插法

---

一、链表概念

1. 什么是链表？

链表是一种数据结构，是一种数据存放的思想；

链表是一种物理存储上非连续，数据元素的逻辑顺序通过链表中的指针链接次序，实现的一种线性存储结构。

1.1 链表的构成

构成：链表由一个个结点组成，每个结点包含两个部分：数据域 和 指针域。

• 数据域（data field）：每个结点中存储的数据。

• 指针域（pointer field）：每个结点中存储下一个结点的地址。

2. 链表和数组的区别

数组的特点：

• 数组中的每一个元素都属于同一数据类型的；
• 数组是一组有序数据的集合；
• 数组是在内存中开辟一段连续的地址空间用来存放一组数据，可以用数组名加下标来访问数组中的元素； 

链表的特点：               

• 动态地进行存储分配的一种结构；
• 链表中的各节点在内存中的地址都是不连续的；
• 链表是由一个个节点组成，像一条链子一样；
• 链表中的节点一般包括两个部分：（1）用户要用的数据（2）下一个节点的地址；          

二者对比：

一个数组只能存放同一种类型的数据，而链表中就可以存放不同的数据类型；
数组中的元素地址是连续的，想删除或添加一个新的元素，十分的麻烦不灵活，而且用数组存放数据是都要先定义好数组的大小(即元素的个数)，如果在定义数组时，定义小了，内存不够用，定义大了，显然会浪费内存；

链表就可以很好的解决这些问题，链表中每一项都是一个结构体，链表中各节点在内存中的地址可以是不连续的，所以你想删除或添加一个新的节点很简单和方便，直接把节点中存放的的地址拿去修改就ok了(具体怎么添加或删除放在后用代码详细讲)。因为链表是一种动态结构，所以链表在建立的时候并不用像数组一样需要提前定义大小和位置(具体怎么创建也放在后面用代码详细讲)。

二、链表静态添加和遍历

思路：

静态创建的链表节点，都是不同内存地址，是不连续的。

所以我们要在每个节点的指针域中，存储下一个节点的地址，如上图：

• 节点 1 的next（指针域），存储的是节点 2 的地址
• 节点 2 的next（指针域），存储的是节点 3 的地址
• 节点 3 的next（指针域），存储的是节点 4 的地址
• 节点 4 的next（指针域），存储的是节点 5 的地址

通过这样的操作，就可以把这 5 个节点连接在一起。

#include <stdio.h>struct Test
{int data;struct Test *next;
};// 打印链表（遍历链表）
void printfLink(struct Test *p) // 当前 p 存储的是 t1 的地址，也就是链表头
{while ( p != NULL ) // p 现是链表头节点，通过循环移动到下一个节点，直到 NULL {printf("%d ",p->data); // 输出当前节点的 data 值p = p->next; // 使 p 移动至下一个节点}putchar('\n');
}int main()
{// 创建节点struct Test t1 = {1, NULL}; // t1.data赋值为1，t1.next赋值为NULLstruct Test t2 = {2, NULL};struct Test t3 = {3, NULL};struct Test t4 = {4, NULL};struct Test t5 = {5, NULL};// 链接节点t1.next = &t2; // t1.next存储t2的地址，使t1.next指向t2这个结构体变量t2.next = &t3;t3.next = &t4;t4.next = &t5;// 打印链表printfLink(&t1); // 将 t1（链表头）的地址传递给printfLink函数的结构体指针变量 preturn 0;
}

三、统计链表节点个数、链表查询及修改节点

#include <stdio.h>struct Test
{int data;struct Test *next;
};// 打印链表
void printfLink(struct Test *p) // 当前 p 存储的是 t1 的地址，也就是链表头
{while ( p != NULL ) // p 现是链表头节点，通过循环移动到下一个节点，直到 NULL {printf("%d ",p->data); // 输出当前节点的 data 值p = p->next; // 使 p 移动至下一个节点}putchar('\n');
}// 统计链表个数
int statisticsNode(struct Test *head) // 当前 head 存储的是 t1 的地址，也就是链表头
{int cnt = 0; // 计数器，统计节点个数// 遍历链表，直到 head == NULLwhile ( head != NULL ){cnt++; // 记录每一个节点head = head->next; // 使 head 移动至下一个节点}return cnt; // 返回节点个数
}// 查询链表
int seekNode(struct Test *head, int data) // 当前 p 存储的是 t1 的地址，也就是链表头。data：我们需要查询的节点
{struct Test *p = head; // 备份头节点地址// 遍历链表，直到 p == NULLwhile ( p != NULL ){// 判断每个节点的数据域（p->data） 是否等于 我们需要查询的节点（data）if( p->data == data ){return 1; // 查询到，返回 1}p = p->next; // 使 p 移动至下一个节点}return -1;// 查不到，返回 -1
}// 修改指定节点
int modifyNode(struct Test *head, int data) // 当前 p 存储的是 t1 的地址，也就是链表头。data：我们需要修改的节点
{struct Test *p = head; // 备份链表头// 遍历链表while ( p != NULL ){// 判断每个节点的数据域（p->data） 是否等于 我们需要修改的节点（data）if( p->data == data ){// 找了，将这个节点的原数据域的数据，修改为100p->data = 100;return 1; // 返回 1，表示修改成功}p = p->next; // 使 p 移动至下一个节点}return -1; // 返回 -1，找不到这个节点
}int main()
{// 创建节点struct Test t1 = {1, NULL}; // t1.data赋值为1，t1.next赋值为NULLstruct Test t2 = {2, NULL};struct Test t3 = {3, NULL};struct Test t4 = {4, NULL};struct Test t5 = {5, NULL};// 链接节点t1.next = &t2; // t1.next存储t2的地址，使t1.next指向t2这个结构体变量t2.next = &t3;t3.next = &t4;t4.next = &t5;// 打印链表printfLink(&t1);// 统计链表个数int ret = statisticsNode(&t1);printf("链表个数：%d\n", ret);// 查询链表int seekNodeData = 3; // 需要查询的节点ret = seekNode(&t1, seekNodeData); // 将 t1 的地址和需要查询的节点，传递至 seekNode 函数中if( ret == 1 ) // 判断返回值是否为1，如 1 表示找到了，非 1 表示找不到{printf("需查询的值：%d，查询结果：%d\n", seekNodeData, ret);}else{printf("需查询的值：%d，查询结果：%d\n", seekNodeData, ret);}// 修改指定节点int modifyNodeData = 5; // 需要修改的节点printf("修改之前的链表：");printfLink(&t1);ret = modifyNode(&t1, modifyNodeData); // 将 t1 的地址和需要修改的节点，传递至 modifyNode 函数中printf("修改之后的链表：");printfLink(&t1);return 0;
}

四、在指定节点插入新的节点

插入一个新节点有两种方法：        

1.  在指定节点后插入新的节点
2.  在指定节点前插入新的节点

1.在指定节点后插入新的节点

如上图，在节点 2 的后方插入新的节点：

1.  通过循环，遍历到指定的节点
2. 让新节点的下一个节点，连接到节点 3
   new->next = p->next
3. 使指定节点的下一个节点，连接到新节点
   p->next = new;

#include <stdio.h>struct Test
{int data;struct Test *next;
};// 打印链表
void printfLink(struct Test *p) // 当前 p 存储的是 t1 的地址，也就是链表头
{while ( p != NULL ) // p 现是链表头节点，通过循环移动到下一个节点，直到 NULL {printf("%d ",p->data); // 输出当前节点的 data 值p = p->next; // 使 p 移动至下一个节点}putchar('\n');
}// 在指定节点后方插入新节点
void afterInsertionNode(struct Test **head, int appointNode, struct Test *new)
{// 备份链表头地址struct Test *p = *head;// 遍历链表while ( p != NULL ){// 判断当前节点是否等于目标节点if( p->data == appointNode ){new->next = p->next; // 让新节点的下一个节点存储，原节点的下一个节点的地址p->next = new; // 让当前节点指向新节点return; // 找到之后直接返回}p = p->next; // 让当前节点移动到下一个节点}printf("没有找到目标节点，插入失败！\n");
}int main()
{// 创建节点struct Test t1 = {1, NULL}; // t1.data赋值为1，t1.next赋值为NULLstruct Test t2 = {2, NULL};struct Test t3 = {3, NULL};struct Test t4 = {4, NULL};struct Test t5 = {5, NULL};// 创建链表头struct Test *head = NULL;// 定义新节点并赋初值struct Test new = {100,NULL};// 链接节点head = &t1; // 头节点head，存储结构体变量 t1 的地址t1.next = &t2; // t1.next存储t2的地址，使t1.next指向t2这个结构体变量t2.next = &t3;t3.next = &t4;t4.next = &t5;// 打印链表printf("输出插入之前的链表：\n");printfLink(head);// 在指定节点后方插入新节点afterInsertionNode(&head, 2,&new);printf("输出插入之后的链表：\n");printfLink(head);return 0;
}

2.在指定节点的前方插入新节点

有两种情况：

• 1.第一个节点之前插入新的节点；
• 2.在中间的节点插入新的节点；

1.第一个节点之前插入新的节点；

 

如上图，在指定节点的节点 1，之前插入的新节点：

1. 遍历，判断节点是否为指定节点
2. 新节点的下一个，指向节点1的地址
   new->next = p;
3. 因为此时新节点变成了头节点，所以此时将new的地址赋值给head
   head = new;

void forwardInsertionNode(struct Test **head, int appointNode, struct Test *new)
{struct Test *p = *head; // 备份链表头的地址// 判断第一个节点的data，是否等于目标节点if( p->data == appointNode ){// 将新节点的下一个节点指向，p的地址，此时new节点变成了链表头new->next = p;// 更新链表头的指向，使*head指向new的地址，让*head重新变成链表头*head = new;return;}
}

2.在中间的节点插入新的节点；

如上图，如果指定节点是5，之前插入新的节点：

思路：

按照之前的后面插入新节点的方法，当我们遍历到指定节点 5 的时候，如果将new的下一个节点，指向目标节点，是可以连接上的，但是new的节点如果访问到指定节点的上一个节点呢？这个时候很难找到目标节点的上一个节点的地址。
可以这么做，我们要在目标节点 5 之前插入一个新节点，比如说：现在 p 指向的是节点 4 ，节点 4 的下一个节点是目标节点 5 。那节点 4 ->next，不就是目标节点 5 吗？，节点 4 ->next->data，不就是节点 5 的data？然后将new->next指向目标节点 5 的地址，节点 4->next 指向new的地址，不就连上了。

    // 判断当前节点的下一个节点，是否为NULLwhile ( p->next != NULL ){// 判断当前节点的下一个节点的data，是否等于目标节点if( p->next->data == appointNode ){// 将new的下一个节点，指向原当前节点的下一个节点new->next = p->next;// 将当前节点的下一个节点指向newp->next = new;return;}p = p->next; // 偏移到下一个节点}

完整代码：

#include <stdio.h>struct Test
{int data;struct Test *next;
};// 打印链表
void printfLink(struct Test *p) // 当前 p 存储的是 t1 的地址，也就是链表头
{while ( p != NULL ) // p 现是链表头节点，通过循环移动到下一个节点，直到 NULL {printf("%d ",p->data); // 输出当前节点的 data 值p = p->next; // 使 p 移动至下一个节点}putchar('\n');
}// 在指定节点前方插入新节点
void forwardInsertionNode(struct Test **head, int appointNode, struct Test *new)
{struct Test *p = *head; // 备份链表的地址，// *head是一个二级指针，保存的是main函数t1的地址，是链表的头地址// 除非链表头发生改变，否则不要更改链表头的地址// 判断目标节点是否为链表的第一个节点if( p->data == appointNode ){new->next = p; // 将新节点的下一个节点指向，p的地址，此时new节点变成了链表头*head = new; // 更新链表头的指向，使*head指向new的地址，让*head重新变成链表头return; }// 判断当前节点的下一个节点，是否为NULLwhile ( p->next != NULL ){// 判断当前节点的下一个节点的data，是否等于目标节点if( p->next->data == appointNode ){// 将new的下一个节点，指向原当前节点的下一个节点new->next = p->next;// 将当前节点的下一个节点指向newp->next = new;return;}p = p->next; // 偏移到下一个节点}
}int main()
{// 创建节点struct Test t1 = {1, NULL}; // t1.data赋值为1，t1.next赋值为NULLstruct Test t2 = {2, NULL};struct Test t3 = {3, NULL};struct Test t4 = {4, NULL};struct Test t5 = {5, NULL};// 创建链表头struct Test *head = NULL;// 定义新节点并赋初值struct Test new = {100,NULL};// 链接节点head = &t1; // 头节点head，存储结构体变量 t1 的地址t1.next = &t2; // t1.next存储t2的地址，使t1.next指向t2这个结构体变量t2.next = &t3;t3.next = &t4;t4.next = &t5;// 打印链表printf("输出插入之前的链表：\n");printfLink(head);forwardInsertionNode(&head, 5,&new);printf("输出插入之后的链表：\n");printfLink(head);return 0;
}

五、删除指定节点

有两种情况：

1. 删除第一个节点
2. 删除中间的节点

1.删除第一个节点

思路：

head指向的是第一个节点，如果我需要删除第一个节点，需要free()释放内存，此时应当将head指向第二个节点。

    struct Test *p = *head; // 备份链表头的地址// 判断链表第一个节点的data，是否与目标节点相等if( p->data == appointNode ){// 将链表头指向第二个节点的地址*head = p->next;return;}

2.删除中间的节点

思路：

如果我们删除的是节点 3，那么节点 2 应该绕过节点 3，使节点 2 连接节点 4

    // 判断当前节点的下一个节点是否为NULLwhile ( p->next != NULL ){// 判断当前节点的下一个节点的data，是否等于目标节点if( p->next->data == appointNode ){// 当前节点的下一个，指向当前节点的下一个节点的下一个节点p->next = p->next->next;return;}p = p->next; // 将当前节点，移动到下一个节点}

完整代码：

#include <stdio.h>struct Test
{int data;struct Test *next;
};// 打印链表
void printfLink(struct Test *p) // 当前 p 存储的是 t1 的地址，也就是链表头
{while ( p != NULL ) // p 现是链表头节点，通过循环移动到下一个节点，直到 NULL {printf("%d ",p->data); // 输出当前节点的 data 值p = p->next; // 使 p 移动至下一个节点}putchar('\n');
}// 删除节点
void delectNode(struct Test **head, int appointNode)
{struct Test *p = *head; // 备份链表头的地址// 判断链表第一个节点的data，是否与目标节点相等if( p->data == appointNode ){// 将链表头指向第二个节点的地址*head = p->next;return;}// 判断当前节点的下一个节点是否为NULLwhile ( p->next != NULL ){// 判断当前节点的下一个节点的data，是否等于目标节点if( p->next->data == appointNode ){// 当前节点的下一个，指向当前节点的下一个节点的下一个节点p->next = p->next->next;return;}p = p->next; // 将当前节点，移动到下一个节点}
}int main()
{// 创建节点struct Test t1 = {1, NULL}; // t1.data赋值为1，t1.next赋值为NULLstruct Test t2 = {2, NULL};struct Test t3 = {3, NULL};struct Test t4 = {4, NULL};struct Test t5 = {5, NULL};// 创建链表头struct Test *head = NULL;// 链接节点head = &t1; // 头节点head，存储结构体变量 t1 的地址t1.next = &t2; // t1.next存储t2的地址，使t1.next指向t2这个结构体变量t2.next = &t3;t3.next = &t4;t4.next = &t5;// 打印链表printf("输出删除之前的链表：\n");printfLink(head);delectNode(&head, 4);printf("输出删除之后的链表：\n");printfLink(head);return 0;
}

六、动态创建节点 

头插法

如果链条为空，创建的第一个节点为链表头，然后每一次创建的新节点插在之前的链表头之前，再让新节点做为新的链表头；

#include <stdio.h>
#include <stdlib.h>struct Test 
{int data;struct Test *next;
};// 头插法
struct Test* insertionHead(struct Test *head, struct Test *new)
{// 如果head（头节点）是NULLif( head == NULL ){// 让head指向newhead = new;}else{// 如果head（头节点）不是NULL，那么新节点指向head，此时new为新的链表头new->next = head;// 让head指向new，让head重新成为链表头head = new;}return head; // 返回链表头的地址
}// 动态创建链表节点
void createNode(struct Test **head)
{struct Test *new = NULL;while(1){// 开辟内存空间new = (struct Test*)malloc( sizeof(struct Test) );// 判断是否开辟成功if( new == NULL ){printf("malloc error\n");exit(-1);}// 将new的下一个节点指向NULLnew->next = NULL;printf("为新节点的数据域赋值，如果输入0,表示退出\n");scanf("%d", &(new->data));// 判断输入的是否为 0if( new->data == 0 ){printf("输入0,quit\n");free(new); // 释放指针new = NULL; // 避免悬空指针return; }// 重新获取链表头的地址*head = insertionHead(*head,new);}
}// 打印链表
void printfLink(struct Test *head)
{struct Test *p = head;while( p != NULL ){printf("%d ", p->data);p = p->next;}putchar('\n');
}int main()
{struct Test *head = NULL;createNode(&head);printfLink(head);return 0;
}

尾插法

如果链表为空，创建的第一个节点做为链表头，然后每一次创建的新节点插在链表最后一个节点的指针域(next)中；

#include <stdio.h>
#include <stdlib.h>// 定义链表节点结构体
struct Test
{int data;           // 数据域struct Test *next;  // 指针域，指向下一个节点
};// 在链表尾部插入新节点
struct Test* insertTail(struct Test *head, struct Test *new)
{struct Test *p = head;if (head == NULL)  // 如果链表为空，新节点即为头节点{head = new;}else{// 遍历链表，找到最后一个节点while (p->next != NULL){p = p->next;}// 将新节点插入到链表尾部p->next = new;}return head;  // 返回链表头节点
}// 创建链表节点
void createNode(struct Test **head)
{struct Test *new = NULL;while (1){// 开辟内存空间，创建一个新节点new = (struct Test*)malloc(sizeof(struct Test));if (new == NULL)  // 检查内存分配是否成功{printf("malloc error\n");exit(-1);  // 内存分配失败，退出程序}new->next = NULL;  // 初始化新节点的指针域为NULL// 为新节点的数据域赋值printf("为新节点的数据域赋值，输入0,退出\n");scanf("%d", &(new->data));if (new->data == 0)  // 如果输入0，则退出循环{free(new);  // 释放内存new = NULL;  // 避免指针悬空return;}// 将新节点插入链表尾部*head = insertTail(*head, new);}
}// 打印链表
void printfLink(struct Test *head)
{while (head != NULL){printf("%d ", head->data);  // 打印当前节点的数据head = head->next;  // 移动到下一个节点}putchar('\n');  // 打印换行符
}int main()
{struct Test *head = NULL;  // 初始化链表头节点为NULLcreateNode(&head);  // 创建链表printfLink(head);   // 打印链表return 0;
}