27 顺序表 · 链表

一、单链表

（一）概念

1、节点

2、链表的性质

（二）单链表的实现

（三）单链表算法题

1、移除链表元素

2、反转链表

3、链表的中间节点

4、合并两个有序的单链表

5、链表分割

6、链表的回文结构

7、相交链表

8、环形链表 · 是否是环形链表

9、环形链表 · 寻找环形起始点

10、随机链表的复制

二、链表的分类

三、双向链表

（一）概念与结构

（二）双向链表的实现

四、顺序表与链表的分析

一、单链表

（一）概念

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

总结：链表的逻辑结构是线性的，数据是一个接着一个的；物理结构不一定是线性的。

1、节点

与顺序表不同的是，链表里的每个元素都是独立申请下来的空间，我们称之为“结点”。

单链表的结点的组成主要有两个部分：当前结点要保存的数据和保存下⼀个结点的地址（指针变量），也称为数据域和指针域。

在单链表中需要通过指针变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。

2、链表的性质

① 链式结构在逻辑上是连续的，在物理结构上不一定连续。

② 节点一般是从堆上申请的。（通过动态内存管理进行开辟空间）

③ 从堆上开辟的空间，是按照一定策略分配出来的，每次开辟的空间可能连续，也可能不连续。

（二）单链表的实现

单链表常用名：SingleList，简称SLT；单链表节点常用名字：SLTNode。

定义链表结构体，其实是在定义节点的结构体，因为链表是由一个个的节点组合起来的。

单链表的编写：

① 头文件：定义单链表的节点结构体，声明要提供的操作（起到目录作用）；

② cpp文件：编写具体实现各种操作（起到内容作用）；

③ 测试文件：测试是否可以正常运行。

SList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<iostream>
using namespace std;typedef int SLTDataType;
typedef struct SLTNode
{SLTDataType data;struct SLTNode* next;
}SLTNode;//一、创建新节点、打印链表、查找节点
//	(一)创建新节点
SLTNode* create_node(SLTDataType num);
//	(二)打印链表
void SLTPrint(SLTNode* phead);
//	(三)查找节点
SLTNode* find_node(SLTNode* phead, SLTDataType num);//二、插入数据(传过来的单链表可以为空，单一定要创建新节点)
//	(一)尾插
void SLTPushBack(SLTNode*& phead, SLTDataType num);
//	(二)头插
void SLTPushFront(SLTNode*& phead, SLTDataType num);
//	(三)指定位置插
//		1、指定位置之前插
void SLTInsert(SLTNode*& phead, SLTNode* pos, SLTDataType num);
//		2、指定位置之后插
void SLTInsertAfter(SLTNode* pos, SLTDataType num);//三、删除数据(要判断传过来的节点是否为空)
//	(一)尾删
void SLTPopBack(SLTNode*& phead);
//	(二)头删
void SLTPopFront(SLTNode*& phead);
//	(三)指定位置删除
//		1、指定位置删除
void SLTErase(SLTNode*& phead, SLTNode* pos);
//		2、指定位置之后删除
void SLTEraseAfter(SLTNode* pos);
//	(四)销毁单链表
void SLTDestroy(SLTNode*& phead);

