前言
此篇记录一下本人对链表的理解，重点讲解链表的插入与删除算法，相信大家在学习数据结构的时候，第一篇就是链表。简直是给了我一个下马威。我对应它放弃了多次，早在1年前我就接触了链表，emmm，放弃。始终不甘心，然后等到高考暑假后再次鼓起勇气认识它，好吧，又被它打跑了。终于在前几天重新再来学习链表，功夫不负有心人，彻彻底底的搞懂了链表。
基本概念
链表由n个结点链组成，第一个结点的存储位置叫做头指针，最后一个结点的指针为“空”(NULL)
结点：包括数据域和指针域
头指针：指向链表中第一个结点的地址
头结点：在单链表的第一个结点前附设的一个结点
头指针是链表的必要元素，头结点是为了操作的统一和方便而设定的，其数据域一般无意义(可用来保存链表的长度)，头结点可有可无。
单链表
结构图
再次强调，请理解头结点和头指针，头指针不是链表的第一个结点，而是指向链表的第一个结点的地址！！
首先定义链表的结点
// 定义链表的结点
typedef struct node{
int id; //数据域，这里为了方便示例全部采用id值
struct node * next; //指针域，指向下一个结点的地址
}Node;然后定义链表的头结点与头指针
// 头结点
// 在定义链表时，习惯性的会定义头结点，以便统一链表结点的插入和删除操作
typedef struct LinkList{
Node * next; //头指针（如果链表有头结点，next就指向头结点，没有就指向第一个结点）
int length;
}LinkList;上面这段代码，你可能会好奇怎么使用，或者说为什么要这样定义，而不是只要有链表的结点不就完了吗，还要这段代码干嘛，别急后面会用到。
单链表插入
插入分为两种情况，第一种插入到第一个位置，第二种插入到其他位置。
第一种情况：插入第一个位置
从图片不难看出，首先将要插入的a结点的next指向头指针，即第一个结点(a1)的地址，然后将链表的头指针指向新插入的a结点的地址，就完成了
第二种情况：插入到其他位置
这里假设插入到3位置
让a结点的next指向a2的next，然后a2的next指向a，就完成了插入。所以，首先要找到要插入的位置的上一个结点
// 在指定的位置pos插入元素id
void InsertLinkList(LinkList *linkList, int pos, int id)
{
// 1.创建空结点并为数据域赋值
Node *node = (Node *)malloc(sizeof(Node)); //创建结点
node->id = id;
node->next = NULL;
// 2.找到要插入位置的结点
// 如果插入的是第一个元素
if (pos == 1)
{
node->next = linkList->next;
linkList->next = node; //重新设置头指针
}
else
{
// 通过循环找到要插入的结点位置
Node *prev = linkList->next; // 获取到插入pos前一个结点的地址
for (int i = 1; i < pos - 1 && prev != NULL; i++)
{
prev = prev->next;
}
// 3.将结点插入并对接前面的结点
if (prev != NULL)
{
//必须先让插入的结点的next获取到前一个结点的next指向的地址空间，
//低下这两行代码不能调换顺序
node->next = prev->next;
prev->next = node;
}
// 并不需要单独考虑结点在最后添加的情况
// 如果在尾部添加结点。因为在前面，就设置了node->next = NULL
// 所以链表的尾结点插入好后下一个空间的地址就是空
}
linkList->length++;
}单链表初始化
定义初始化函数，此初始化只出现本篇一次，后面的双链表和循环链表将不会出现初始化示例
// 初始化链表
void InitLinkList(LinkList * linkList,int length)
{
linkList.length = 0; //初始化链表长度
//注意头指针的定义是，即使链表为空，头指针也不为空，这里是本人的代码习惯，所以将头指针设置为空
linkList.next = NULL; //初始头指针为空
for (int i = 0; i < length; i++)
{
InsertLinkList(linkList,i + 1,i + 1);
}
}单链表删除
这里也要分两种情况，第一种情况:删除的位置在第一个，第二种情况:在其他位置删除
第一种情况:删除的位置在第一个示例
整个的逻辑其实是，直接让头指针指向a2即可，然后释放掉a1的内存空间即可
第二种情况:在其他位置删除
假设删除的位置是2，那么需要找到上一个结点，从图片可知让a1的next指向a2的next，然后释放掉a2的空间即可
// 在指定位置删除结点
void DeleteLinkList(LinkList *linkList, int pos)
{
// 1.指向链表的第一个结点
Node *node = linkList->next;
// 2.删除的结点为第一个
if (pos == 1)
{
linkList->next = node->next; //重新设置头指针
free(node); //记得要使用free()，这一步容易忽略
linkList->length--;
return;
}
// 3.获取要删除的结点的前一个结点地址
for (int i = 1; i < pos - 1; i++)
{
node = node->next;
}
Node *delNode = node->next; //要删除的结点的地址
node->next = delNode->next; //重新指向地址
free(delNode);
linkList->length--;
}清空链表
通过循环链表的方式，去清空链表，代码胜千言
// 清空链表
void ClearLinkList(LinkList *linkList)
{
Node *node = linkList->next; //指向链表的第一个结点
Node *nextNode;
while (node != NULL)
{
nextNode = node->next; //先记录当前结点的下一个结点以便释放当前结点的内容
free(node);
node = nextNode; //重新获取结点
}
linkList->next = NULL;
linkList->length = 0;
}打印链表
void PrintLinkList(LinkList *linkList)
{
Node *node = linkList->next; //获取到链表的第一个结点
if (node == NULL)
{
printf("链表为空\n");
return;
}
while (node != NULL)
{
printf("%d ", node->id);
node = node->next;
}
printf("\n");
}main函数展示，本篇也只出现这一次，其他类型的链表main内容都大同小异
int main()
{
LinkList linkList;
InitLinkList(&linkList, 4);
PrintLinkList(&linkList);
InsertLinkList(&linkList,1,2);
DeleteLinkList(&linkList,1);
ClearLinkList(&linkList);
PrintLinkList(&linkList);
}理解了单链表后，那么后面的循环链表和双向链表都大同小异。而从上面的代码中可看出头指针是非常重要的，用起来非常方便。
循环链表
结构图
循环链表最大的特点是尾结点的指针域指向第一个结点
定义循环链表的结点
// 循环链表的结点
typedef struct CircularNode
{
int id; //数据域
struct CircularNode *next; //指向下个结点的指针域
} CircularNode;定义循环链表的头结点
// 头结点
typedef struct CircularLinkList
{
CircularNode *next; //指向第一个结点的指针，头指针
int length;
} CircularLinkList;循环链表的插入
循环链表的插入稍微复杂了一点点，有4种情况
第一种:插入位置在第一个，链表长度不为0
第二种:插入位置在第一个，链表长度为0
第三种:插入位置在尾部
第四种:插入位置在非上述情况
虽然看起来要四种情况，但其实总的来说只有两大种，其他两小种只需要在里面，加一个if判断就能搞定
第一种:插入位置在第一个，链表长度不为0
先让a结点的next指向第一个结点的地址，然后让尾结点的next指向a结点的地址，最后头指针指向a结点的地址即可
第二种:插入位置在第一个，链表长度为0
直接让头指针指向即可
第三种:插入位置在尾部
第四种:插入位置在非上述情况
可以看到在非第一个位置插入的情况下，都需要找到前缀结点，先让a结点的next指向前缀结点的next，在让前缀结点的next指向a。如果插入的位置在最后需要更新尾结点指针域
// 在循环链表指定位置插入元素
void InsertCircularLinkList(CircularLinkList *linkList, int pos, int id)
{
// 创建一个空节点
CircularNode *node = (CircularNode *)malloc(sizeof(CircularNode));
node->id = id;
node->next = NULL;
// 插入的位置是第一个
if (pos == 1)
{
node->next = linkList->next;
// 如果长度不为0，就要找到链表的最后一个结点
if (linkList->length != 0)
{
CircularNode *lastNode = linkList->next;
for (int i = 1; i < linkList->length; i++)
{
lastNode = lastNode->next;
}
// 重新设置尾结点
lastNode->next = node;
}
linkList->next = node; //重新设置头结点
linkList->length++;
return;
}
CircularNode *currNode = linkList->next; //找到要插入的上一个结点地址
for (int i = 1; i < pos - 1 && currNode != NULL; i++)
{
currNode = currNode->next;
}
node->next = currNode->next;
currNode->next = node;
// 插入的结点在尾部
if (pos == linkList->length)
{
node->next = linkList->next; //设置尾结点指针域
}
linkList->length++;
}循环链表的删除
删除分为两种情况
第一种:在第一个位置删除
先让尾结点的next指向a2，此gif下的一步应该是让头指针指向a2，为了方便演示故此顺序不一样，最后free(a1)即可
第二种:在其他位置删除
其实循环链表的删除和单链表的删除基本是一模一样的，无非就是多了一个更新尾结点的操作
// 删除循环链表中指定位置的元素
void DeleteCircularLinkList(CircularLinkList *linkList, int pos)
{
CircularNode *node = linkList->next;
if (pos == 1)
{
CircularNode *lastNode = linkList->next; //找到最后一个结点
for (int i = 1; i < linkList->length; i++)
{
lastNode = lastNode->next;
}
lastNode->next = node->next; // 重新设置尾指针
linkList->next = node->next; // 重新设置头指针
}
else
{
// 找到要删除的结点的前一个结点
CircularNode * preNode = linkList->next;
for (int i = 1; i < pos - 1; i++)
{
preNode = preNode->next;
}
node = preNode->next; //要删除的结点地址
preNode->next = node->next;
}
free(node);
linkList->length--;
}循环链表的特殊遍历法
通过给定的某个位置，循环遍历出链表中的每个元素
只需要先拷贝当前要位置的结点的地址，用do while循环遍历，当下一个地址不等于拷贝的地址就循环打印即可
// 通过给定的某个位置，循环遍历出链表中的每个元素
void PrintCircularLinkListByNode(CircularLinkList * linkList,int pos)
{
CircularNode * node = linkList->next;
if(node == NULL || pos <= 0 || pos > linkList->length)
{
return NULL;
}
//获取到pos位置的结点的地址
for (int i = 1; i < pos; i++)
{
node = node->next;
}
CircularNode * BackupNode = node; //拷贝该结点的地址
do
{
printf("%d ",node->id);
node = node->next;
}while(node != BackupNode);
}双向链表
双向链表只是在单链表的基础上，多了一个前缀结点，就多了一份存储空间，相当于用空间换时间
结构图
老规矩，先创建结点和头结点
/** 双向链表的结点,包含一个数据域和两个指针域 */
typedef struct Node{
int id;
struct Node * next; //指向前缀结点
struct Node * prev; //指向后继结点
}Node;/** 双向链表 */
typedef struct LinkList{
int length;
Node * next;
}LinkList;双向链表的插入
第一种情况:插入的位置在第一个，链表为空
第二种情况:插入的位置在第一个，链表不为空
第三种情况:插入的位置在中间
第四种情况:插入的位置在最后
// 向双向链表指向位置插入元素
void InsertDoublyLinkList(LinkList * linkList,int pos,int id)
{
// 创建空结点
Node * node = (Node *)malloc(sizeof(Node));
node->id = id;
node->next = NULL;
node->prev = NULL;
if(pos == 1)
{
//链表不为空
if(linkList->length != 0)
{
node->next = linkList->next;
linkList->next->prev = node;
}
linkList->next = node; //更新头指针
}
else
{
Node * preNode = linkList->next; //获取到要插入位置的前缀结点
for (int i = 1; i < pos - 1; i++)
{
preNode = preNode->next;
}
// 在中间插入
if (preNode->next != NULL)
{
node->next = preNode->next;
preNode->next->prev = node;
}
node->prev = preNode;
preNode->next = node;
}
linkList->length++;
}双向链表的删除
第一种情况:删除的位置在第一个，链表长度为1
请勿将代码直接写成 头指针=null (linkList->next = null)的形式，而是换一种等价写为法:linkList->next = node->next，这种写法将直接减少代码行数
第二种情况:删除的位置在第一个，链表长度不为1
第三种情况:删除的位置在中间
第四种情况:删除的位置在最后
这里找删除结点跟前两个不一样，因为有了前缀结点，所以找结点的时候直接找到要删除的结点即可，而不是要删除的结点的前缀结点
// 在指定位置删除元素
void DeleteLinkList(LinkList * linkList,int pos)
{
Node * node = linkList->next; //获取到链表的第一个结点
if (pos == 1)
{
// 链表长度不为1
if (node->next != NULL)
{
node->next->prev = NULL;
}
linkList->next = node->next; //更新头指针
}
else
{
// 循环找到要删除的结点的位置
for (int i = 1; i < pos; i++)
{
node = node->next;
}
node->prev->next = node->next;
// 不是在最后一个位置删除
if(node->next != NULL)
{
node->next->prev = node->prev;
}
}
free(node);
linkList->length--;
}后记
至此，链表的核心操作就介绍完了，感谢大家的阅读！为了更好的理解链表的详细操作步骤，本人花费大量的时间做出这些gif图片。如果你要使用这些图片，请包含出处等信息，在此谢谢各位大佬！