1.什么是单链表
单链表也是一种存储数据的结构之一，他和我们上一节讲到的顺序表有很大的去区别，上一节讲到的顺序表是由一个结构体做的框架，结构体里面有malloc开出的空间来存储数据，而今天的单链表是由数个结点构成的，每一个结点又都是一个小的结构体，因为每一个结构体里不仅有存储数据的空间，还有一个指针来存储下一个结点的地址，用来指向下一个结点。这样我们就可以发现单链表是由数个结点串起来。基于这样的结构，单链表是在内存空间里面是不连续的，但是在逻辑上是连续的。这也是单链表和顺序表最大的区别。后面我们将基于这样的结构特点，实现单链表的各种功能。
2.单链表的结构
单链表又一个个结点构成，结点又是一个结构体。结构体里面有两个结构体成员，第一个是一个存储数据的变量（data），第二个是一个指向下一个结构的结构体类型的指针（next），但是单链表的最后一个结点的next指向NULL，代表链表结束。代码示例：
typedef struct SlistNode { SListdataType data; struct SlistNode* next; }SlistNode;
这里使用typedef 是struct SlistNode 重命名为 SlistNode。
3.开辟一个新的结点
当我们有一个数据需要一个结点存储的时候，就需要开辟一个结点，结点也就是一个结构体，我们可以使用malloc开辟一个struct SlistNode结构体大小的空间作为一个结点，并将数据存入结点的data里面，因为新开辟的结点自然而然也就是单链表的最后一个结点，所以新开辟的结点的next需要指向空。代码实例：
SlistNode* BuySListNode(SListdataType x)//开辟结点；x 代表存储的数据； { //增加结点的时候，结点是一个结构体，里面有一个结构体类型的指针，和一个数据存储变量， //所以申请空间的时候要申请一个节点的大小； SlistNode* newNode = (SlistNode*)malloc(sizeof(SlistNode)); if (newNode == NULL)//判断是否开辟成功； { printf("开辟失败！"); exit(-1); } newNode->data = x;//结点开辟成功后，将待存数据 x，存入data； newNode->next = NULL;//新增加的结点也是最后一个结点，需要将节点里面的结构体指针置空； return newNode; }
这里如果开辟失败，后面也就没有必要对结构体操作的必要，直接exit（-1）暴力终止，最后我们返回新开辟节点的地址，因为需要将新开辟的节点的接到上一个结点的后面。
4.在链表的尾部插入一个节点数据
在链表的尾部插入一个节点数据，可以分为两步：（1）生成一个结点，并且将数据存入节点的data里面，将节点的next置空，因为新生成的结点也就是最后一个结点（2）将前一个结点里面的结构体指针指向新生成的结点的地址。这样就保持了我们单链表的逻辑上的连续性。
图片示例：
代码示例：
void SListpushback(SlistNode** pphead, SListdataType x)//尾插结点数据； { SlistNode* newNode = BuySListNode(x); if (*pphead == NULL)//如果，*pphead为空，就意味着链表第一个结点就是空；直接增加一个结点 { *pphead = BuySListNode(x);//将新增的节点的地址赋值给*pphead； } else//如果第一个结点不是空 { SlistNode* tail = *pphead; while (tail->next != NULL)//找到最后一个结点； { tail = tail->next; } tail->next = newNode;//找到最后一个结点之后,将最后一个结点里面的结构体指针，赋值为新增加的节点的地址； } }
int main() { SlistNode* plist = NULL; SListpushback(&plist, 100); SListpushback(&plist, 200); SListpushback(&plist, 300); SListpushback(&plist, 400); SListpushback(&plist, 500); SListpushback(&plist, 600); SListpushback(&plist, 700); return 0; }
这里调用的时候使穿过的时plist的地址，plist是一个结构体的指针，如果我们只是传的时plist，也就是简单的传值，虽然pliat本身是个地址，但是传递过去的是plist，plist最为一个值传递过去了，传值的调用是无法对链表发生变化的，所以这里是使用了&plist，作为函数的形参，就要用二级指针，来接收实参。也是为数不多的使用到二级指针的地方。
调用BuySListNode(x)函数返回的是新生成的节点的地址。如果，*pphead为空，就意味着链表第一个结点就是空；直接增加一个结点，将新增的节点的地址赋值给*pphead；
单链表打印函数：单链表的遍历，只要循环的打印data的值，并且将结点往后移一下，看代码示例：
void SlistPrintf(SlistNode* phead)//打印函数 { SlistNode* cur = phead;//为了不在原链表上操作；我们重新用一个链表的头来操作； while (cur != NULL)//当cur==NULL时，链表结束。 { printf("%d ", cur->data); cur = cur->next;//结点往后移； } }
我们借助，打印函数，来看一下代码的效果，
5.删除链表尾部的结点
删除链表尾部的一个结点，其实很简单，我们只要找到最后一个结点，并且把它用free（），释放掉，再把倒数第二个结点的next置空。因为最后一个结点没有了以后，倒数第一个结点就是最后一个结点了。 但是有一个点需要注意，就是当我们找到最后一个结点的时候，就回不到倒数第二个结点里面的next，也就没办法给他置空了，所以为了能够在找到倒数第一个结点的时候还能找到倒数第二个，我们可以定义一前一后两个指针，后面的指针指到倒数第一个结点的时候，前面的指针就可以指向倒数第二个指针了。
图片示例：
代码示例：
void SListpophback(SlistNode** pphead)//尾删结点； { if (*pphead == NULL)//说明一个结点都没有，无需操作； { return; } else if ((*pphead)->next == NULL)//就一个结点，直接把结点的空间地址置空； { free(*pphead); *pphead = NULL; } else//有多个结点； { SlistNode* prev = NULL; SlistNode* tail = *pphead; while (tail->next != NULL)//先找到最后一个结点； { prev = tail; tail = tail->next; } free(tail); prev->next = NULL;//将最后一个结点的地址置空； } }
如果链表中就一个结点，就不必考虑这么多了，直接 将这个结点free就可以了；
调用：
int main() { SlistNode* plist = NULL; SListpushback(&plist, 100); SListpushback(&plist, 200); SListpushback(&plist, 300); SListpushback(&plist, 400); SListpushback(&plist, 500); SListpushback(&plist, 600); SListpushback(&plist, 700); printf("尾删前:"); SlistPrintf(plist); printf("\n"); printf("尾删后:"); SListpophback(&plist); SlistPrintf(plist); return 0; }
执行效果：
6.查找一个结点，以及改动一个结点
我们查找一个数据X，所在的结点，找到之后就直接返回结点的地址，如果没有就返回NULL；查询的方式很简单，接直接遍历链表，遍历的同时进行判断。
代码示例：
SlistNode* FindList(SlistNode* phead, SListdataType x)//查找一个结点； { SlistNode* cur = phead; while (cur != NULL) { if ((cur->data) == x)//如果相等，就找到了，返回cur； { return cur; } else { cur = cur->next;//不相等就往后走，判断下一个； } } return NULL;//走到这里，链表都遍历完了，就是没找到，返回NULL； }
这里代码方便演示，我们找到那个数据的结点地址，并且把它改动一下，调用的主函数：
int main() { SlistNode* plist = NULL; SListpushback(&plist, 100); SListpushback(&plist, 200); SListpushback(&plist, 300); SListpushback(&plist, 400); SListpushback(&plist, 500); SListpushback(&plist, 600); SListpushback(&plist, 700); printf("改动前:"); SlistPrintf(plist); printf("\n"); SlistNode* pos= FindList(plist, 300);//获得数据所在结点的地址； if (pos != NULL)//找到数据的结点并且改动数据内容； { pos->data = 3000; } printf("改动后:"); SlistPrintf(plist); return 0; }
代码执行效果：
7. 在pos之后增加一个结点
在pos位之后，增加一个结点，首先我们结合查询函数，获得你想插入链表中的一个中间位置的地址，这个位置地址就是pos，我们申请一个新的结点（newNode），先将pos后一个结点的地址（pos->next）给新结点的next，再将新结点的地址给pos->next。这样新增加的结点就和我们的链表连接起来了。这里的先后顺序是不能变的，因为如果pos->next=newNode;后面也就找不到pos后面的一个结点。
void SlistInserAfter(SlistNode** pos, SListdataType x)//在pos之后增加一个结点； { assert(*pos); SlistNode* newnode = BuySListNode(x); newnode->next = (*pos)->next; (* pos)->next = newnode; }
函数调用：
int main() { SlistNode* plist = NULL; SListpushback(&plist, 100); SListpushback(&plist, 200); SListpushback(&plist, 300); SListpushback(&plist, 400); SListpushback(&plist, 500); SListpushback(&plist, 600); SListpushback(&plist, 700); printf("插入前:"); SlistPrintf(plist); printf("\n"); SlistNode* pos= FindList(plist, 300); SlistInserAfter(&pos, 350); printf("插入后:"); SlistPrintf(plist); return 0; }
我们利用查询函数查询了300的结点位置地址，300的后面增加一个存入350的结点；
代码执行效果：
8.删除pos后面的一个结点
首先先保存一下，被删除结点的地址，在将pos的next指向被删除后面的结点的地址，最后释放掉被删除结点的空间，并将指针置空。
代码示例
void SlistEraseAfter(SlistNode** pos)//删除pos之后的一个结点； { assert(*pos); SlistNode*Next=(*pos)->next; (*pos)->next = Next->next; free(Next); Next = NULL; }
函数调用代码：
int main() { SlistNode* plist = NULL; SListpushback(&plist, 100); SListpushback(&plist, 200); SListpushback(&plist, 300); SListpushback(&plist, 400); SListpushback(&plist, 500); SListpushback(&plist, 600); SListpushback(&plist, 700); printf("插入前:"); SlistPrintf(plist); printf("\n"); SlistNode* pos= FindList(plist, 300); SlistInserAfter(&pos, 350); printf("插入后:"); SlistPrintf(plist); SlistEraseAfter(&pos); printf("\n"); printf("删除后:"); SlistPrintf(plist); return 0; }
代码执行效果：
9.单链表的优缺点
单链表的优点：
1.链表是一个动态数据结构，因此它可以在运行时通过分配和取消分配内存来增长和收缩。 因此，无需给出链表的初始大小。
2.节点的插入和删除确实非常容易。 与数组不同，在插入或删除元素后，我们不必移动元素。 在链表中，我们只需要更新节点的下一个指针中存在的地址即可。
3.由于链表的大小可以在运行时增加或减小，因此不会浪费内存。 在数组的情况下，会浪费大量内存，例如，如果我们声明一个大小为10的数组并在其中仅存储6个元素，那么就会浪费4个元素的空间。 链表中没有这种问题，因为仅在需要时才分配内存。
单链表的缺点：
1.与数组相比，在链表中存储元素需要更多的内存。 因为在链表中，每个节点都包含一个指针，并且它本身需要额外的内存。
2.在链表中很难遍历元素或节点。 我们不能像按下标在数组中那样随机访问任何元素。 例如，如果我们要访问位置n处的节点，则必须遍历它之前的所有节点。 因此，访问节点所需的时间很大。
3.在链表中，反向遍历确实很困难。 在情况下，它双链表比较容易，但是向后指针需要额外的内存，因此浪费了内存。