SList.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"//一、创建新节点、打印链表、查找节点
//	(一)创建新节点
SLTNode* create_node(SLTDataType num)
{SLTNode* new_node = (SLTNode*)malloc(sizeof(SLTNode));if (new_node == nullptr){perror("creat_node fail");exit(1);}new_node->data = num;new_node->next = nullptr;
}
//	(二)打印链表
void SLTPrint(SLTNode* phead)
{while (phead){cout << phead->data << " -> ";phead = phead->next;}cout << "nullptr" << endl;
}
//	(三)查找节点
SLTNode* find_node(SLTNode* phead, SLTDataType num)
{while (phead){if (phead->data == num)return phead;phead = phead->next;}
}//二、插入数据(传过来的单链表可以为空，单一定要创建新节点)
//	(一)尾插
void SLTPushBack(SLTNode*& phead, SLTDataType num)
{SLTNode* new_node = create_node(num);if (phead == nullptr)phead = new_node;else{SLTNode* node = phead;while (node->next)node = node->next;node->next = new_node;new_node->next = nullptr;}
}
//	(二)头插
void SLTPushFront(SLTNode*& phead, SLTDataType num)
{SLTNode* new_node = create_node(num);if (phead == nullptr)phead = new_node;else {new_node->next = phead;phead = new_node;}
}
//	(三)指定位置插
//		1、指定位置之前插
void SLTInsert(SLTNode*& phead, SLTNode* pos, SLTDataType num)
{assert(pos);SLTNode* new_node = create_node(num);if (phead == pos){new_node->next = phead;phead = new_node;}else{SLTNode* pre_node = phead;while (pre_node){if (pre_node->next == pos){new_node->next = pre_node->next;pre_node->next = new_node;break;}pre_node = pre_node->next;}}
}
//		2、指定位置之后插
void SLTInsertAfter(SLTNode* pos, SLTDataType num)
{assert(pos);SLTNode* new_node = create_node(num);new_node->next = pos->next;pos->next = new_node;
}//三、删除数据(要判断传过来的节点是否为空)
//	(一)尾删
void SLTPopBack(SLTNode*& phead)
{assert(phead);if(phead->next == nullptr){free(phead);phead == nullptr;}else{SLTNode* pre_node = phead;while (pre_node->next->next)pre_node = pre_node->next;SLTNode* node = pre_node->next;pre_node->next = nullptr;free(node);node = nullptr;}
}
//	(二)头删
void SLTPopFront(SLTNode*& phead)//若不传引用，则会造成二次free
{assert(phead);SLTNode* node = phead->next;free(phead);phead = node;
}
//	(三)指定位置删除
//		1、指定位置删除
void SLTErase(SLTNode*& phead, SLTNode* pos)
{assert(phead && pos);if (phead == pos){phead = phead->next;free(pos);pos = nullptr;}else{SLTNode* pre_node = phead;while (pre_node){if (pre_node->next == pos){pre_node->next = pos->next;free(pos);pos = nullptr;break;}pre_node = pre_node->next;}}
}
//		2、指定位置之后删除
void SLTEraseAfter(SLTNode* pos)
{assert(pos);SLTNode* node = pos->next;pos->next = node->next;free(node);node = nullptr;
}
//	(四)销毁单链表
void SLTDestroy(SLTNode*& phead)
{assert(phead);SLTNode* next_noed = phead->next;while (next_noed){free(phead);phead = next_noed;next_noed = next_noed->next;}free(phead);phead = nullptr;
}

test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"void test()
{//SLTNode* re =  create_node(15);SLTNode* plist = nullptr;for (int i = 1; i < 11; i++){SLTPushBack(plist, i);//SLTPushFront(plist, i);}SLTPrint(plist);SLTNode* re = find_node(plist, 5);//SLTInsert(plist, re, 255);//SLTInsertAfter(re, 255);//for (int i = 0; i < 1; i++)//{//	//SLTPopBack(plist);//	//SLTPopFront(plist);//}//SLTErase(plist, re);//SLTEraseAfter(re);SLTDestroy(plist);SLTPrint(plist);
}int main()
{test();return 0;
}

总结：

① 单链表没办法从右向左遍历，只能从左向右遍历，若是对单链表进行操作，需要影响到目标节点的前一个节点时，需要传递头节点进行遍历，找到目标节点的前一个节点进行修改。

② 在链表中，没有增容的概念（不使用realloc），需要插入新的数据，直接申请一个节点大小的空间就可以了。

③ 判断传参传的是一级指针还是二级指针（使用 “引用” ），就要看是否改变了实参地址指向的空间（这个改变是指实参所指向的空间不会变成另一个地址的空间）。

比如：

