前言：
应部分粉丝要求，专门抽出一个专题来讨论下链表相关的数据结构，今天这篇文章来简单探讨下单向链表，后面会陆续出单向循环链表、双向链表、双向循环链表，还没关注的小伙伴抓紧时间关注起来啦。
简介：
链表也是一种数据结构，链表分为数据域和指针域
数据域：存放当前节点的数据
指针域：指向下一个节点，通过next指针把每个节点串联起来，形成一个链式的数据结构，因此得名链表。
链表和数组的区别：
说到这里很多人可能都在想，链式串联起来的数据结构不是和数组很像吗？确实，他们两之间有共同点，也有各自的优缺点，下面我们就来剖析下两者的区别：
从内存分配上：
· 数组是静态分配的内存空间
· 链表是程序员在堆区动态分配的内存
从内存的存储方面上：
· 数组在内存中是连续存储的会造成一定的内存浪费，在定义数组的长度的时候必须预先规定其大小，如果长度过大会造成内存浪费。
· 链表在内存中是不连续的，通过指针将每个节点串接起来，其内存利用率高，能灵活的拓展我们要使用的内存空间。
从查找元素方面上：
· 数组有下标查询定位，能快速的访问元素，查找的事件复杂度是O(1)
· 链表通过遍历所有节点查找元素，时间复杂度O(n)
从插入和删除元素上：
· 数组插入和删除元素需要移动其他元素，时间复杂度O(n)
· 链表则不需要移动其他元素，只需要该表指针的指向即可，时间复杂度O(1)，链表的插入和删除的效率高
删除节点图示：
插入节点图示
链表中节点的定义：
struct stList_node { int data; /*! 数据域 */ struct stList_node *next; /*! 指针域 */ };
在使用单向链表的时候我们经常会定义一个头节点，该节点不存放数据，用于对整个链表的遍历查找，能方便的实现链表的遍历、头插、尾插等过程。
下面小编整理了几个链表操作的常用接口，并针对这些接口实现了链表的代码。这些接口的作用通过函数名就能知道是什么作用了。下面来一个一个详细介绍下。
extern int CreatListHead(struct stList_node **head); extern eListType ifListempty(struct stList_node *head); extern void List_Print(struct stList_node *head); extern int ListInsertByHead(struct stList_node *head, int data); extern int ListInsertByTail(struct stList_node *head, int data); extern int ListDeleteByHead(struct stList_node *head); extern int ListDeleteByTail(struct stList_node *head); extern int ListDeleteByData(struct stList_node *head, int data, eListType type);
list.h
#ifndef __LIST_H__ #define __LIST_H__ #include "stdio.h" #include "stdlib.h" struct stList_node { int data; /*! 数据域 */ struct stList_node *next; /*! 指针域 */ }; typedef enum { TYPE_NULL = 0, DELETE_ALL_SAME_DATA = 1, DELETE_ONE_DATA = 2, LIST_EMPTY = 3, LIST_NOT_EMPTY = 4, }eListType; extern int CreatListHead(struct stList_node **head); extern eListType ifListempty(struct stList_node *head); extern void List_Print(struct stList_node *head); extern int ListInsertByHead(struct stList_node *head, int data); extern int ListInsertByTail(struct stList_node *head, int data); extern int ListDeleteByHead(struct stList_node *head); extern int ListDeleteByTail(struct stList_node *head); extern int ListDeleteByData(struct stList_node *head, int data, eListType type); #endif /* __LIST_H__ */
list.c
#include "list.h" /* * 函数名称：CreatListHead * 输入参数：{struct stList_node **} head：头节点 * 返 回 值：-1：创建失败，原因是内存申请失败 0：创建成功 * 作 者：Barry * 功能描述：创建头链表的头指针并为其申请内存空间 * 修改记录：None */ int CreatListHead(struct stList_node **head) { /* 创建头节点 */ *head = (struct stList_node *)malloc(sizeof(struct stList_node)); if(*head == NULL) return -1; (*head)->data = -1; (*head)->next = NULL; return 0; } /* * 函数名称：ifListempty * 输入参数：{struct stList_node **} head：头节点 * 返 回 值：TRUE：空链表 FALSE：非空链表 * 作 者：Barry * 功能描述：通过头指针判断链表是否为空 * 修改记录：None */ eListType ifListempty(struct stList_node *head) { if(head->next == NULL) return LIST_EMPTY; else return LIST_NOT_EMPTY; } /* * 函数名称：List_Print * 输入参数：{struct stList_node **} head：头节点 * 返 回 值：None * 作 者：Barry * 功能描述：通过头指针遍历链表节点并打印 * 修改记录：None */ void List_Print(struct stList_node *head) { struct stList_node *p; /* 空链表走这个分支 */ if(ifListempty(head) == LIST_EMPTY) return; for(p = head->next; p != NULL; p = p->next) printf("%d \t", p->data); printf("\r\n"); } /* * 函数名称：ListInsertByHead * 输入参数：{struct stList_node **} head：头节点 {int } data：待插入的数据 * 返 回 值：-1:节点内存申请失败 0：删除成功 * 作 者：Barry * 功能描述：链表头插法，在链表的头部插入数据 * 修改记录：None */ int ListInsertByHead(struct stList_node *head, int data) { /* 定义待插入的节点 */ struct stList_node *node = NULL; /* 插入的节点申请内存空间 */ node = (struct stList_node *)malloc(sizeof(struct stList_node)); if(node == NULL) return -1; node->data = data; node->next = head->next; head->next = node; return 0; } /* * 函数名称：ListInsertByTail * 输入参数：{struct stList_node **} head：头节点 {int } data：待插入的数据 * 返 回 值：-1:节点内存申请失败 0：删除成功 * 作 者：Barry * 功能描述：链表尾插法，在链表的尾部插入数据 * 修改记录：None */ int ListInsertByTail(struct stList_node *head, int data) { /* 定义待插入的节点 */ struct stList_node *node = NULL; /* 遍历链表 */ struct stList_node *p = head; /* 插入的节点申请内存空间 */ node = (struct stList_node *)malloc(sizeof(struct stList_node)); if(node == NULL) return -1; node->data = data; node->next = NULL; while(p->next != NULL) { p = p->next; } p->next = node; return 0; } /* * 函数名称：ListDeleteByHead * 输入参数：{struct stList_node **} head：头节点 * 返 回 值：-1:删除失败，原因：链表为空 0：删除成功 * 作 者：Barry * 功能描述：链表头删法，在链表的头部删除数据 * 修改记录：None */ int ListDeleteByHead(struct stList_node *head) { struct stList_node *p = head->next; /* 空链表走这个分支 */ if(ifListempty(head) == LIST_EMPTY) return -1; head->next = p->next; free(p); return 0; } /* * 函数名称：ListDeleteByTail * 输入参数：{struct stList_node **} head：头节点 * 返 回 值：-1:删除失败，原因：链表为空 0：删除成功 * 作 者：Barry * 功能描述：链表尾删法，在链表的尾部删除数据 * 修改记录：None */ int ListDeleteByTail(struct stList_node *head) { /* 当前节点 */ struct stList_node *cur = NULL; /* 上一个节点 */ struct stList_node *prev = NULL; /* 空链表走这个分支 */ if(ifListempty(head) == LIST_EMPTY) return -1; cur = head; while(cur->next != NULL) { prev = cur; cur = cur->next; } free(cur); /* 将上一节点的next指针指向空，否则free cur节点后prev->next没有任何指向，导致程序异常 */ prev->next = NULL; return 0; } /* * 函数名称：ListDeleteByTail * 输入参数：{struct stList_node **} head：头节点 {int } data：待删除的数据 {eListType } type：删除方式 DELETE_ALL_SAME_DATA：删除链表中所有的data数据 DELETE_ONE_DATA ：删除链表中遍历到的第一个data数据（从头部开始遍历） * 返 回 值：-1:删除失败，原因：链表为空 0：删除成功 * 作 者：Barry * 功能描述：删除指定数据的链表，删除单个数据或链表中所有等于data的节点 * 修改记录：None */ int ListDeleteByData(struct stList_node *head, int data, eListType type) { struct stList_node *cur = NULL; struct stList_node *prev = NULL; struct stList_node *ptemp = NULL; /* 空链表走这个分支 */ if(ifListempty(head) == LIST_EMPTY) return -1; cur = head; prev = head; ptemp = cur; while(cur != NULL) { if(cur->data == data) { prev->next = cur->next; ptemp = cur; free(ptemp); /* 释放ptemp后cur没有指向任何内容，将其指向下一个要判断数据的节点 */ cur = prev->next; if(type == DELETE_ONE_DATA) break; } else { prev = cur; /* 向后移动一个节点 */ cur = cur->next; } } return 0; }
有兴趣的想要深入学习的可以研究下上面的代码。如有问题也请评论区指出，小编修改更正。
来简单的测试下上面的几个接口：
main.c
#include "list.h" struct stList_node *ListHead = NULL; int main(void) { CreatListHead(&ListHead); ListInsertByTail(ListHead, 4); ListInsertByTail(ListHead, 4); ListInsertByTail(ListHead, 1); ListInsertByTail(ListHead, 2); ListInsertByTail(ListHead, 3); ListInsertByTail(ListHead, 4); ListInsertByTail(ListHead, 3); ListInsertByTail(ListHead, 3); ListInsertByTail(ListHead, 4); List_Print(ListHead); ListDeleteByData(ListHead, 4, DELETE_ALL_SAME_DATA); List_Print(ListHead); return 0; }
从上面的代码知道我们利用尾插法插入一些元素，并打印出来，再调用删除节点的接口删除指定数据，下面来看下运行结果吧！
由于我们上面删除的接口是删除链表中所有数据是4的节点，因此删除前后的打印是上图这样的。
我们修改一下传入的参数，修改成只删除一个数据即
ListDeleteByData(ListHead, 4, DELETE_ONE_DATA);
再看下效果吧！
这次就只删除了第一个数据为4的节点。
我们再来测试下其他的接口：
使用头插法插入数据，再通过尾删法删除一个数据
ListInsertByHead(ListHead, 4); ListInsertByHead(ListHead, 3); ListInsertByHead(ListHead, 2); ListInsertByHead(ListHead, 1); List_Print(ListHead); ListDeleteByTail(ListHead); List_Print(ListHead);
运行结果如下：
每次插入数据都在头部插入数据，因此链表中的数据是1 2 3 4，数据4在插入完成后变成尾部，通过尾删法删除后的打印是1 2 3，结果也是符合预期的。
其他的接口小编都测试过了，在这里就不一一测试啦，有兴趣的小伙伴可以测试下。
上述的三个文件放到VS Code上就可以直接运行。
如果觉得本篇文章多少有点帮助的话大家不要忘了，点赞、关注、评论、转发哦，创作不易！你们的支持是小编创作的最大动力。
