一、什么是链表？
1.链表的定义
链表是是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。比较通俗易懂的说法就是，在计算机内存中开辟了一个个空间，然后通过地址的方式将它们链接在一起，并通过地址的方式进行访问。
2.链表的实现
只知道了链表的定义，估计大家还是云里雾里的，不知道什么才算是链表，接下来笔者就手动创建一个很挫的链表给大家，不通过函数的形式实现，主要是让大家先感受一下。
2.1链表的定义
在手动创建链表之前，我们要先对链表进行定义，对链表的定义，接口函数的引用和头文件的引用最好放在一个头文件中 这样在要使用创建的接口时便只需要引用一个头文件即可，而接口函数的实现你也可以放在一个.c文件中，最后在另一个.c文件中引用函数测试即可，如图：
//链表博客版.h #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int SLDateType; //链表成员我们先用int，int简单好懂 //而之所以要给它取个SLDateType的别名 //不仅仅是因为方便和int进行区分 //更主要的是以后链表的成员不想用int类型的话 //直接在这里进行修改即可 typedef struct SlistNode { SLDateType data;//成员 struct SlistNode* next; //这里给它取名叫next其实是为了方便到时使用，其实你叫它abc也是可以的 // 在链表中，一个节点通过地址链接到下一个节点，就像串串一样把它们穿起来，而这个地址则是它们唯一的联系， //我们这讲述的是单向链表，所以只能够是前面的找到后面的，从后面找到前面是不可能实现的。 }SlistNode;
2.2创建一个链表
链表，其实也没什么高大上的，就是通过地址找到下一个节点然后进行对应的访问，核心在于地址上 只要我们能够将首节点的地址链接到下一个节点，将下一个节点的地址链接到下下个节点的地址.....直到链接完成就停止即可，这里我们就先不链接那么多个节点，我们就简单的链接个节点数为3的链表
#include"链表博客版.h" int main() { SlistNode a, b, c;//创建三个节点 a.next=&b;//a节点的链接部分存储b节点的地址 b.next = &c;//b节点的链接部分存储c节点的地址 c.next = NULL;//最后一个链接到空指针上，代表着链接结束 a.data = 1; b.data = 2; c.data = 3; SlistNode* plist = &a;//将首节点保存 while (plist) { printf("%d ", plist->data);//打印节点内的内容 plist = plist->next;//不断地指向下一个节点，直到为空 } }
二、链表的各个接口
1.创建节点
创建节点是一个很重要的函数，在插入函数中需要使用。在函数中创建节点，我们就不能够像之前一样直接创建了，众所周知，在函数上创建节点出了函数就会自动销毁，为了避免节点被自动销毁，这里采用malloc的方式创建节点，别忘了在头文件中引用函数
#include"链表博客版.h" SlistNode* buy_slistnode(SLDateType x) //使用节点指针作为返回类型，来拿到创建好的新节点 { SlistNode* newnode = (SlistNode*)malloc(sizeof(SlistNode)); //使用malloc创建一个新节点 if (newnode == NULL) { perror("buy_slistnode"); exit(-1);//创建失败直接中止程序 } newnode->data = x;//将节点内容修改成需要的值 newnode->next = NULL;//将链接对象置为空，因为不知道要链接谁 return newnode; }
2.头插(将新创建的节点作为头插入到链表中)
为什么先将头插节点呢？无他，相比尾插它简单很多
void slist_pushfront(SlistNode** phead, SLDateType x) //采用二级指针的原因是，当没有节点的时候，我们要对首节点的地址进行修改 { //先创建一个新的节点 SlistNode* newnode = buy_slistnode(x); //我们要头插是吧，也就是说新创建的节点是新的头 //那么我们是不是应该把我们自己原来的头更新一下 //然后再将之前的节点，也就是之前的头链接到新的头后面 /* *phead = newnode; newnode->next = *phead;*/ //但这是错误的，原因很简单，你的头更新了，那么你就找不到之前的节点了 //换一下顺序即可 newnode->next = *phead; *phead = newnode; }
3.打印链表
插入完节点之后，也不知道自己到底有没有插入，因此我们来设计一个打印链表的函数
void print_slist(SlistNode* phead) { while (phead)//phead不为空意味着还有节点没被访问完 { printf("%d->", phead->data); phead=phead->next;//指向下一个节点 } printf("NULL\n");//访问完了打印空，提示已经访问完了 }
测试效果：
#include"链表博客版.h" void test1() { SlistNode* plist = NULL;//创建一个链表头 slist_pushfront(&plist, 1);//依次将1，2，3头插进链表中 slist_pushfront(&plist, 2);//那么链表最后应该是3为头，1为尾 slist_pushfront(&plist, 3); print_slist(plist); } int main() { test1(); }
4.尾插(将新创建的节点插入到链表的末端)
尾插要在链表的末端进行插入，那么找到链表的末端是一件必须要做的事
void slist_pushback(SlistNode** phead, SLDateType x) { SlistNode* tmp = *phead; //创建一个首节点的拷贝，避免影响到首节点的指向 SlistNode* newnode = buy_slistnode(x);//创建一个新节点 while(tmp->next) //当成员的next为空的时候意味着已经找到目标了 // 跳出循环 //接下来就是把这个成员的指向改变 { tmp = tmp->next; } tmp->next = newnode; }
很多小伙伴，写到这里的时候就以为已经完成了，但你想一想，如果此时链表中没有节点呢，也就是*phead此时为NULL的时候，你还能够指向next吗，你能对空指针进行解引用吗？显然不能，因此我们把这种情况单独处理。
void slist_pushback(SlistNode** phead, SLDateType x) { SlistNode* tmp = *phead; //创建一个首节点的拷贝，避免影响到首节点的指向 SlistNode* newnode = buy_slistnode(x);//创建一个新节点 if (*phead==NULL)//当*phead==NULL时，意味着链表为空 { *phead = newnode;//直接链接 return; } while(tmp->next) //当成员的next为空的时候意味着已经找到目标了 // 跳出循环 //接下来就是把这个成员的指向改变 { tmp = tmp->next; } tmp->next = newnode; }
测试代码：
void test2() { SlistNode* plist = NULL; slist_pushback(&plist, 10086);//依次尾插10086，666，555，111 slist_pushback(&plist, 666); slist_pushback(&plist, 555); slist_pushback(&plist, 111); print_slist(plist); } int main() { test2(); }
错误情况
程序直接就崩溃了，连print_slist即使是空也应该打印出来的NULL都没打印出来
正确情况
5.头删
void slist_popfront(SlistNode** phead) { if (*phead==NULL)//空了就别删了 { printf("链表为空，操作失败\n"); return; } SlistNode* tmp = (*phead)->next; //储存头的下一个节点，避免找不到 free(*phead);//直接释放头节点 *phead =tmp;//头节点重新指向下一个节点 }
效果测试：
void test3() { SlistNode* plist = NULL; slist_popfront(&plist);//直接删除，测试报错 slist_pushback(&plist, 10086);//依次尾插10086，666，555，111 slist_pushback(&plist, 666); slist_pushback(&plist, 555); slist_pushback(&plist, 111); print_slist(plist); slist_popfront(&plist);//删除10086 print_slist(plist); slist_popfront(&plist);//删除666 print_slist(plist); slist_popfront(&plist);//删除555 print_slist(plist); slist_popfront(&plist);//删除111 print_slist(plist); } int main() { test3(); }