在尾插中存在两种情况，第一种是存在节点的时候，直接进行尾插，不需要改变传过来的头节点的指针指向；而第二种情况就是头指针指向空的时候，需要把头指针指向空地址改成指向新开辟的空间的地址，这样就改变了实参指向的地址空间，所以在尾插操作中需要传二级指针（使用 “引用” ）。

而在删除指定节点之后的节点的操作中，并没有改变对指定节点的空间进行改变，所以传一级指针即可。

（三）单链表算法题

1、移除链表元素

题目链接如下：

https://leetcode.cn/problems/remove-linked-list-elements/description/

解题思路：

创建新链表，然后遍历原链表，把除了【指定移除节点】的其他节点全部复制尾插在新链表后面。

注意点：需要把新链表最后的节点的next置为空，因为可能会链接着需要删除的节点的地址。

代码如下：

typedef struct ListNode SLTNode;
struct ListNode* removeElements(struct ListNode* head, int val) 
{//创建新链表SLTNode* new_head, * new_tail;new_head = new_tail = NULL;//遍历原链表SLTNode* pcur = head;while(pcur){if(pcur->val != val){if(new_head == NULL)//尾插分为两种情况：①链表为空 ②链表不为空new_head = new_tail = pcur;else{new_tail->next = pcur;new_tail = new_tail->next;}}pcur = pcur->next;}if(new_tail)new_tail->next = NULL;return new_head;
}

2、反转链表

题目链接如下：

https://leetcode.cn/problems/reverse-linked-list/description/

题解思路：

创建三个指针，第一个指针 p1 指向 nullptr，第二个指针指向头节点，第三个指针指向头节点的下一个节点。然后把第二个指针的指向改成第一个指针所指向的 nullptr，再把第二个指针的地址赋给第一个指针，第三个指针的地址赋给第二个指针，第三个指针向后走一步。

注意点：

需要判断第三个指针是否为空：因为在处理最后一个节点的指向的时候，第三个指针的指向已经是空了，所以要判断一下第三个指针是否为空，若为空就不能解引用结构体里面的值把next赋给自己了；

循环的判断条件为第二个指针是否为空，因为当第二个指针为空的时候，就没有需要改变指向的节点了（画图理解）。

