这里是只讲干货不讲废话的炽念，这个系列的文章是为了我自己以后复习数据结构而写，所以可能会用一种我自己能够听懂的方式来描述，不会像书本上那么枯燥和无聊，且全系列的代码均是可运行的代码，关键地方会给出注释^_^
全文1W+字
版本：C++17
编译器：Clion 2023.3.24
暂时只给出代码，不会涉及到基础知识的讲解
1.链表的定义
1.1定义链表结点
// 链表的核心是定义结点
typedef struct list_node{ // C语言中必须要先声明 list_node,不然编译器会报错，C++可以忽略这个问题Element value; // 结点存储的数据元素struct list_node *next; // 指向下一个结点的指针
}ListNode;1.2定义链表头结点
// 链表的表头
typedef struct {ListNode head; // 头结点,通常不存储实际数据,用作链表的起始点int len; // 链表的长度,用于记录链表中实际结点的数量
}LinkList;
2.链表的实现函数
2.1.表的创建以及删除
// 创建链表和删除链表
LinkList *createLinkList(); // 创建一个链表void releaseLinkList(LinkList* linkList); // 释放一个链表2.2.向表中插入元素
// 三种插入方式
int insertLinkList(LinkList *linkList, int pos, Element val); // 任意位置上插入int headInsertLinkList(LinkList *linkList, Element val); // 头插法int tailInsertLinkList(LinkList *linkList, Element val); // 尾插法2.3.表的展示
void showLinkList(LinkList *linkList); // 显示链表内的元素2.4.删除表中的元素
int deleteLinkList(LinkList *linkList, Element val); // 删除链表中的特定元素2.5逆转链表
void reverseLinklist(LinkList *linkList); // 逆转链表3.实现函数的代码
3.1 createLinkList函数的实现
函数定义：
LinkList *createLinkList();函数功能：
该函数用于创建一个空的链表，并返回链表的头结点指针实现思路：
a.申请一个类型为LinkList，大小为sizeof(LinkList)的头结点b.判空，判断申请是否成功c.初始化LinkList->len = 0, LinkList->head.value = 0(根据实际情况来定义这个值)d.初始化LinkList->head.next = NULLe.返回指向新创建链表头结点的指针具体实现代码：
LinkList *createLinkList() {LinkList *linkList = (LinkList *) malloc(sizeof (LinkList));if (!linkList){printf("Malloc linklist failed\n");return NULL;}linkList->len = 0; // 表示链表的长度linkList->head.value = 0; // 根据具体的场景来定义这个值linkList->head.next = NULL;printf("Create linklist success!\n");return linkList;
}测试代码：
int main(){LinkList *linkList= createLinkList();return 0;
}测试结果：
3.2 releaseLinkList函数的实现
函数定义：
void releaseLinkList(LinkList* linkList);函数功能：
释放链表中的所有节点(包括头节点)，避免内存泄漏实现思路：
方法一：头删法
a.初始化:
获取链表头结点地址并赋值给 node 指针。
node->next 指向待删除结点的下一个结点，用于备份b.循环删除:
循环遍历链表，条件为 node->next 不为空。
使用 tmp 指针指向要删除的结点 (node->next)。
将 node 的 next 指针指向 tmp 的下一个结点 (tmp->next)，移除 tmp 指向的结点。
释放 tmp 指向的结点内存。
更新链表长度，减去 1c.释放头结点:
循环结束后，释放头结点的内存方法二：循环删除法
a.初始化:
将 node 指针指向链表的头结点的下一个结点，准备开始遍历链表b.循环删除:
使用 while 循环遍历链表，直到到达链表末尾。在循环中：
备份当前要删除的结点到 tmp 指针
将当前结点的 next 指针指向下一个结点，从而将 tmp 指向的结点从链表中移除
释放 tmp 指向的结点的内存
更新链表长度，减去 1c.释放头结点:
最后释放头结点的内存具体实现代码：
方法一：头删法(不断删除头结点后的那个结点，直到为空)
void releaseLinkList1(LinkList *linkList) {if (linkList){ListNode *node = &linkList->head;// 不断的删除头结点的下一个指向，直到为空（头删法）while (node->next){ListNode *tmp = node->next; // 备份要删除的结点node->next = tmp->next; // 这里为什么不是node = node->next;free(tmp); // 因为这样已经移动了头结点，会失去对前一个节点的引用，可能导致内存泄露linkList->len--;}printf("Release success! LinkList have %d node\n",linkList->len);free(linkList);}
}
方法二：循环删除法
void releaseLinkList2(LinkList *linkList){if (linkList) {ListNode *node = linkList->head.next;// 使用循环遍历链表，释放除头结点外的每个节点(循环删除法)while (node) {ListNode *tmp = node; // 备份当前节点node = node->next; // 移动到下一个节点free(tmp); // 释放当前节点linkList->len--;}printf("Release success! LinkList have %d node\n",linkList->len);free(linkList);}
}
测试代码：
因为需要知道链表中还剩下多少元素，所以先引入加入函数
1.头删法测试代码：
int main(){LinkList *linkList= createLinkList();for (int i = 0; i < 5; i++){headInsertLinkList(linkList, i+100);}showLinkList(linkList);insertLinkList(linkList, 2, 888);showLinkList(linkList);insertLinkList(linkList, 1, 888);showLinkList(linkList);tailInsertLinkList(linkList, 999);showLinkList(linkList);tailInsertLinkList(linkList, 111);showLinkList(linkList);releaseLinkList1(linkList);return 0;
}2.循环删除法测试代码：
int main(){LinkList *linkList= createLinkList();for (int i = 0; i < 5; i++){headInsertLinkList(linkList, i+100);}showLinkList(linkList);insertLinkList(linkList, 2, 888);showLinkList(linkList);insertLinkList(linkList, 1, 888);showLinkList(linkList);tailInsertLinkList(linkList, 999);showLinkList(linkList);tailInsertLinkList(linkList, 111);showLinkList(linkList);releaseLinkList2(linkList);return 0;
}测试结果：
1.头删法测试结果：
2.循环删除法测试结果：
3.3 insertLinkList && headInsertLinkList && tailInsertLinkList 函数的实现
函数定义：
int insertLinkList(LinkList *linkList, int pos, Element val); // 任意位置上插入int headInsertLinkList(LinkList *linkList, Element val); // 头插法int tailInsertLinkList(LinkList *linkList, Element val); // 尾插法函数功能：
1.insertLinkList
在链表的指定位置插入新节点2.headInsertLinkList
在链表头部插入新节点3.tailInsertLinkList
在链表尾部插入新节点实现思路：
1.insertLinkList
a.判断链表是否为空，判断插入位置是否合法* 在 pos 的位置上插入，就要找到 pos-1 的位置* pos = 1 逻辑位置上的插入，就定义 cnt = 0 是头节点的位置* pos = 0 逻辑位置上的插入，就定义 cnt = -1 是头节点的位置b.通过遍历找到待插入结点的前一个结点c.判断 node 是否为空(逻辑完备性)d.申请结点，将新节点 newNode->next 设为 NULL，将新节点的 value 设为 vale.将 newNode->next 赋值为 node->next //这两步一定要注意顺序f.将 node->next 赋值为 newNode //这两步一定要注意顺序g.更新链表长度，LinkList->len++
2.headInsertLinkList
a.判断链表是否为空b.申请结点，将新节点 newNode->next 设为 NULL，将新节点的 value 设为 valc.将 newNode->next 赋值为 LinkList->head.next //这两步一定要注意顺序d.将 LinkList->head.next 赋值为 newNode->next //这两步一定要注意顺序e.更新链表长度，LinkList->len++3.tailInsertLinkList
问：如何让尾插法达到O(1)的效率？
答：在定义链表头的时候增设尾指针，尾指针始终指向最后一个结点，即可实现O(1)的效率
a.判断链表是否为空b.申请结点，将新节点 newNode->next 设为 NULL，将新节点的 value 设为 valc.判断 LinkList 是否为只有头节点的链表d.如果是只有头节点的链表，则直接插入到头节点后*即 LinkList->head.next = newNode;e.如果不是，则不断循环找到尾节点，之后插入到尾节点后*即 node->next = newNode;g.更新链表长度，LinkList->len++
具体实现代码：
1.insertLinkList
int insertLinkList(LinkList *linkList, int pos, Element val) {if (!linkList){printf("LinkList is null. Insert error!\n");return -1;}if (pos < 1 || pos > linkList->len + 1){printf("Insert position out of range!\n");return -1;}ListNode *node = &linkList->head;int cnt = 0;while (node && cnt < pos - 1){ // 找到待插入位置的前一个位置node = node->next;cnt++;}// 判断是找到了pos-1的位置，还是遍历完链表都没有找到if (node == NULL){ // 为了逻辑完备性，多加一段代码printf("Insert position out of range!\n");return -1;}ListNode *newNode = (ListNode *) malloc(sizeof (ListNode)); //这段是核心代码newNode->next = NULL;newNode->value = val;newNode->next = node->next; // 这里注意顺序，一定要先保存当前结点的下一个结点的位置node->next = newNode;linkList->len++;return 0;
}2.headInsertLinkList
int headInsertLinkList(LinkList *linkList, Element val) {if (!linkList){printf("LinkList is null. Insert error!\n");return -1;}ListNode *newNode = (ListNode *) malloc(sizeof (ListNode));if (newNode == NULL) {printf("Memory allocation failed.\n");return -1;}newNode->next = NULL;newNode->value = val;newNode->next = linkList->head.next;linkList->head.next = newNode;linkList->len++;return 0;
}3.tailInsertLinkList
int tailInsertLinkList(LinkList *linkList, Element val) {if (!linkList) {printf("LinkList is null. Insert error!\n");return -1;}ListNode *newNode = (ListNode *) malloc(sizeof(ListNode));if (newNode == NULL) {printf("Memory allocation failed.\n");return -1;}newNode->value = val;newNode->next = NULL; // 初始化新节点的 next 指针为空if (linkList->head.next == NULL) { // 链表为空，直接将新节点插入到头节点linkList->head.next = newNode;} else {ListNode *node = linkList->head.next;while (node->next != NULL) { // 找到最后一个节点node = node->next;}node->next = newNode; // 将最后一个节点的 next 指向新节点}linkList->len++;return 0;
}测试代码：
1.insertLinkList
int main(){LinkList *linkList= createLinkList();for (int i = 0; i < 5; i++){headInsertLinkList(linkList, i+100);}showLinkList(linkList);insertLinkList(linkList, 5, 888);showLinkList(linkList);insertLinkList(linkList, 2, 888);showLinkList(linkList);insertLinkList(linkList, 1, 888);showLinkList(linkList);insertLinkList(linkList,999, 888);showLinkList(linkList);releaseLinkList2(linkList);return 0;
}2.headInsertLinkList
int main(){LinkList *linkList= createLinkList();for (int i = 0; i < 5; i++){headInsertLinkList(linkList, i+100);}showLinkList(linkList);releaseLinkList2(linkList);return 0;
}3.tailInsertLinkList
int main(){LinkList *linkList= createLinkList();for (int i = 0; i < 5; i++){tailInsertLinkList(linkList, i+100);}showLinkList(linkList);releaseLinkList2(linkList);return 0;
}测试结果：
1.insertLinkList
2.headInsertLinkList 
3.tailInsertLinkList
3.4 void showLinkList(LinkList *linkList);
函数定义：
void showLinkList(LinkList *linkList); // 显示链表内的元素函数功能：
将链表中的所有元素依次打印到控制台实现思路：
a.判断传入链表是否为空b.定义 node 为头节点后的第一个节点c.遍历链表，同时打印node->val，直到链表为空
具体实现代码：
void showLinkList(LinkList *linkList) {if (!linkList){printf("LinkList is null. Show error!\n");return;}ListNode *node = linkList->head.next;while (node){printf("%d ", node->value);node = node->next;}printf("\n");
}
测试代码：
int main(){LinkList *linkList= createLinkList();for (int i = 0; i < 5; i++){headInsertLinkList(linkList, i+100);}showLinkList(linkList);releaseLinkList2(linkList);return 0;
}测试结果：
3.5 deleteLinkList函数的实现
函数定义：
int deleteLinkList(LinkList *linkList, Element val)函数功能：
从链表中删除第一个值为 val 的节点实现思路：
a.判断传入的链表是否为空b.用循环找到待删除节点的 前一个 结点c.判断链表的下一个结点是否为空(逻辑完备性)d.用一个指针 tmp 指向待删除的结点e.将 node->next(待删除结点的前一个结点) 设为 tmp->next(删除结点的下一个结点)f.释放掉 tmp 的空间g.更新链表长度，LinkList->len--具体实现代码：
int deleteLinkList(LinkList *linkList, Element val) {if (!linkList) {printf("LinkList is null. Delete error!\n");return -1;}ListNode *node = &linkList->head;while (node->next && node->next->value != val){node = node->next;}if (!node->next){printf("Find element failed! Delete failed!\n");return -1;}ListNode *tmp = node->next; // 注意顺序node->next = tmp->next;free(tmp);linkList->len--;return 0;
}
测试代码：
int main(){LinkList *linkList= createLinkList();for (int i = 0; i < 5; i++){headInsertLinkList(linkList, i+100);}showLinkList(linkList);deleteLinkList(linkList, 104);showLinkList(linkList);deleteLinkList(linkList, 100);showLinkList(linkList);deleteLinkList(linkList, 104);showLinkList(linkList);deleteLinkList(linkList, 102);showLinkList(linkList);releaseLinkList2(linkList);return 0;
}测试结果：
3.6 reverseLinklist函数的实现
函数定义：
void reverseLinklist(LinkList *linkList);函数功能：
将给定的单链表反转实现思路：
方法一：
a.判断当前链表是否为空b.初始化
cur = LinkList->head.next (头节点的下一个)
pre = NULL
LinkList->head.next = NULL (注意cur一定要在之前就要赋值)c.循环
备份当前结点 (pre = cur)
移动cur避免丢失 (cur = cur->next)
将pre->next = LinkList->head.next (不断往头节点后插入结点)
将 LinkList->head.next = pre (将头节点指向正确的位置)方法二：
a.判断当前链表是否为空b.初始化
cur = LinkList->head.next (头节点的下一个)
nxt = NULL
LinkList->head.next = NULL (注意cur一定要在之前就要赋值)c.循环
备份下一个结点 (nxt = cur->next)
将 cur->next = LinkList->head.next (不断往头节点后插入结点)
将 LinkList->head.next = cur (将头节点指向正确的位置)
cur = nxt (避免结点丢失)方法三：
a. 将链表所有的结点全部压入到栈中(除了头节点)
b. 利用栈先进后出的特性，出栈一个元素，头节点就连接一个元素
c. 注意使用 尾插法 来连接元素具体实现代码：
方法一(备份当前节点，反转当前结点)：
void reverseLinklist1(LinkList *linkList) {if (!linkList) {printf("LinkList is null. Delete error!\n");return;}ListNode *cur = linkList->head.next;ListNode *pre = NULL;linkList->head.next = NULL;while(cur){pre = cur;cur = cur->next;pre->next = linkList->head.next;linkList->head.next = pre;}printf("Reverse success!\n");
}方法二(备份下一个结点，反转当前结点)：
void reverseLinklist2(LinkList *linkList) {if (!linkList) {printf("LinkList is null. Delete error!\n");return;}ListNode *cur = linkList->head.next;ListNode *nxt = NULL;linkList->head.next = NULL;while (cur){nxt = cur->next;cur->next = linkList->head.next;linkList->head.next = cur;cur = nxt;}printf("Reverse success!\n");
}方法三：
这里在栈的部分写，到时候放一个链接
测试代码：
方法一：
int main(){LinkList *linkList= createLinkList();for (int i = 0; i < 5; i++){headInsertLinkList(linkList, i+100);}showLinkList(linkList);reverseLinklist1(linkList);releaseLinkList2(linkList);return 0;
}方法二：
int main(){LinkList *linkList= createLinkList();for (int i = 0; i < 5; i++){headInsertLinkList(linkList, i+100);}showLinkList(linkList);reverseLinklist2(linkList);releaseLinkList2(linkList);return 0;
}测试结果：
方法一：
方法二：
