一，前言
1.顺序表的问题和思考
问题：
- 中间/头部的插入删除，时间复杂度为O(N)。
- 增容需要申请新空间，拷贝数据，释放旧空间,会有不小的消耗。
- 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
思考：
如何解决以上问题呢？下面给出了链表的结构来看看。
二 ，有关链表的概念，结构和分类
1. 链表的概念和结构
链表是一种物理存储结构上非连续、非顺序的存储构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
1.1 逻辑结构（就是我们想象的，数据元素依次链接）：
1.2 物理结构（实实在在的在内存中真实存储的结构，数据元素不一定是连续存储的）：
1. 每个结点（一块空间）都是随机在内存中动态开辟（malloc)出来的,都有它们的地址（第一个字节的地址），这些地址也是随机的。
2. 每个新结点都包含两个区域——数据域和指针域。数据域存放我们要操作的数据，指针域存放着下一个结点的地址。我们就是通过这个地址和下一个结点建立联系。
3. 最后一个结点的指针域中存放的是NULL。
2. 链表的分类
实际中的链表种类非常多，以下情况组合起来就有8种链表构：
比如：
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构，下面也只对这两种结构进行代码实现：
- 无头单向非循环链表： 结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
- 带头双向循环链表： 结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
三，无头单向非循环链表（单链表）
1.单链表的功能
单链表的功能一般有如下几个：
- 打印数据
- 动态申请新结点
- 尾部插入数据
- 头部插入数据
- 尾部删除数据
- 头部删除数据
- 查找指定数据的位置
- 在pos位置前插入数据
- 删除pos处的数据
2.单链表功能的实现
2.1 定义单链表结构体
注意：结构体中的struct SListNode * next 不能写成struct SListNode next，因为如果这样写就成了结构体无限嵌套了，这是不允许的！但是定义为 struct SListNode * next 可以，因为它只是一个结构体指针变量，并不会嵌套。
typedef int SLTDataType; typedef struct SListNode { SLTDataType data;//要操作的数据 struct SListNode * next;//指向下一个结点的指针 }SLNode;
2.2 打印数据
首先定义一个指针cur指向第一个结点（头指针phead)，使用循环进行遍历，当cur != NULL时，打印数据，再让cur指向下一个结点，直至跳出循环。
代码实现如下：
void SListPrint(SLNode* phead) { SLNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
2.3 动态申请新结点
由于链表在内存中不是一块连续的空间，所以每次进行插入（增加）数据的操作时，都要在内存中创建新结点，即动态开辟（malloc)一块空间。
//这个函数是每次在增加数据时进行调用的 SLNode* BuySListNode(SLTDataType x) { //随机开辟一块空间（结点） SLNode* newnode =(SLNode*)malloc(sizeof(SLNode)); if (newnode == NULL) { printf("malloc fail!\n"); return; } newnode->data = x;//存入要插入的数据 newnode->next = NULL;//把最后一个结点指向空 return newnode; }
2.4 尾部插入数据
时间复杂度是O(N).
尾插分为两种情况：
1.如果链表中没有结点时，直接让新结点指向头指针；
2.链表中至少有一个结点时，需要循环找到链表的尾结点的指针，再链接上新结点。
代码实现如下：
void SListPushBack(SLNode** pphead, SLTDataType x) { SLNode* newnode = BuySListNode(x); //1.如果表中没有一个节点 if (*pphead == NULL) { *pphead = newnode; } else { //2.有两个节点以上，找尾， SLNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } //链接新节点 tail->next = newnode; } }
2.5 头部插入数据
头插，首先在内存中开辟一个结点，把链表内原来第一个结点的地址存入新结点中，使两者建立联系，再把新结点的地址存入头指针即可。
代码实现如下：
void SListPushFront(SLNode** pphead, SLTDataType x) { SLNode* newnode = BuySListNode(x); newnode->next = *pphead; *pphead = newnode; }
2.6 尾部删除数据
时间复杂度是O(N).
尾删分为三种情况：
1.如果链表中没有数据（链表为空），则不需要删除，略作提示终止程序即可；
2.如果表中只有一个结点，直接free释放，再置空即可；
3.如果表中多于一个结点，不能直接循环找到尾结点删除，这样前一个结点会形成野指针，而是要先保存倒数第二个结点的地址，再把尾结点释放置空。
代码实现如下：
void SListPopBack(SLNode** pphead) { //1.链表内无数据 if (*pphead == NULL) { printf("链表为空!\n"); return; } //2.如果只有一个结点 else if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLNode* prev = NULL; SLNode* tail = *pphead; //3.记住前一个位置 while (tail->next != NULL) { prev= tail; tail = tail->next; } free(tail); prev->next = NULL; } }
2.7 头部删除数据
头删，相同的道理，不能直接把第一个结点free释放，这样就找不到后面的数据了，而是先要定义一个指针变量保存第二个结点的地址，再把第一个结点free释放，置空。最后让头指针指向这个变量。
代码实现如下：
void SListPopFront(SLNode** pphead) { SLNode* cur = NULL; cur = (*pphead)->next; free(*pphead); *pphead = cur; }
2.8 查找指定数据的位置
循环遍历链表，查找出指定数字的位置，用指针pos保存，这个函数一般配合下面两个函数一起使用。
代码实现如下：
SLNode* SListFind(SLNode* phead, SLTDataType x) { SLNode* cur = phead; while (cur!=NULL) { if (cur->data == x) { //找到了发回地址 return cur; } cur = cur->next; } //没有找到，返回空 return NULL; }
2.9 在pos位置前插入数据
时间复杂度是O(N).
这个函数包含两种情况：
1.当在第一个结点前插入时（pos指向第一个结点，pos是通过查找函数找到的），相当于头插；
2.当在其余结点前插入时，需要一个变量prev保存pos的前一个结点的地址，再把prev，pos，newnode这三个结点链接起来。
代码实现如下：
void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x) { SLNode* newnode = BuySListNode(x); //当在第一个结点前插入时，相当于头插 if (*pphead == pos) { SListPushFront(pphead, x); } else { SLNode* prev = NULL; SLNode* cur = *pphead; while (cur->next != pos) { cur = cur->next; } prev = cur;//保存到了pos前一个结点的地址 prev->next = newnode; newnode->next = pos; } }
2.10 删除pos处的数据
时间复杂度是O(N).
相同的，这个函数也包含两种情况：
1.当要删除第一个结点时（此时pos指向第一个结点），相当于头删；
2.当pos指向其他位置时，不能直接free释放掉pos，而是要先找到pos前一个结点的位置，把它与pos的后一个结点进行链接，最后free释放掉pos。
代码实现如下：
void SListErase(SLNode** pphead, SLNode* pos) { //当要删除第一个结点时，相当于头删 if (pos == *pphead) { SListPopFront(pphead); } else { SLNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); } }
3.完整代码
SList.h
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode; //尾插 void SListPushBack(SLTNode** pphead, SLTDataType x); //头插 void SListPushFront(SLTNode** pphead, SLTDataType x); //打印数据 void SListPrint(SLTNode* phead); //尾删 void SListPopBack(SLTNode** pphead); //头删 void SListPopFront(SLTNode** pphead); //查找 SLTNode* SListFind(SLTNode* pphead, SLTDataType x); //在pos位置前插入数据 void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); //在pos位置处删除数据 void SListEarse(SLTNode** pphead, SLTNode* pos);
SList.c
#define _CRT_SECURE_NO_WARNINGS #include "SList.h" void SListPrint(SLTNode* phead) { SLTNode* cur =phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); } SLTNode* BuySListNode(SLTDataType x) { //开辟新节点 SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { printf("malloc fail!\n"); return; } newnode->data = x; newnode->next = NULL; } void SListPushBack(SLTNode** pphead, SLTDataType x) { //判断刚开始是否有节点,若没有，则直接开辟 SLTNode* newnode = BuySListNode(x); if (*pphead == NULL) { *pphead = newnode; } else { //若已经存在节点 则找到尾结点，链接新节点 SLTNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } } void SListPushFront(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuySListNode(x); newnode->next = *pphead; *pphead = newnode; } void SListPopFront(SLTNode** pphead) { if (*pphead == NULL) { printf("链表无数据！\n"); } //注意不能直接free，要先记住第二个节点的地址，再释放第一个节点 SLTNode* next = (*pphead)->next; free(*pphead); *pphead = next; } void SListPopBack(SLTNode** pphead) { //1.当链表为空时 if (*pphead == NULL) { printf("链表无数据!\n"); return; } //2.只有一个节点时,直接释放掉，再置空 else if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLTNode* prev = NULL; SLTNode* tail = *pphead; //让prev记住倒数第二个节点，此时tail指向最后一个节点 while (tail->next != NULL) { prev = tail; tail = tail->next; } //释放最后一个空间 free(tail); //这时prev是最后一个节点，要置空，避免野指针 prev->next = NULL; } } SLTNode* SListFind(SLTNode* pphead, SLTDataType x) { SLTNode* cur = pphead; //遍历链表，找数 while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { //要在第一个节点前插入数据时，相当于头插 if (pos == *pphead) { SListPushFront(pphead, x); } else { SLTNode* newnode = BuySListNode(x); SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = newnode; newnode->next = pos; } } void SListEarse(SLTNode** pphead, SLTNode* pos) { //1.当pos为第一个节点时，没有前一个节点，删除时相当于头删 if (pos == *pphead) { SListPopFront(pphead); } else { //2.Pos不是第一个节点，找到pos的前一个位置，再释放空间 SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); } }
test.c
#define _CRT_SECURE_NO_WARNINGS #include "SList.h" //在这里对那些函数接口进行测试，例如： void SListTest() { //定义一个头指针，置空 SLTNode* plist = NULL; //这里传地址的原因是我们要对链表中的数据进行修改， //由于形参是实参的一份临时拷贝，改变形参不影响实参 //所以只有传地址，对内存进行修改 SListPushBack(&plist, 1); SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPrint(plist); //在3前面插入有一个30，先找到3的前一个的位置，再插入 SLTNode* pos = SListFind(plist, 3); if (pos) { SListInsert(&plist,pos，30); } SListPrint(plist); } int main() { SListTest(); return 0; }
四，带头双向循环链表（双链表）
虽然单链表是我们要掌握基础链表之一，但是它并不完美，比如它不能从后往前操作，不容易找到前驱，每次尾插，尾删都要进行遍历，使得时间复杂度为O（N）等，使用起来其实并不是那么方便。
下面介绍的双链表虽然结构更复杂，但是它完美解决了单链表的缺陷，使用起来十分方便，丝滑。
1.单链表与双链表的结构区别
- 双链表的"带头"是指需要在链表的最前端动态申请一个特殊的结点，这第一个结点不存储有效数据，这种结点也称为带哨兵位的头结点。 它的好处是在进行增删查改等操作时，不需要改变传过来的指针了，也就意味着不需要传二级指针了。
而且，与单链表相比，它不仅有存放下一个结点地址的next指针（也可叫后驱指针），还会增加一个前驱指针prev，用来存放上一个节点的地址。这样就使得每个节点都能快速找到自己的前一个结点，也能找到自己的下一个结点。 最终会形成"循环"。
双链表的这两点结构对我们增删查改的实现有极大的方便，使它能够完美解决单链表的缺陷。- 单链表的结构就更简单了，它没有带头，也没有循环，只能从头到尾前一个结点指向后一个结点。
2.双链表的功能
双链表是最优的链表结构，在任何位置插入删除数据时间复杂度都是O(1)。
双链表的功能一般有如下几个：
- 初始化链表
- 打印数据
- 动态申请新结点
- 尾部插入数据
- 头部插入数据
- 尾部删除数据
- 头部删除数据
- 查找指定数据的位置
- 在pos位置前插入数据
- 删除pos处的数据
- 销毁链表
3.双链表功能的实现
3.1 建立双链表
typedef int SLTDataType; typedef struct ListNode { SLTDataType data;//要操作的数据 struct ListNode* next;//后驱指针 struct ListNode* prev;//前驱指针 }ListNode;
3.2 初始化链表
首先要申请一个带哨兵位的头结点，并且让它的前驱和后驱都指向自己。
代码实现如下：
//注意：这个函数并没有进行传参，而是通过返回值的方式 //把申请空间的地址返回。这就避免了使用二级指针。 ListNode* ListInit() { ListNode* phead = BuyListNode(0); phead->next = phead; phead->prev = phead; return phead; }
3.3 动态申请新结点
在初始化链表和插入数据时，都需要在内存中动态申请新结点。
ListNode* BuyListNode(SLTDataType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); if (newnode == NULL) { printf("malloc fail!\n"); return; } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; }
3.4 打印数据
首先定义一个指针cur指向第二个结点（头节点不存放数据），由于是循环链表，所以通过循环，当cur != phead时，打印出数据即可。
代码实现如下：
void ListPrint(ListNode* phead) { ListNode* cur = phead->next; if (cur == phead) { printf("链表为空!\n"); return; } while (cur != phead) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); }
3.5 尾部插入数据
尾插，申请新结点newnode，定义变量tail指向最后一个结点（其实就是phead的前驱，这就避免了要向单链表那样通过遍历找到尾节点，体现出了双链表的优越性。），再链接起phead，newnode，tail
代码实现如下：
void ListPushBcck(ListNode* phead, SLTDataType x) { assert(phead);//断言 ListNode* newnode = BuyListNode(x); ListNode* tail = phead->prev; tail->next = newnode; newnode->prev = tail; phead->prev = newnode; newnode->next = phead； }
3.6 头部插入数据
头插，就是在头结点phead和和第二个结点之间插入，申请新结点newnode，再定义变量first指向第二个结点，再链接起三者即可。
代码实现如下：
void ListPushFront(ListNode* phead, SLTDataType x) { assert(phead); ListNode* first = phead->next; ListNode* newnode = BuyListNode(x); phead->next = newnode; newnode->prev = phead; newnode->next = first; first->prev = newnode; }
3.7 尾部删除数据
尾删，与单链表类似，不能直接把最后一个结点free释放。定义一个变量tail指向尾结点（其实就是phead->prev)，再定义一个变量prev保存倒数第二个结点的地址（其实就是tail->prev)，再进行三者链接，最后释放，置空。
代码实现如下：
void ListPopBcck(ListNode* phead) { assert(phead); //不能把哨兵位节点销毁 assert(phead->next != phead); ListNode* tail = phead->prev; ListNode* prev = tail->prev; phead->prev = prev; prev->next = phead; free(tail); tail = NULL; }
3.8 头部删除数据
头删，是删除第二个结点，不能直接释放第二个结点。定义变量first指向第二个结点（就是phead->next)，再定义变量second指向第三个结点（就是first->next)，再进行三者链接，最后释放，置空。
代码实现如下：
void ListPopFront(ListNode* phead) { assert(phead); ListNode* first = phead->next; ListNode* second = first->next; phead->next = second; second->prev = phead; free(first); first = NULL; }
3.9 查找指定数据的位置
定义变量cur指向第二个结点，直接循环遍历，直至cur指向phead。若找到了，则直接返回该结点的地址，用pos接收，否则返回NULL。这个函数一般与下面两个函数配合使用。
ListNode* ListFind(ListNode* phead, SLTDataType x) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
3.10 在pos位置前插入数据
pos是查找函数找到的位置，申请新结点newnode，定义变量prev指向pos的前一个结点，再链接三者即可。
代码实现如下：
void ListInsert(ListNode* pos, SLTDataType x) { assert(pos);//断言，pos不能为空 ListNode* prev = pos->prev; ListNode* newnode = BuyListNode(x); prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; }
3.11 删除pos处的数据
与前面类似，不能直接free释放pos处的空间。定义变量prev指向（保存）pos前一个结点的（地址），定义变量next指向（保存）pos后一个结点（地址），再把两者进行链接，最后释放，置空。
代码实现如下：
void ListEarse(ListNode* pos) { assert(pos); ListNode* prev = pos->prev; ListNode* next = pos->next; prev->next = next; next->prev = prev; free(pos);//释放 pos = NULL; }
3.12 销毁链表
销毁链表是从第二个结点开始，循环依次释放。定义变量cur指向第二个结点，与前面类似，不能直接释放cur处的空间，而是要先保存到下一个结点的空间，再把当前节点空间释放。最后再释放头结点（phead)，置空。
代码实现如下：
void ListDestory(ListNode* phead) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { ListNode* next = cur->next;//保存下一个结点的地址 free(cur);//先释放有数据的结点 cur = next; } free(phead);//释放哨兵位头结点 phead = NULL; }
4. 完整代码
List.h
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int SLTDataType; typedef struct ListNode { SLTDataType data; struct ListNode* next; struct ListNode* prev; }ListNode; //初始化链表 ListNode* ListInit(); //销毁链表 void ListDestory(ListNode* phead); //打印数据 void ListPrint(ListNode* phead); //尾插 void ListPushBcck(ListNode* phead, SLTDataType x); //头插 void ListPushFront(ListNode* phead, SLTDataType x); //尾删 void ListPopBcck(ListNode* phead); //头删 void ListPopFront(ListNode* phead); //查找 ListNode* ListFind(ListNode* phead, SLTDataType x); //在pos前插入数据 void ListInsert( ListNode* pos, SLTDataType x); //删除pos处的数据 void ListEarse( ListNode* pos);
List.c
#define _CRT_SECURE_NO_WARNINGS #include "List.h" ListNode* BuyListNode(SLTDataType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); if (newnode == NULL) { printf("malloc fail!\n"); return; } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } ListNode* ListInit() { ListNode* phead = BuyListNode(0); phead->next = phead; phead->prev = phead; return phead; } void ListPrint(ListNode* phead) { ListNode* cur = phead->next; if (cur == phead) { printf("链表为空!\n"); return; } while (cur != phead) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); } void ListDestory(ListNode* phead) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { ListNode* next = cur->next; free(cur); cur = next; } free(phead); phead = NULL; } void ListPushBcck(ListNode* phead, SLTDataType x) { assert(phead); ListNode* newnode = BuyListNode(x); ListNode* tail = phead->prev; tail->next = newnode; newnode->prev = tail; phead->prev = newnode; newnode->next = phead; } void ListPushFront(ListNode* phead, SLTDataType x) { assert(phead); ListNode* first = phead->next; ListNode* newnode = BuyListNode(x); phead->next = newnode; newnode->prev = phead; newnode->next = first; first->prev = newnode; } void ListPopFront(ListNode* phead) { assert(phead); ListNode* first = phead->next; ListNode* second = first->next; phead->next = second; second->prev = phead; free(first); first = NULL; } void ListPopBcck(ListNode* phead) { assert(phead); //不能把哨兵位节点销毁 assert(phead->next != phead); ListNode* tail = phead->prev; ListNode* prev = tail->prev; phead->prev = prev; prev->next = phead; free(tail); tail = NULL; } ListNode* ListFind(ListNode* phead, SLTDataType x) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } void ListInsert(ListNode* pos, SLTDataType x) { assert(pos); ListNode* prev = pos->prev; ListNode* newnode = BuyListNode(x); prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; } void ListEarse(ListNode* pos) { assert(pos); ListNode* prev = pos->prev; ListNode* next = pos->next; prev->next = next; next->prev = prev; free(pos); pos = NULL; }
test.c
#define _CRT_SECURE_NO_WARNINGS #include "List.h" //在这个函数中进行各函数接口的测试： ListNode* ListTest() { ListNode* plist = ListInit(); ListPushBcck(plist, 1); ListPushBcck(plist, 2); ListPushBcck(plist, 3); ListPushBcck(plist, 4); ListPrint(plist); ListDestory(plist); return 0; } int main() { ListTest(); return; }