答案代码如下：

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {if(head == NULL)return head;else{ListNode* p1, *p2, *p3;p1 = NULL, p2 = head, p3 = head->next;while(p2){p2->next = p1;p1 = p2;p2 = p3;if(p3)p3 = p3->next;}return p1;//p1为反转链表的头指针}
}

3、链表的中间节点

题目链接如下：

https://leetcode.cn/problems/middle-of-the-linked-list/description/

解题思路：

创建两个指针，起始位置都指向目标链表的第一个节点处；

一个指针为慢指针，另一个指针为快指针，顾名思义慢指针的移动速度比快指针慢，慢指针走一步，快指针走两步；

当快指针到达最后一个节点指向的空地址，或者快指针的下一个节点就是空地址的时候，慢指针所指向的节点就是中间节点。

原理：假设快指针走的路程为n，快指针走的路程是慢指针的两倍，即 2*慢=快；此时慢指针走的路程就是n/2。当链表的长度为5的时候，快指针到达了终点5，而慢指针的路程为2（整形去除小数点），又因为起始位置为1，所以到达的节点是3，为中间节点；当链表的长度为6的时候，快指针到达了终点7，慢指针的路程为3，又因为起始位置为1，所以到达的节点是4，为中间节点。

注意点：

while判断的 pfast && pfast->next 的顺序不能换，若换过来判断偶数节点数中间节点的时候，pfast已经为空地址，空地址不能解引用 pfast->next，这样会报错。

答案代码如下：

typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {ListNode* pfast, *pslow;pfast = pslow = head;while(pfast && pfast->next){pfast = pfast->next->next;pslow = pslow->next;}return pslow;
}

4、合并两个有序的单链表

题目链接如下：

https://leetcode.cn/problems/merge-two-sorted-lists/description/

解题思路如下：

创建一个新的链表，创建两个指针分别指向两个有序的单链表；两个有序单链表的节点开始比较，较小或者相等的节点尾插到新链表中，然后比较时较小链表的指针与新链表中指向为节点的指针都向后走一步，开始循环比较大小；循环结束后若是有一方还存在数据，直接把数据全部插入到新链表中。

注意点：

因为每次比较之后都要判断新链表的头尾指针是否为空（为尾插分两种情况），显得代码冗余，可以直接动态申请一个内存给新链表的头尾指针，这样就可以不用检查判断是否为空了。

答案代码如下：

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{if(list1 == NULL)return list2;//这里处理了list1为空的情况与list1和list2都为空的情况if(list2 == NULL)return list1;ListNode* new_head , *new_tail;//创建新链表new_head = new_tail = (ListNode*)malloc(sizeof(ListNode));ListNode* p1 = list1, *p2 = list2;//创建指针指向两个数组while(p1 && p2){if(p1->val < p2->val){new_tail->next = p1;new_tail = p1;p1 = p1->next;}else{new_tail->next = p2;new_tail = p2;p2 = p2->next;}}if(p1)new_tail->next = p1;if(p2)new_tail->next = p2;ListNode* node = new_head->next;//释放掉无有效数据的哨兵节点free(new_head);new_head = node;return new_head;
}

5、链表分割

题目链接如下：

https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70

解题思路：

创建两个非空链表，每个链表都要创建哨兵节点，这样不用每次尾插都要检查节点指针是否为空（因为单链表的尾插有两种情况）；然后进行比较数据大小，把小于x的属于与大于或等于x的数据分别插入小链表与大链表；最后把大链表的节点插入小链表中，释放哨兵节点。

注意点：

尾插不会改变要插入节点的next，这里原来的节点的next可能还是下一个较小节点的地址，这样打印会造成死循环；大连表尾插进小链表后需要把大链表的最后一个节点的next置空。

答案代码如下：

class Partition 
{
public:ListNode* partition(ListNode* pHead, int x) {//创建两个非空链表(创建哨兵节点，这样不用每次尾插都要检查节点指针是否为空)ListNode* less_head, * less_tail;less_head = less_tail = (ListNode*)malloc(sizeof(ListNode));ListNode* big_head, * big_tail;big_head = big_tail = (ListNode*)malloc(sizeof(ListNode));//比较数据大小，分别插入大链表与小链表ListNode* pcur = pHead;while(pcur){if(pcur->val < x){less_tail->next = pcur;less_tail = less_tail->next;}else {big_tail->next = pcur;big_tail = big_tail->next;}pcur = pcur->next;}//把大链表的节点插入小链表中//尾插不会改变要插入节点的next//这里原来的节点的next可能还是下一个较小节点的地址，这样打印会造成死循环，需要把大链表的最后一个节点的next置空big_tail->next = nullptr;less_tail->next = big_head->next;//释放哨兵节点ListNode* re = less_head->next;free(less_head);free(big_head);less_head = big_head = nullptr;return re;}
};

6、链表的回文结构

题目链接如下：

https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa

解题思路：

回文数字、字符串：轴对称；

需要用到的思想为前面题目中的找中间节点与反转链表：设置快慢指针，找到中间节点；设置三个指针，分别指向nullptr、中间节点与中间节点的第二个指针，进行指向反转。最后把反转后的链表与中间节点之前的部分链表从头开始比较，若完全相等就是回文结构。

答案代码如下：

class PalindromeList {
public:ListNode* fine_mid(ListNode* phead){ListNode* pslow, * pfast;pslow = pfast = phead;while(pfast && pfast->next){pslow = pslow->next;pfast = pfast->next->next;}return pslow;}ListNode* reversal(ListNode* mid){ListNode* p1, *p2, *p3;p1 = nullptr, p2 = mid, p3 = mid->next;while(p2){p2->next = p1;p1 = p2;p2 = p3;if(p3)p3 = p3->next;}return p1;}bool chkPalindrome(ListNode* A) {//一、找中间节点ListNode* mid_node = fine_mid(A);//二、把中间节点后面的数据都反转ListNode* rever_head = reversal(mid_node);//三、把反转之后的节点与原头节点while(rever_head)//循环条件是rever_head是否存在，因为rever_head指向的单链表的最后有nullptr，而A取不符合条件{if(rever_head->val != A->val)return false;rever_head = rever_head->next;A = A->next;}return true;}
};

7、相交链表

题目链接如下：

https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

相交链表的图例如下：

解题思路：

首先从两个不同的头节点开始到尾进行遍历，并计算从不同头节点开始的总节点个数，并计算节点个数之差的绝对值；然后设置长链表与短链表，让长链表先走节点差数的步数，再开始分别遍历两个链表，若有相同地址的节点，则返回该节点的地址，若没有相同地址的节点，则返回nullptr。

注意点：

求绝对值函数：abs（）。

答案代码如下：

typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {//遍历链表，找节点差ListNode* node_A = headA;ListNode* node_B = headB;int size_A = 0, size_B = 0;while(node_A){size_A++;node_A = node_A->next;}while(node_B){size_B++;node_B = node_B->next;}int gap = abs(size_A - size_B);//计算节点个数差//设置长短链表ListNode* long_list = headA;ListNode* short_list = headB;if(size_A < size_B){long_list = headB;short_list = headA;}while(gap--)//先让长链表走节点差步long_list = long_list->next;//遍历两链表，有相同地址值就返回节点地址，没有就返回nullwhile(long_list && short_list){if(long_list == short_list)return long_list;long_list = long_list->next;short_list = short_list->next;}return NULL;
}

8、环形链表 · 是否是环形链表

题目链接如下：

https://leetcode.cn/problems/linked-list-cycle/description/

解题思路如下：

带环链表：从头节点开始遍历链表，遍历不会结束。链表的尾节点next指针不指向空；

使用的是快慢指针的思想（即慢指针一次走一步，快指针⼀次走两步），两个指针从链表起始位置开始运行，如果链表带环则⼀定会在环中相遇，否则快指针率先走到链表的未尾。

注意点：

无论快指针一次走多少步，最终都会与慢指针相遇。并且快指针走了三步及以上步数，就会引入额外的代码步骤，所以一般快指针都是走两步。

答案代码如下：

typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {ListNode* fast = head, *slow = head;while(fast && fast->next){if(fast == slow)return true;fast = fast->next->next;slow = slow->next;} return false;
}

9、环形链表 · 寻找环形起始点

题目链接如下：

https://leetcode.cn/problems/linked-list-cycle-ii/description/

解题思路：

解题原理：让⼀个指针从链表起始位置开始遍历链表，同时让⼀个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。

具体过程：设置快慢指针从环形链表的头节点开始遍历，慢指针走一步，快指针走两步，得到他们的相遇点并记录下来；然后设置两个速度相同的指针，一个从环形链表的头节点开始遍历，另一个从快慢指针的相遇点开始遍历，他们每次都是走一步；最终会在环形链表的循环起始点相遇。

答案代码如下：

typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) 
{ListNode* fast = head;ListNode* slow = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){ListNode* node = head;while(node != slow){node = node->next;slow = slow->next;}return slow;}}return NULL;
}

