在学习链表之前，我们先说说之前学的顺序表，在前面的章节中，我们说，顺序表实际上是对数组的操纵，它的内存空间是连续的，可以通过数组下标随机访问，但是链表就不行，这是顺序表的优点，那它有没有缺点呢？
答案是有的。
顺序表的问题：
1. 中间/头部的插入删除，时间复杂度是O(N)。
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容 到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
如何解决上述问题呢?下面我们来学习链表。
1. 链表
1.1 链表的概念和结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
顺序表的问题本质就在于，它是一块连续的物理空间，而链表就不一样了。链表在内存中申请的是一块一块的内存空间，相互之间通过节点联系在一起。
开始时给一个指针指向第一个空间，然后通过节点找到第二个，第二个找到第三个........最后一个节点指向空（NULL）
如下图：
现在我们首先来定义一个结构体：
typedef int SLDataType; typedef struct SListNode { SLDataType data; struct SListNode* next; }SLTNode;
结构体中有一个数据data，还有一个结构体指针next。
下面我们简单来遍历打印一个链表：
void SLDPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
上述代码中，把头节点赋给cur，cur->data是结构体中的数据，代码中的cur=cur->next刚开始可能有点难以理解，实际上cur->next访问的是存放在结构体中的下一个结构体的地址，->相当于对其进行解引用，这样cur就可以找到下一个节点，然后打印下一个结构体的数据，直到最后一个节点的cur->next指向空指针（NULL）。
上图其实就是链表的逻辑结构，这是为了方便形象理解，想象出来的。实际上链表在内存中是下面的物理结构：
实际的物理结构，变量phead中存放的是第1个节点的地址，第1个节点的结构体中存放的是第2个节点的地址， 2中存放3节点的地址，3中存放4节点的地址.......直到最后的节点中存放的是空。
这样上述代码中的cur = cur->next就更好理解了，它实际上相当把next中的地址拷贝到cur中去，然后cur就指向了下一个节点。
1.2 链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
1. 单向或者双向：
2. 带头或者不带头
3. 循环或者非循环
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
2. 单链表的实现：
单链表头插数据：
头插数据只需要使新开辟出来的newnode节点下一个指向的是头节点phead，然后把头节点指向在newnode的地方。
下面我们来看看下面代码实现：
//单链表头插数据 void SLPushFront(SLTNode* phead, SLDataType x) { //动态内存开辟 SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc"); return; } newnode->data = x; newnode->next = NULL; //头插 newnode->next = phead; phead = newnode; }
问题来了，上述代码正确吗？
看起来逻辑十分严密是吧，但是我们测试运行一下就会发现，什么都没有打印出来：
这又是为什么呢？
因为我们在头插的时候改变的是指针，例如：newnode->next = phead; phead = newnode;改变指针实际上就是，把指针的值拷贝过去，当我们传plist，并用phead接收时，实际上就是phead把plist的值拷贝过去，但是后面phead = newnode，又把newnode的值拷贝过去了，原有的值被覆盖了，plist和phead建立不上联系。
那该怎么办呢？
很简单，既然我们要改变指针，那就传指针的地址，用二级指针接收，使用时解引用就行。通过*phead=newnode可以使newnode和plist直接建立联系。
代码修改如下：
//单链表头插数据 void SLPushFront(SLTNode** phead, SLDataType x) { //动态内存开辟 SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc"); return; } newnode->data = x; newnode->next = NULL; newnode->next = *phead; *phead = newnode; }
测试：
单链表尾插数据
尾插数据，因为链表不是连续物理空间，所以我们要先找到链表的尾，然后再指向新开辟的节点newnode，并把newnode->next置为NULL。
同理，尾部插入也需要使用二级指针，如果不使用二级指针，在phead=newnode这条语句中，因为此时的newnode和phead是局部变量，出了作用域就销毁了，所以phead和plist建立不上联系。而如果我们用二级指针，*phead=newnode，相当于把newnode的值直接给plist，尽管phead和newnode后面还会销毁，但是新节点和plist的联系已经建立起来了。
不论是头插还是尾插数据，都要开辟新空间，所以我们可以将其封装为一个函数：
//动态内存开辟 SLTNode*CheckSList(SLDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc"); return; } newnode->data = x; newnode->next = NULL; return newnode; }
尾插数据代码：
//单链表尾插数据 void SLPushBack(SLTNode** phead, SLDataType x) { SLTNode* newnode = CheckSList(x); //1.空链表 //2.非空链表 if (*phead == NULL) { *phead = newnode; } else { SLTNode* tail = *phead; //找到尾 while (tail->next != NULL) { tail = tail->next; } //尾插 tail->next = newnode; } }
注意：要判断链表是不是空链表。
测试：
单链表头删数据：
要想头删数据，只需要将头节点指向第二个节点，并将头节点free掉，置为NULL。
注意：分三种情况，无节点，一个节点和多个节点。实现的方式不同，需要判断。
//单链表头删数据 void SLPopFront(SLTNode** phead) { assert(*phead); //一个节点 //多个节点 if ((*phead)->next == NULL) { free(*phead); *phead = NULL; } else { SLTNode* start = *phead; *phead = start->next; free(start); start = NULL; } }
测试：
单链表尾删数据：
要想尾删数据，可以先找到倒数第二个节点，把它后面的节点free掉，并置为NULL即可。
注意：分三种情况，无节点，一个节点和多个节点。实现的方式不同，需要判断。
代码如下：
//单链表尾删数据 void SLP0pBack(SLTNode** phead) { assert(*phead); //一个节点 //多个节点 if ((*phead)->next == NULL) { free(*phead); *phead = NULL; } else { SLTNode* tail = *phead; //找到倒数第二个节点 while (tail->next->next != NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
测试：
单链表查找并修改数据：
查找数据很简单，直接把链表遍历一遍就行。而查找和修改可以同时实现。
直接上代码：
//单链表查找数据 SLTNode* SLFind(SLTNode* phead, SLDataType x) { assert(phead); SLTNode* cur = phead; int count = 0; while (cur != NULL) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
上述代码可以同时实现查找和修改，查找到数据后，返回节点指针，通过指针修改结构体数据：
SLTNode* pos = SLFind(plist,2); if (pos != NULL) pos->data = 30;
测试：
在上文中，我们发现有些参数传的是一级指针，有些传的是二级指针，为什么呢？
其实给打印和查找函数传的就是一级指针，而其他的头插、尾插、头删、尾删都是二级指针，原因很明显，打印和查找函数不需要改变指针，而其他的需要改变指针，要改变指针就要使用二级指针。
下面我们再来补充一个内容，
什么时候需要断言？
比如：查找函数需要断言assert(phead)吗？
不需要，因为即使phead传过来的是空链表，查找函数也可以找，找不到就返回NULL。同理，打印函数也不需要断言，它可以打印空链表NULL。
头插函数中需要断言assert(phead)吗？
需要，因为phead是头指针plist的地址，永远都不能为空，一旦为空，再对其解引用就成空指针NULL了。
头插函数中需要断言assert(*phead)吗？
不需要，因为它即使为空，空链表也可以插入数据啊。
头插函数断言如下：
//单链表头插数据 void SLPushFront(SLTNode** phead, SLDataType x) { assert(phead);//链表为空，phead也不为空，因为它是头指针plist的地址 //assert(*phead);不需要断言，链表为空，也需要能插入 SLTNode*newnode=CheckSList(x); newnode->next = *phead; *phead = newnode; }
头删函数中需要断言assert(phead)和assert(*phead)吗？
都需要，头删函数中，一旦链表为空就不能再删了，所以需要断言assert(*phead)，而断言assert(phead)的原因和上文一致。
头删函数断言如下：
//单链表头删数据 void SLPopFront(SLTNode** phead) { assert(phead);//链表为空，phead也不为空，因为它是头指针plist的地址 assert(*phead);//链表为空，不能再删。 //一个节点 //多个节点 if ((*phead)->next == NULL) { free(*phead); *phead = NULL; } else { SLTNode* start = *phead; *phead = start->next; free(start); start = NULL; } }
同理，尾删和头删保持一致，尾插和头插保持一致。
下面我们接着讲链表任意位置的插入和删除：
单链表在pos之前插入数据：
要想在pos之前插入数据，就要先找到pos前一个节点，然后把使该节点下一个指向newnode，让newnode的下个节点指向pos。
代码如下：
//单链表在pos之前插入数据 void SLInsert(SLTNode** phead, SLTNode* pos, SLDataType x) { assert(phead); assert(pos); if (*phead == pos) { SLPushFront(phead, x); } else { SLTNode* newnode = CheckSList(x); SLTNode* cur = *phead; while (cur->next != pos) { cur = cur->next; } cur->next = newnode; newnode->next = pos; } }
注意：上述代码中复用了头插函数，因为当pos在头节点的位置时，while循环就找不到pos的前一个节点了，所以这种情况需要单独判断，当pos在头节点位置时，直接使用头插。
测试：先用查找函数找到pos，然后在pos前面插入数据：
单链表在pos之后插入数据：
在pos之后插入数据很简单，直接插入就行。
上代码：
//单链表在pos后插入数据 void SLErase(SLTNode** phead, SLTNode* pos, SLDataType x) { assert(phead); SLTNode* newnode = CheckSList(x); SLTNode* next = pos->next; pos->next = newnode; newnode->next = next; }
测试：也是先用查找函数找到pos，然后在pos后面插入数据：
单链表在pos位置删除数据：
经过上文的练习，这个应该很简单吧。直接找到pos前一个节点，让它指向pos下一个节点，然后将pos节点free就行。
上代码：
//单链表在pos位置删除数据 void SLPErase(SLTNode** phead, SLTNode* pos) { assert(phead); assert(*phead); if (*phead == pos) { SLPopFront(phead); } else { SLTNode* prev =*phead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); } }
测试：
至于在pos之前和之后删除数据，和前面的思路一样，不再赘述。
3.完整代码：
test.c:
仅供测试用例。
#define _CRT_SECURE_NO_WARNINGS 1 #include"SList.h" //测试函数 void test1() { SLTNode* plist = NULL; SLPushFront(&plist, 1); SLPushFront(&plist, 2); SLPushFront(&plist, 3); SLPushFront(&plist, 4); SLTNode* pos = SLFind(plist, 2); if (pos != NULL) SLPErase(&plist, pos); /*SLPushBack(&plist, 5); SLPushBack(&plist, 6); SLPushBack(&plist, 7);*/ /*SLTNode* pos = SLFind(plist,2); if (pos != NULL) pos->data = 30;*/ /*SLPopFront(&plist); SLPopFront(&plist); SLPopFront(&plist);*/ SLPrint(plist); } int main() { test1(); return 0; }
SList.h:
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> //定义结构体 typedef int SLDataType; typedef struct SListNode { SLDataType data; struct SListNode* next; }SLTNode; //打印函数 void SLPrint(SLTNode*phead); //单链表头插数据 void SLPushFront(SLTNode** phead, SLDataType x); //单链表尾插数据 void SLPushBack(SLTNode** phead, SLDataType x); //单链表头删数据 void SLPopFront(SLTNode** phead); //单链表尾删数据 void SLP0pBack(SLTNode** phead); //单链表查找数据 SLTNode* SLFind(SLTNode* phead, SLDataType x); //单链表在pos之前插入数据 void SLInsert(SLTNode** phead, SLTNode* pos, SLDataType x); //单链表在pos之后插入数据 void SLErase(SLTNode** phead, SLTNode* pos, SLDataType x); //单链表在pos位置删除数据 void SLPErase(SLTNode** phead, SLTNode* pos);
SList.c:
#define _CRT_SECURE_NO_WARNINGS 1 #include"SList.h" void SLPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); } //动态内存开辟 SLTNode*CheckSList(SLDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc"); return NULL; } newnode->data = x; newnode->next = NULL; return newnode; } //链表头插数据 void SLPushFront(SLTNode** phead, SLDataType x) { assert(phead);//链表为空，phead也不为空，因为它是头指针plist的地址 //assert(*phead);不需要断言，链表为空，也需要能插入 SLTNode*newnode=CheckSList(x); newnode->next = *phead; *phead = newnode; } //链表尾插数据 void SLPushBack(SLTNode** phead, SLDataType x) { assert(phead);//链表为空，phead也不为空，因为它是头指针plist的地址 //assert(*phead);不需要断言，链表为空，也需要能插入 SLTNode* newnode = CheckSList(x); //1.空链表 //2.非空链表 if (*phead == NULL) { *phead = newnode; } else { SLTNode* tail = *phead; //找到尾 while (tail->next != NULL) { tail = tail->next; } //尾插 tail->next = newnode; } } //链表头删数据 void SLPopFront(SLTNode** phead) { assert(phead);//链表为空，phead也不为空，因为它是头指针plist的地址 assert(*phead);//链表为空，不能再删。 //一个节点 //多个节点 if ((*phead)->next == NULL) { free(*phead); *phead = NULL; } else { SLTNode* start = *phead; *phead = start->next; free(start); start = NULL; } } //链表尾删数据 void SLP0pBack(SLTNode** phead) { assert(phead);//链表为空，phead也不为空，因为它是头指针plist的地址 assert(*phead);//链表为空，不能再删。 //一个节点 //多个节点 if ((*phead)->next == NULL) { free(*phead); *phead = NULL; } else { SLTNode* tail = *phead; //找到倒数第二个节点 while (tail->next->next != NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; } } //链表查找数据 SLTNode* SLFind(SLTNode* phead, SLDataType x) { assert(phead); SLTNode* cur = phead; int count = 0; while (cur != NULL) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } //单链表在pos之前插入数据 void SLInsert(SLTNode** phead, SLTNode* pos, SLDataType x) { assert(phead); assert(pos); if (*phead == pos) { SLPushFront(phead, x); } else { SLTNode* newnode = CheckSList(x); SLTNode* cur = *phead; while (cur->next != pos) { cur = cur->next; } cur->next = newnode; newnode->next = pos; } } //单链表在pos后插入数据 void SLErase(SLTNode** phead, SLTNode* pos, SLDataType x) { assert(phead); SLTNode* newnode = CheckSList(x); SLTNode* next = pos->next; pos->next = newnode; newnode->next=next; } //单链表在pos位置删除数据 void SLPErase(SLTNode** phead, SLTNode* pos) { assert(phead); assert(*phead); if (*phead == pos) { SLPopFront(phead); } else { SLTNode* prev =*phead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); } }
以上就是今天学习的关于单链表的所有内容。
未完待续。。。
