首先我们看看我们来看看顺序表有哪些不足：静态顺序表我们就不多说了，我们来看一下动态顺序表。
动态顺序表：①插入数据，空间不够要增容 ②要求数据是依次存储的
缺陷：①如果空间不够，就需要增容。增容会付出一定的性能消耗，其次可能出现一定的性能浪费 ②头部或者中部左右的插入删除效率低------》O（n）
如何去解决它了，那就需要进入我们今天的重头戏——链表
链表的特点：①空间上，按需给空间 ②不要求物理空间连续，头部和中间的插入删除，不需要挪动数据
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。
逻辑结构图：
通过以上的逻辑结构图，我们可以看出每个结点都包括两部分：数据和指针，通过指针指向下一个结点。每个结点我们都可以设置为结构体类型。
物理结构图：
通过以上的物理结构图，我们可以看除了最后一个结点的指针指向NULL，其余的指针都指向下一个结点的数据域地址。
那我们接下来，做一下对单链表的增删查找等操作。
跟上我的步伐哦！相信各位勇敢者学完定有收获
首先定义一个头文件：
#include<stdio.h> #include<stdlib.h> #pragma once typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode; //打印 void SListPrint(SLTNode* phead); //尾插 void SListPushBack(SLTNode** pphead, SLTDataType x); //头插 void SListPushFront(SLTNode** pphead, SLTDataType x); //头删 void SListPopFront(SLTNode** pphead); //尾删 void SListPopBack(SLTNode** pphead); //查找 SLTNode* SListFind(SLTNode* phead, SLTDataType x); //在pos的前面插入x void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); //删除pos位置的值 void SListErase(SLTNode** pphead, SLTNode* pos);
这个头文件主要包含了：1.库函数的声明 2.定义了一个SLTNod的结构体类型 3.自定义函数的声明
在定义一个.c的测试文件：
#include"SList.h" void TestSList1() { SLTNode* plist = NULL; SListPushBack(&plist, 1); SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPushFront(&plist,5); SListPushFront(&plist,6); SListPushFront(&plist,7); SListPrint(plist); SListPopFront(&plist); SListPrint(plist); SListPopBack(&plist); SListPrint(plist); //想在3的前面插入一个30 SLTNode* pos = SListFind(plist, 6); if (pos) { SListInsert(&plist, pos, 10); } SListPrint(plist); pos = SListFind(plist, 10); if (pos) { SListErase(&plist, pos); } SListPrint(plist); } int main() { TestSList1(); return 0; }
测试文件：通过主函数的调用TestList1，TestList1中首先定义了一个结构体指针指向SLTNode类型的结构体.
请各位思考一下为什么不定义一个结构体变量，反而定义一个结构体指针了？？？
如图所示：
观图所知，定义一个同类型的结构体指针，可以指向头结点，然后通过头结点的指针域访问第二个结点，依次如下。反而结构体变量却达不到这种效果。
那我们接下来实现头文件中的自定义函数吧！！！
//打印 void SListPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
疑惑解答：
疑惑①：大家学到这里是不是有点疑惑，但是千万别划走哦，有些侠士会想连插入都没有学，怎么打印呀！先别急，首先打印操作在单链表中相对其它操作简单一点，所以先让大家有先接受一下打印。
疑惑②：现在大家肯定还有一个疑惑，怎么让phead指针指向头结点地址了。
别急、别急学完插入之后，你就将知道phead指针是怎么指向头结点的地址了
跟上我的步伐，开始学习插入了
//尾插 void SListPushBack(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); newnode->data = x; newnode->next = NULL; if (*pphead == NULL) { *pphead = newnode; } else { SLTNode* tail = *pphead; //找到尾节点的指针 while (tail->next != NULL) { tail = tail->next; } //链接尾节点 tail->next = newnode; } }
学到这里大家，应该知道phead指针是怎样指向头结点的了吧！大家应该也知道如何实现尾插了吧！
大家可以自己先不看下面的讲解，自己先试一试头插，然后写完之后再看看与代码中的头插有哪里不同吧！！！
//头插 void SListPushFront(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); newnode->data = x; newnode->next = NULL; newnode->next = *pphead; *pphead = newnode; }
注：要是链表为空，那我们新增的结点的指针域本来就是空，然后*pphead里面也是空，把*pphead指向新结点，新结点的指针域为空，在赋一个空，不影响
//头删 void SListPopFront(SLTNode** pphead) { SLTNode* next = (*pphead)->next; free(*pphead); *pphead = next; }