10、随机链表的复制

题目链接如下：

https://leetcode.cn/problems/copy-list-with-random-pointer/description/

解题思路：

原链表如下：

① 复制旧链表中的val值来创建新节点，插入到旧链表头节点之后的每个节点之间：

② 根据旧链表的 random 指针的关系来赋值给新节点的 random 指针：

node->random = pcur->random->next; 若pcur->random指向空，直接让pcur->random指向空。

③ 断开新旧节点之间的联系。

答案代码如下：

typedef struct Node node;node* Buy_node(int num)
{node* re = (node*)malloc(sizeof(node));re->val = num;re->next = re->random = NULL;return re;
}void Add_node(node* phead)
{node* phead_after = NULL;node* new_node = NULL;while(phead){new_node = Buy_node(phead->val);phead_after = phead->next; new_node->next = phead_after;phead->next = new_node;phead = phead_after;    }
}struct Node* copyRandomList(struct Node* head) 
{//处理传空指针的情况if(head == NULL)return NULL;//一、创建节点，并尾插在每个原节点的后面Add_node(head);//二、处理新节点的random指针node* pcur = head;node* copy = pcur->next;while(pcur->next->next)//这里条件结束后不能处理最后一个节点{if(pcur->random != NULL)copy->random = pcur->random->next;pcur = copy->next;copy = pcur->next;}if(pcur->random != NULL)copy->random = pcur->random->next;//三、断开新链表与旧链表的联系pcur = head;node* new_head = pcur->next, * new_tail = pcur->next;while(pcur->next->next){pcur = pcur->next->next;new_tail->next = pcur->next;new_tail = new_tail->next;}return new_head;
}

