文章目录
1.链表的概念
链表是一种基础的数据结构，链表可以动态的进行存储分配，也就是说，链表是一个功能极为强大的数组，他可以在节点中定义多种数据类型，还可以根据需要随意增添，删除，插入节点。我们每次只分配出一个节点的内存。链表使用指针将各个节点组合到一起，这样就形成了一个连一个的链式的结构，这就是链表这个名称的由来。
下面具体介绍链表的增添，删除，插入节点是怎么实现的。
2.链表的实现
2.1链表的结构
首先我们来看看链表的具体结构，他是由一个一个的节点链接起来的，，每个节点都包括两部分，一部分数据域，存放我们序要的数据内容，一部分为指针域，用来连接下一个节点。最后一个节点的指针域指向空。如下图所示。
2.2链表的初始化
要创建一个新的链表，首先我们的定义一个链表的结构体，结构体中就是包含数据部分和指针部分，数据我们可以定义为void* 类型，这样我们就可以接收任意类型的数据了。
typedef struct ListNode
{
void* date; //数据域
struct ListNode* next; //指针域，指向下一个节点
}ListNode;
定义完链表的结构体之后，我们还要初始化出一个链表的头结点，也就是上图中的phead，方便我们进行增删改查的操作。下面通过两个函数来完成这操作。首先我们要写一个创建新节点的函数，然后在创建一个头结点。
//创建新节点
ListNode* BuyNode(void* newdate)
{
//为新节点开辟空间
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
//给新节点赋值
newNode->date = newdate;
newNode->next = NULL;
return newNode;
}
//初始化链表。创建头结点
ListNode* InitList()
{
void* date = NULL;
ListNode* phead = BuyNode(date);
phead->date = NULL;
phead->next = NULL;
return phead;
}
2.3插入节点
链表的插入，一般分为头插和尾插，还有任意位置的插入，这里我就写一个任意位置的插入。在一个pos位置插入一个节点，我们先得找到该位置的前一个节点posPrve，新节点newNode->next指向pos位置，然后使得posPrve->next指向新节点newNode。如下图所示
下面看具体代码
//在进行插入操作中，我们要用到链表的长度，所以先写个函数求去链表的长度。
//这个比较简单遍历一遍链表就可以了
int lenthOfList(ListNode* phead)
{
int count = 0;
while (phead)
{
phead = phead->next;
count++;
}
return count;
}
void InsertList(ListNode* phead, int pos, void* date)
{
assert(phead);
//判断pos位置的有效性
if (pos < 0)
{
return;
}
if (date == NULL)
{
return;
}
//创建新的数据节点
ListNode* newNode = BuyNode(date);
//得到链表长度
int lenth = lenthOfList(phead);
//如果pos位置大于链表长度就进行尾插，这个由自己决定
if (pos > lenth)
{
ListNode* last = phead;
//遍历到链表的尾
while (last->next)
{
last = last->next;
}
//尾插
last->next = newNode;
newNode->next = NULL;
return;
}
ListNode* cur = phead;
//遍历到pos位置的前一个位置
for (int i = 1; i < pos; i++)
{
cur = cur->next;
}
newNode->next = cur->next;
cur->next = newNode;
}
2.4删除节点
删除节点这里提供两种方法来进行删除操作，一种是通过给定位置进行删除，一种是通过数据内容来删除。
2.4.1通过位置来进行删除
首先我们要找到pos位置的节点，并要记录pos位置的前一个节点，及该节点为posPrve,然后使得posPre->next指向pos->next就行了。
void removeByPosList(ListNode* phead, int pos)
{
assert(phead);
//得到链表的长度
int lenth = lenthOfList(phead);
//判断位置有效性
if (pos<0 || pos>lenth)
{
return;
}
ListNode* posPrve= phead;
//遍历到链表的前一个节点
for (int i = 1; i < pos; i++)
{
posPrve= posPrve->next;
}
//得到要删除的节点
ListNode* posNode = posPrve->next;
//进行删除操作
posPrve->next = posNode ->next;
//释放掉删除位置的空间
free(posNode);
posNode == NULL;
}
2.4.2通过数据来删除节点
通过数据来删除节点，首先我们要先找出链表中与我们要删除节点数据相同的节点，然后再来进行删除操作。
那么我们要怎么才能找到那个数据相同的节点呢？因为我们链表的结构体中，存放的数据是void* 型的数据，所以我们可以用一个函数指针来用作回调函数来进行判断。在下面我会介绍函数指针怎么用
void removeByDateList(ListNode* phead, void* date, bool(*myCompar)(void*,void*))
{
assert(phead);
ListNode* cur = phead;
while (cur)
{
//记录当前节点的前一个节点
ListNode* curPrve = cur;
cur = cur->next;
//判断数据是否相同，相同就进行删除操作
if (myCompar(cur->date,date))
{
curPrve->next = cur->next;
free(cur);
cur = NULL;
break;
}
}
}
可能有人对回调函数不知道怎么写，那么我下面列举一种自定数据类型，来进行举例
//定义一个自定义数据类型，假如链表中存放着该数据类型
//然后可以将该函数用作回调函数，对链表数据进行判断
struct Person
{
char name[64];
int age;
};
//写一个函数来判断数据是否相同，相同返回真，否则返回假
bool myCompar(void* date1, void* date2)
{
struct Person* p1 = date1;
struct Person* p2 = date2;
if ((strcmp(p1->name, p2->name) == 0) && (p1->age == p2->age))
{
return true;
}
return false;
}
2.5打印链表
因为，这里我们是定义的void* 型的数据，所以链表里的数据不能直接打印出来，也只能通过回调函数来进行打印。看到这里，有人也许会问为什么要用 void * 类型的数据，用 void * 类型的数据，遍历和查找都要提供回调函数，不是更麻烦了吗。其实不然，用 void * 类型的数据可以接收任意类型的数据，这样的话，等我们下一次要换数据类型的时候，就不用了频繁的更改代码，这样也就更方便了
//打印信息，用作遍历数组的回调函数
void myPrint(void* date)
{
struct Person* p = date;
printf("姓名:%s 年龄: %d\n", p->name, p->age);
}
void foreachList(ListNode* phead, void(*myforeach)(void*))
{
assert(phead);
ListNode* first = phead->next;
while (first)
{
myforeach(first->date);
first = first->next;
}
}
2.6清空链表
清空链表就比较简单了，就是将链表中的所有节点都删除就好了。
清空链表也分为两种，一种是不清楚头结点，一种是全部清除。
2.6.1不清空头结点
void clearList(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur)
{
ListNode* curNext = cur->next;
free(cur);
cur = curNext;
}
phead->next = NULL;
}
2.6.2清空头结点
void destorList(ListNode* phead)
{
assert(phead);
clearList(phead);//调用上面写好的函数
free(phead);
phead = NULL;
}