《数据结构》宗师级大记忆恢复术 —— 链表
目录
一. 单链表的定义
单链表，本质就是线性表的链式存储结构形式。
它的实现逻辑是，通过一组任意的存储单元来存储线性表中的数据元素。
为建立数据元素之间的关系，对于每个结点内，除了要存放自身元素信息之外，还要存放一个指向其后继的指针。单链表结点结构图示如下：
其中data为数据域，用于存放数据元素；next为指针域，用于存放后继结点的地址。
单链表中的结点声明如下：
typedef struct LNode { //定义单链表结点类型 ElemType data; //数据域 struct LNode* next; //指针域 }LNode, *LinkList; 注意：代码使用 LNode * 时，强调这是一个结点；代码使用 LinkList 时，强调这是一个单链表。
单链表的元素并非连续存放在存储空间中，而是离散分布，所以其存储结构是顺序存取而非随机存取。所以在查找特定元素时，需要从表头开始遍历，依次查找，也是非常墨迹啊。
头节点和头指针的关系：无论是否有头节点，头指针始终指向链表的第一个结点，而头结点是带头链表 的第一个结点，该结点内通常不存储信息。
引入头结点的优点：
①第一个数据结点的位置存放于头结点中，因此在链表中的第一个位置上的操作与在链表中其他位置的操作一致。
②不管链表是空的还是有数据，头指针都固定指向头结点，空表只是头结点的指针域为空而已，这样空表和非空表的处理逻辑也能统一，不用分开写判断逻辑。
二. 单链表的基本操作
1. 单链表的初始化
这是带头结点的单链表初始化函数，先申请一块内存当这个头结点，再把它的 next 指针设成空，代表现在链表还没存任何有效数据，最后返回初始化成功的结果。
bool InitList(LinkList& L) //带头结点的单链表初始化 { L = (LNode*)malloc(sizeof(LNode)); //创建头结点 L->next = NULL; //头结点之后暂时没有元素节点 return true; }这是不带头结点的单链表初始化，逻辑更简单，直接把链表的头指针设成 NULL，就代表这个链表现在是空的，初始化就完成了，最后返回成功的状态。
bool InitList(LinkList& L) { L = NULL; return true; }2. 单链表判空
这是带头结点单链表的判空函数，给它传链表的头指针，它就帮你检查这个链表有没有存有效数据的节点，要是链表啥数据都没有，就返回 true，有数据的话就返回 false。
bool Empty(LinkList L) { if (L->next == NULL) //如果L->next为NULL，说明链表没有任何有效数据节点，是空链表 return true; else return false; }3. 求表长的操作
这函数是用来算链表长度的，也就是数链表里有多少个存数据的节点。它会顺着链表一个一个往下走，每数到一个节点就给计数器加 1，直到走到链表的末尾，最后把数出来的总个数返回给你。
int Length(LinkList L) { int len = 0; //定义计数器len，初始值为0，用来统计数据节点的个数 LNode* p = L; //定义遍历用的指针p，初始指向链表的头结点 while (p->next != NULL) //只要当前节点的下一个节点不为空，说明还有未统计的数据节点，继续遍历 { p = p->next; //指针向后移动，走到下一个数据节点 len++; //每遍历到一个数据节点，计数器加1 } return len; //遍历结束，返回统计好的链表长度 }4. 按序号查找结点
这是按序号找节点的函数，给他要查的链表、还有要找的是第几个节点，它就顺着链表挨个往下找，找到对应节点就把这个节点的地址返回给你；要是你给的序号不对、或者链表没这么长，就返回 NULL，告诉你没找到对应的节点。
LNode* GetElem(LinkList L, int i) { LNode* p = L; //定义遍历用的指针p，初始指向链表的头结点 int j = 0; //定义计数器j，记录当前指针指向的节点序号，初始值0对应头结点 while (p != NULL && j < i) //只要指针没走到链表末尾，且还没到达目标序号i，就继续遍历查找 { p = p->next; //指针向后移动，走到下一个节点 j++; //计数器加1，更新当前节点的序号 } return p; //遍历结束，返回找到的节点地址（没找到对应节点则返回NULL） }5. 按值查找表结点
这是按值找节点的函数，给它要查的链表、还有要找的目标数值，它就顺着链表挨个节点看，找到第一个存了这个数值的节点，就把节点的地址返回给你；要是整个链表都找完了都没这个数，就返回 NULL，告诉你查找失败了。
LNode* LocateElem(LinkList L, ElemType e) { LNode* p = L->next; //定义遍历用的指针p，初始指向第一个数据节点（跳过不存数据的头结点） while (p != NULL && p->data != e) //只要指针没走到链表末尾，且当前节点的数据不等于目标值e，就继续向后查找 p = p->next; //指针向后移动，检查下一个节点 return p; //遍历结束，返回找到的匹配节点地址（没找到对应节点则返回NULL） }6. 插入结点操作（指定位置）
这是带头结点链表的按位置插入函数，给它要操作的链表、要在第几个位置插、还有要插入的数，它会先检查你给的位置是否合法，然后找到要插的位置的前一个节点，把新节点插进去，插成功了就返回 true，位置不对就返回 false。
bool ListInsert(LinkList& L, int i, ElemType e) { if (i < 1) //检查位序合法性 return false; LNode* p = L; //定义遍历指针p，初始指向链表的头结点 int j = 0; //定义计数器j，记录当前p指向的节点序号，初始0对应头结点 while (p != NULL && j < i - 1) //循环找到第i-1个前驱节点：只要p不为空，且还没到第i-1个节点，就继续遍历 { p = p->next; //指针向后移动，走到下一个节点 j++; //计数器加1，更新当前节点的序号 } if (p == NULL) //如果p为空，说明i超过了链表的长度，位置不合法，返回false return false; LNode* s = (LNode*)malloc(sizeof(LNode)); //申请内存，创建一个新的节点s s->data = e; //给新节点的data域赋值，存入要插入的元素e s->next = p->next; //新节点的next指向p原来的下一个节点，把链表后续的节点接在新节点后面 p->next = s; //p的next指向新节点，把新节点接在p的后面，完成插入 return true; //插入成功，返回true }这是不带头结点链表的按位置插入函数，和带头的不一样，插第一个位置的时候要单独处理，因为要修改链表的头指针；其他位置的话，也是先找到要插的位置的前一个节点，再把新节点插进去，插成功了返回 true，位置不合法就返回 false。
bool ListInsert(LinkList& L, int i, ElemType e) { if (i == 1) //单独处理插入第1个位置的情况（不带头结点的链表，插第一个位置要修改头指针） { LNode* s = (LNode*)malloc(sizeof(LNode)); //申请内存，创建新节点s s->data = e; //给新节点赋值元素e s->next = L; //新节点的next指向原来的头节点，把原来的链表接在新节点后面 L = s; //头指针L指向新节点，新节点成为新的头节点 return true; } int j = 1; //处理插入位置不是第1位的情况：定义计数器j，初始1对应第一个节点的序号 LNode* p = L; //定义遍历指针p，初始指向链表的第一个节点（头指针L） while (p != NULL && j < i - 1) //循环找到第i-1个前驱节点：只要p不为空，且还没到第i-1个节点，就继续遍历 { p = p->next; //指针向后移动，走到下一个节点 j++; //计数器加1，更新当前节点的序号 } if (p == NULL) //如果p为空，说明i超过了链表的长度，位置不合法，返回false return false; LNode* s = (LNode*)malloc(sizeof(LNode)); //申请内存，创建新节点s s->data = e; //给新节点赋值元素e s->next = p->next; //新节点的next指向p原来的下一个节点，接好后续链表 p->next = s; //p的next指向新节点，完成插入 return true; }7. 插入结点操作（指定结点）
这是给已知节点前插元素的函数，传入已知的节点指针 p，有要插入的数 e，它就能直接在 p 的前面插入新节点，不用从头遍历链表。操作成功就返回 true，要是你给的 p 是空的，就返回 false。
bool InsertPriorNode(LNode* p, ElemType e) { if (p == NULL) //如果节点p为空，位置不合法，直接返回false return false; LNode* s = (LNode*)malloc(sizeof(LNode)); //申请内存，创建新节点s s->next = p->next; //新节点的next指向p的下一个节点，把新节点插在p的后面 p->next = s; s->data = p->data; //把p原来的数据复制到新节点s里 p->data = e; //把要插入的元素e存入p节点，相当于p变成了新插入的节点，s变成了原来的p节点，实现前插效果 return true; }这是给已知节点后插元素的函数，传入已知节点的指针 p、要插入的元素 e，函数会在节点 p 的后面插入新元素 e。不用从头遍历链表，直接修改节点的指针即可完成插入，操作成功返回 true，若节点 p 为空则返回 false。
bool InsertNextNode(LNode* p, ElemType e) { if (p == NULL) //如果传入的节点p为空，位置不合法，直接返回false，终止操作 return false; LNode* s = (LNode*)malloc(sizeof(LNode)); //申请内存，创建一个新的节点s，用来存放要插入的元素 s->data = e; //给新节点的data域赋值，存入要插入的元素e s->next = p->next; //新节点s的next指向p原来的下一个节点，把p后续的链表接在新节点后面 p->next = s; //把p的next指向新节点s，将新节点接在p的后面，完成后插操作 return true; }8. 删除结点操作
入链表头指针 L、要删除的位置 i、用来接收被删除元素的变量 e，函数会检查删除位置的合法性，找到第 i-1 个前驱节点，删除第 i 个节点并释放内存，删除成功返回 true，位置不合法返回 false。
bool ListDelete(LinkList& L , int i, ElemType& e) { LNode* p = L; //定义遍历指针p，初始指向链表的头结点 int j = 0; //定义计数器j，记录当前p指向的节点序号，初始0对应头结点 while (p->next != NULL && j < i - 1) //循环找到第i-1个前驱节点：只要p的下一个节点不为空，且还没到第i-1个节点，就继续遍历 { p = p->next; //指针向后移动，走到下一个节点 j++; //计数器加1，更新当前节点的序号 } if (p->next == NULL || j > i - 1) //校验位置合法性：如果p的下一个节点为空（要删除的节点不存在），或者j超过了i-1（位置非法），返回false return false; LNode* q = p->next; //用指针q指向要删除的第i个节点（p的下一个节点） e = q->data; //把被删除节点的元素值赋值给e，带出去给调用者 p->next = q->next; //把p的next指向q的下一个节点，跳过要删除的节点，把链表接好 free(q); //释放q节点的内存，避免内存泄漏 return true; }9. 采用头插法建立单链表
传入链表头指针 L，函数会初始化带头结点的空链表，循环读取用户输入的整数，每读一个数就把它作为新节点插到链表头结点的后，直到输入 9999 停止，最终返回建立好的链表头指针。
LinkList List_HeadInsert(LinkList& L) { LNode* s; //定义新节点指针s，和用来接收用户输入的变量x int x; L = (LNode*)malloc(sizeof(LNode)); //申请内存，创建链表的头结点 L->next == NULL; //头结点的next置为NULL，初始化空链表 scanf("%d", &x); //读取用户输入的第一个整数，存入x while (x != 9999) //循环：只要输入的x不是9999，就继续插入节点 { s = (LNode*)malloc(sizeof(LNode)); //申请内存，创建新节点s s->data = x; //给新节点赋值，存入用户输入的x s->next = L->next; //新节点的next指向头结点原来的下一个节点，接好链表的后续部分 L->next = s; //头结点的next指向新节点，把新节点插到链表头部 scanf("%d", &x); //读取下一个用户输入的整数，继续循环 } return L; }10. 采用尾插法建立单链表
传入链表头指针 L，函数会初始化带头结点的空链表，用尾指针 r 记录链表的最后一个节点，循环读取用户输入的整数，每读一个数就把它作为新节点插到链表的尾部，直到输入 9999 停止，最终返回建立好的链表头指针。
LinkList List_TailInsert(LinkList& L) { int x; //定义用来接收用户输入的变量x L = (LNode*)malloc(sizeof(LNode)); //申请内存，创建链表的头结点 LNode* s, * r = L; //定义新节点指针s，和尾指针r，初始r指向头结点（空链表的尾部就是头结点） scanf("%d", &x); //读取用户输入的第一个整数，存入x while (x != 9999) //循环：只要输入的x不是9999，就继续插入节点 { s = (LNode*)malloc(sizeof(LNode)); //申请内存，创建新节点s s->data = x; //给新节点赋值，存入用户输入的x r->next = s; //尾指针r的next指向新节点，把新节点接到链表的尾部 r = s; //尾指针r移动到新节点，更新为新的链表尾部 scanf("%d", &x); //读取下一个用户输入的整数，继续循环 } r->next = NULL; //循环结束，把链表最后一个节点的next置为NULL，标记链表结束 return L; //链表建立完成，返回链表的头指针 }三. 双链表的定义
单链表中只有一个指向后继结点的指针，这导致其在执行查找、插入和删除等操作的时候只能从头开始遍历，时间复杂度为 O (n) 。所以双链表的产生就是为了解决这种问题，其拥有prior指针和next指针，分别指向其直接前驱和直接后继。双链表结点结构图示如下：
单链表中的结点声明如下：
typedef struct DNode { //定义双链表结点类型 ElemType data; //数据域 struct DNode* prior, * next; //前驱指针和后驱指针 }DNode, *DLinklist; 注意：代码使用 DNode * 时，强调这是一个结点；代码使用 DLinkList 时，强调这是一个双链表。
双链表的按值查找和按位查找时间复杂度与单链表持同，因为其都为顺序存取结构；但是其插入与操作快于单链表，因为双链表拥有前驱指针，可以很容易地找到前一结点，时间复杂度为 O(1) 。
四. 双链表的基本操作
1. 双链表的初始化
这是带头结点的双链表初始化函数，说白了就是给双链表建一个头结点，先申请一块内存当这个头结点，要是内存申请失败就返回 false；申请成功的话，就把头结点的前驱指针 prior 和后继指针 next 都设成 NULL，代表现在链表是空的，最后返回初始化成功的 true。
bool InitDLinklist(DLinklist& L) { L = (DNode*)malloc(sizeof(DNode)); //申请一块内存，大小是一个DNode节点的大小，把申请到的地址赋值给头指针L，也就是创建头结点 if (L == NULL) //如果L是NULL，说明刚才申请内存失败了，直接返回false return false; L->prior = NULL; //把头结点的前驱指针prior设为NULL，头结点前面没有节点 L->next = NULL; //把头结点的后继指针next设为NULL，头结点后面也没有节点，现在链表是空的 return true; }
2. 双链表的插入
这是双链表的节点后插函数，给它一个已知的节点 p，还有要插入的新节点 s，它就能把 s 插到 p 的后面。因为双链表有前后两个指针，所以要把新节点和前后的节点的指针都接好，要是 p 或者 s 是空的，就直接返回 false，操作成功就返回 true。
bool InsertNextDNode(DNode* p, DNode* s) { if (p == NULL || s == NULL) //如果p是空的，或者s是空的，位置不合法，直接返回false return false; s->next = p->next; //让新节点s的后继指针，指向p原来的下一个节点，先把p后面的链表接在s的后面 if (p->next != NULL) //如果p原来的下一个节点不是空的 p->next->prior = s; //让p原来的后继节点的前驱指针，指向新节点s，把后面节点的前向指针接好 s->prior = p; //让新节点s的前驱指针，指向节点p，把s和p的前向关系接好 p->next = s; //让p的后继指针，指向新节点s，把p和s的后向关系接好，完成插入 return true; }3. 双链表的删除
这是双链表的节点删除函数，作用是删掉节点 p 后面的那个节点。它会先检查 p 是不是空的，还有 p 后面有没有节点可以删，要是没的删就返回 false；有的话就把链表的前后指针重新接好，跳过要删的节点，再释放掉这个节点的内存，避免内存泄漏，删成功了就返回 true。
bool DeleteNextNode(DNode* p) { if (p == NULL) //如果p是空的，位置不合法，直接返回false return false; DNode* q = p->next; //用指针q指向p的后继节点，也就是我们要删掉的节点 if (q == NULL) //如果q是空的，说明p后面没有节点，没的可删，返回false return false; p->next = q->next; //让p的后继指针，直接指向q的下一个节点，跳过要删的q节点，把链表的后向接好 if (q->next != NULL) //如果q的下一个节点不是空的（也就是q不是链表最后一个节点） q->next->prior = p; //让q的后继节点的前驱指针，指向p，把链表的前向接好 free(q); //释放掉q节点的内存，把要删的节点彻底清掉，避免内存泄漏 return true; }4. 双链表的销毁
这是销毁整个双链表的函数，说白了就是把整个链表的所有节点都删掉，释放所有占用的内存，避免内存泄漏。它会循环调用刚才的删除函数，一直删掉头结点后面的所有节点，最后把头结点也释放掉，再把头指针设成 NULL，整个链表就彻底销毁了。
void DestroyList(DLinklist& L) { while (L->next != NULL) //循环：只要头结点的后面还有节点，就继续删 DeleteNextNode(L); //调用删除函数，删掉头结点后面的第一个节点，循环执行直到所有数据节点都被删掉 free(L); //所有数据节点都删完了，现在释放头结点的内存 L = NULL; //把头指针L设为NULL，避免变成野指针 return; }五. 循环链表的定义
1. 循环单链表
循环单链表与单链表的区别就是，原来表尾指针指向NULL的，现在改为指向头结点。
循环单链表结点结构图示如下：
因此循环单链表中不会出现指针域指向NULL的结点，因此判空条件从是否头结点指向NULL改为是否等于头指针L。
判空：L->next == L;
判p是否为尾：p->next == L;
2. 循环双链表
循环双链表相比循环单链表增加了头结点的prior指针也将指向表尾结点这一点。
循环双链表结点结构图示如下：
同理，循环双链表的判空条件是头结点的prior指针和next指针是否都指向头指针L。
判空：L->next == L; L->prior == L;
判p是否为尾：p->next == L;
六. 静态链表的定义
静态链表说白了就是用数组来实现线性表的链式存储结构，结点同样也分为用来存我们要放的实际数据的数据域data和指针域next。不过这里的 “指针” 不是真正的内存地址，而是下一个节点在数组里的下标（也叫游标）。
注意：静态链表的数组大小是我们提前定好的，所以它能存的节点数量有固定上限，不能像动态链表那样随便加节点。
静态链表结点结构图示如下：
静态链表中的结点声明如下：
#define MaxSize 50 //宏定义一个静态链表的最大长度 typedef struct { //静态链表结构类型的定义 ElemType data; //存储数据元素 int next; //下一个元素的数组下标 }SLinkList[MaxSize];静态链表以 next == -1 作为结束标志，因为数组的下标都是 ≥0 的正数，-1 就代表 “这个节点后面没有其他节点了”，作用和动态链表最后一个节点的next=NULL是一模一样的。
其余操作与动态链表几乎相同，比如插入、删除节点，都只需要修改 next 指针，不用移动其他元素。唯一的小区别是，静态链表不用手动申请、释放节点的内存，而是从我们提前开好的数组里找空闲的位置来用，动态链表则是需要的时候才申请内存。
七. 顺序表和链表的区别
1. 存取方式
顺序表：支持随机存取和顺序存取。
顺序表的本质是数组，只要给出元素的下标，就可以直接通过内存地址计算一步找到对应元素，时间复杂度为 O (1) 。比如我们要找顺序表的第 5 个元素，直接访问data[4]就能拿到，不需要遍历前面的元素。
链表：仅支持顺序存取。
链表的节点在内存中是分散的，要找到第 i 个元素，必须从链表的头结点开始，顺着指针一个一个遍历到目标位置，无法直接跳转到对应节点，时间复杂度为 O (n) 。比如要找链表的第 5 个元素，必须从第 1 个开始，依次往后数 4 次才能找到。
2. 逻辑结构与物理结构
顺序表：采用顺序存储。逻辑上相邻，物理存储位置也相邻。
链表：采用链式存储。逻辑上相邻，物理存储位置不一定相邻。
3. 查找、插入和删除操作
按序查找：顺序表的随机存取结构使得时间复杂度为 O (1) ;链表必须从头开始遍历查找，所以时间复杂度为 O (n) 。
按值查找：如果表内元素是无序的，则顺序表和链表都必须从头开始找，时间复杂度均为 O (n) ；如果表内元素是有序的，则顺序表可以用二分法查找，时间复杂度为 O (nlog2n) ，而链表时间复杂度依旧为 O (n) 。
4. 空间分配
顺序表：分为静态分配顺序表和动态分配顺序表。
对于静态分配顺序表，数组大小在初始化的时候就已经定死了，若分配量过小，元素量超出存储空间上限就会溢出导致运行崩溃；若分配量过大，会使得空间闲置浪费。
而动态分配顺序表，虽然可以在存储空间不够用时随时扩容，但是它的扩容是开一个新空间，然后把旧空间装不下的内容全部复制到新空间中，操作量大，效率极低。并且还可能因为找不到足够大的连续内存而扩容失败.
链表：其结点内存是在插入时才申请、删除时就释放的，不需要提前确定链表的最大长度，只要系统还有可用内存，就可以继续添加结点；同时结点可以利用内存中零散的空闲空间，不会出现大块内存闲置的问题，唯一的空间开销是每个结点需要额外的内存来存放指针。
下期预告：《数据结构》保姆级代码大题解析 —— 链表