二、链表的分类

链表的结构非常多样，以下情况组合起来就有八种链表结构：

每种情况具体如下：

虽然有这么多的链表结构，但实际中最常用的还是两种结构：单链表与双向链表。

单链表的全称是：单向不带头不循环链表；

双向链表的全称是：双向带头循环链表。

双向链表与单链表完全不是同一类。

三、双向链表

（一）概念与结构

带头链表里的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这里“放哨的”。

双向链表的节点结构：数据 + 指向后一个节点的指针 + 指向前一个节点的指针。

双向链表比单链表多的东西：哨兵节点 + 指向前一个节点的指针 + 双向循环。

（二）双向链表的实现

双向链表的编写：

① 头文件：定义双向链表的节点结构体，声明要提供的操作（起到目录作用）；

② cpp文件：编写具体实现各种操作（起到内容作用）；

③ 测试文件：测试是否可以正常运行。

List.h

#pragma once#include<stdlib.h>
#include<iostream>
#include<stdbool.h>
#include<assert.h>
using namespace std;typedef int LTDataType;
typedef struct LTNode
{LTDataType data;struct LTNode* prev;struct LTNode* next;}LTNode;//一、节点的创建并初始化、打印链表、判断头节点、查找节点、销毁链表
//(一)节点的创建并初始化
LTNode* Buy_node(LTDataType num);
//(二)链表的初始化
LTNode* LTInit();
//(三)打印链表
void LTPrint(LTNode* phead);
//(四)判断是否只有头节点
bool LTEmpty(LTNode* phead);
//(五)查找节点
LTNode* LTFine(LTNode* phead, LTDataType num);
//(六)销毁链表(是指整个链表都销毁，包括哨兵尾，会影响头指针)
void LTDestroy(LTNode*& phead);//二、节点的插入
//(一)尾插
void LTPushBack(LTNode* phead, LTDataType num);
//(二)头插
void LTPushFront(LTNode* phead, LTDataType num);
//(三)指定位置插入节点
void LTInsert(LTNode* pos, LTDataType num);
//(四)指定位置之后插入节点
void LTInsertAfter(LTNode* pos, LTDataType num);//三、节点的删除
//(一)尾删
void LTPopBack(LTNode* phead);
//(二)头删
void LTPopFront(LTNode* phead);
//(三)指定位置删除节点
void LTErase(LTNode*& pos);
//(四)指定位置之后删除节点
void LTEraseAfter(LTNode* pos);

List.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"//一、节点的创建、初始化、打印链表、判断头节点、查找节点、销毁链表
//(一)节点的创建并初始化
LTNode* Buy_node(LTDataType num)
{//节点的创建LTNode* new_node = (LTNode*)malloc(sizeof(LTNode));if (new_node == nullptr){perror("Buy_node malloc fail");exit(1);}//节点的初始化new_node->data = num;new_node->next = new_node->prev = new_node;return new_node;
}
//(二)链表的初始化
LTNode* LTInit()
{LTNode* plist = Buy_node(-1);return plist;
}
//(三)打印链表
void LTPrint(LTNode* phead) 
{LTNode* pcur = phead->next;cout << "-> ";while (pcur != phead){cout << pcur->data << " -> ";pcur = pcur->next;}cout << endl;
}
//(四)判断是否只有头节点
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}
//(五)查找节点
LTNode* LTFine(LTNode* phead, LTDataType num)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == num)return pcur;pcur = pcur->next;}return nullptr;
}
//(六)销毁链表
void LTDestroy(LTNode*& phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next_noed = pcur->next;//next_noed->prev = phead;//phead->next = next_noed;free(pcur);pcur = next_noed;}free(phead);pcur = phead = nullptr;
}//二、节点的插入
//(一)尾插
void LTPushBack(LTNode* phead, LTDataType num)
{LTNode* new_node = Buy_node(num);new_node->next = phead;new_node->prev = phead->prev;phead->prev->next = new_node;phead->prev = new_node;}
//(二)头插
void LTPushFront(LTNode* phead, LTDataType num)
{LTNode* new_node = Buy_node(num);new_node->next = phead->next;new_node->prev = phead;phead->next->prev = new_node;phead->next = new_node;}
//(三)指定位置插入节点
void LTInsert(LTNode* pos, LTDataType num)
{assert(pos);LTNode* new_node = Buy_node(num);LTNode* pre_node = pos->prev;new_node->next = pos;new_node->prev = pre_node;pos->prev = new_node;pre_node->next = new_node;}
//(四)指定位置之后插入节点
void LTInsertAfter(LTNode* pos, LTDataType num)
{assert(pos);LTNode* new_node = Buy_node(num);LTNode* after_node = pos->next;new_node->next = after_node;new_node->prev = pos;after_node->prev = new_node;pos->next = new_node;
}//三、节点的删除
//(一)尾删
void LTPopBack(LTNode* phead)
{assert(phead);//空指针不可删除，需要判断assert(!LTEmpty(phead));//判断是不是只有头节点LTNode* del = phead->prev;LTNode* pre = del->prev;pre->next = phead;phead->prev = pre;free(del);del = nullptr;
}
//(二)头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* del = phead->next;LTNode* del_after = del->next;del_after->prev = phead;phead->next = del_after;free(del);del = nullptr;
}
//(三)指定位置删除节点
void LTErase(LTNode*& pos)
{assert(pos);LTNode* pre_node = pos->prev;LTNode* after_node = pos->next;pre_node->next = after_node;after_node->prev = pre_node;free(pos);pos = nullptr;
}
//(四)指定位置之后删除节点
void LTEraseAfter(LTNode* pos)
{assert(pos);LTNode* del = pos->next;LTNode* after_node = del->next;after_node->prev = pos;pos->next = after_node;free(del);del = nullptr;}

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"void test()
{LTNode* plist = Buy_node(-1);//LTPrint(plist);for (int i = 1; i < 11; i++)LTPushBack(plist, i);//LTPushFront(plist, i);LTPrint(plist);/*for (int i = 0; i < 5; i++)LTPopFront(plist);LTPrint(plist);*///LTNode* re_pos =  LTFine(plist, 10);//LTInsertAfter(re_pos, 255);//LTEraseAfter(re_pos);LTDestroy(plist);//LTPrint(plist);
}int main()
{ test();return 0;
}

总结：

① 第一个节点指的是第一个有效的节点，而哨兵位是无效的节点（头节点）；

② 插入时修改节点的顺序：先修改插入的新节点，再修改前一个指针（head->prev ）和head指针的指向；（先改新节点，然后从后向前改）

③ 在哨兵位之前插入，也是尾插；