文章目录
1.双向链表的概念和结构
1.1 双向链表的概念
概念：双向链表是一种链式数据结构，其每个节点都包含三个部分：数据域、前驱指针和后继指针。这种设计使得链表中的每个节点都可以找到其前后的节点，从而实现了双向遍历的能力。
1.2 双向链表与单链表的对比
一.结构区别：
1.节点区别：
单链表：每个节点只包含一个数据域和一个指向下一个节点的指针域（next指针）。这种结构使得单链表只能单向遍历。
双向链表：每个节点除了包含一个数据域外，还包含两个指针域：一个指向前一个节点的指针域（prev指针）和一个指向下一个节点的指针域（next指针）。这种结构使得双向链表可以双向遍历。
2.空间开销:
由于双向链表的每个节点都需要额外存储一个前驱指针，因此其空间开销相比单链表要大。
二.功能区别:
1.遍历能力:
单链表：只能从头节点开始，单向遍历到尾节点。
双向链表：可以从任意节点开始，向前或向后遍历整个链表。
2.插入和删除操作
单链表：插入和删除节点时，只需修改相邻节点之间的指针，操作相对简单。但需要注意的是，删除节点时通常需要从第一个节点开始遍历链表以找到该节点进行删除。因此，时间复杂度为O(N)
双向链表：插入和删除节点时，需要同时修改前驱和后继节点的指针，操作相对复杂一些。但由于可以双向遍历，因此在某些情况下（如删除指定节点）可能更高效。
三.应用场景区别
1.动态内存管理:
单链表和双向链表都适用于动态内存管理，因为它们都可以在运行时动态地添加或删除节点。然而，由于双向链表的空间开销较大，因此在内存资源有限的情况下，单链表可能更为合适。
2.实现复杂数据结构:
单链表是构建更复杂数据结构（如双向链表、循环链表、链式哈希表等）的基础。而双向链表本身就可以看作是一种在单链表基础上的改进和扩展。
3.查询效率:
对于需要频繁查询前驱节点的应用场景（如LRU缓存机制），双向链表由于其双向遍历的能力而更具优势。而在其他只需要单向遍历的应用场景中（如简单的队列实现），单链表可能就足够了。
链表的结构非常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构：
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：单链表(单向不带头不循环链表)和双向链表(双向带头循环链表)
1.3 双向链表的结构
双向链表的结点由三个部分组成：
1.保存当前结点的数据——data
2.指向下一个结点的指针——next
3.指向上一个结点的指针——prev
//定义双链表结点的结构
typedef int LTDataType;
typedef struct LTNode {
LTDataType data;//保存数据
struct LTNode* next;//指向下一个结点的指针
struct LTNode* prev;//指向前一个结点的指针
}LTNode;
注意：
1.双向链表带有哨兵位结点，也就是头结点，但不是第一个结点
2.哨兵位结点不存储任何有效元素，只是站在这里“放哨的”
3.有哨兵位结点的双向链表才是双向链表
哨兵位结点的作用：
1.简化边界条件处理：
在普通的双向链表中，头节点的前驱和尾节点的后继都是null，这在进行插入、删除等操作时需要对边界条件进行特殊处理。而添加了哨兵位结点后，头哨兵的前驱可以指向尾节点，尾节点的后继可以指向头哨兵，从而形成一个闭环，避免了对边界条件的特殊处理。哨兵位结点永远不为空，这减少了空指针带来的麻烦，比如在头插、尾插时，不需要担心头节点或尾节点为空的情况。
2. 提高操作效率：
由于哨兵位的前驱指针指向尾结点，后继指针指向头结点，所以访问头结点和尾结点非常方便。在一些插入和删除操作中(如头插，尾插，头删，尾删)的时间复杂度为O(1)
2. 双向链表的接口实现
2.1 申请一个新结点
对申请新结点的功能进行封装，方便其它接口调用
//申请一个新结点
LTNode* LTBuyNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//使用malloc函数申请一个结点空间
if (newnode == NULL)
{
//申请失败
perror("malloc fail!");//打印错误信息
exit(1);//异常退出
}
//申请成功
newnode->data = x;
//因为是双向循环链表所以申请的新结点初始时的prev和next先指向自身，即使链表只有头结点也是循环的
newnode->next = newnode;
newnode->prev = newnode;
return newnode;//返回新节点
}
创建新节点使用malloc函数，realloc函数适用于对一块连续存储空间开辟更大的空间，双向链表的结点都是独立存在的，逻辑结构上是连续的，但物理结构上不一定是连续的。
2.2 初始化
//初始化
void LTInit1(LTNode** pphead)
{
*pphead = LTBuyNode(-1);//创建一个新结点为头结点（哨兵位结点）
}
LTNode* LTInit2()
{
return LTBuyNode(-1);//任意传递一个变量
}
初始化方式有两种：
第一种：创建一个新节点(一级指针)，如果要改变一级指针的内容从而改变头节点就要传入一级指针的地址，要在函数内改变头指针就要用二级指针去接收一级指针的地址。 然后调用申请节点函数创建哨兵位节点，再对二级指针解引用变为一级指针去接收即可。
第二种：不需要传递参数，直接调用申请节点函数创建哨兵位节点再返回哨兵位节点即可。
2.3 打印
//打印
void LTPrint(LTNode* phead)
{
if (phead == NULL)
{
//如果链表为空就打印NULL
printf("NULL\n");
return;
}
LTNode* pcur = phead->next;//从第一个结点开始打印
while (pcur!=phead)//不等于哨兵位结点
{
LTNode* pcurnext = pcur->next;
if (pcurnext != phead)
{
printf("%d->", pcur->data);
}
else
{
printf("%d\n", pcur->data);
}
pcur = pcurnext;
}
}
思路：创建一个结点指针pcur指向链表中的第一个结点，遍历链表，当pcur指向哨兵位结点时就退出循环，完成打印。
2.4 尾插
因为哨兵位结点的前驱指针prev指向尾结点，所以尾结点可以直接找到，不需要遍历，ptail=phead->prev
思路: 先修改新结点newnode的前驱指针和后继指针，再修改头结点的前驱指针和尾结点的后继指针。如果先修改后者，那么新结点newnode就成为了尾结点，而newnode的prev指针就不知道指向谁(头结点phead的prev指针已修改，指向newnode)，newnode的prev指针应该要指向原链表的尾结点。
注意：因为尾插不会影响哨兵位结点(头结点)，所以传入函数内的是一级指针,后续接口功能的实现都是一样，只要不影响哨兵位结点的都传入一级指针。
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);//哨兵位结点（头结点）不能为空
LTNode* newnode = LTBuyNode(x);//创建一个新结点
newnode->next = phead;//新结点next指针为头结点phead
newnode->prev = phead->prev;//新结点prev指针为尾结点即头结点的前一个结点（phead->prev）
//下面两步不能调换
phead->prev->next = newnode;//头结点的前一个结点(尾结点)的next指针为newnode
phead->prev = newnode;//头结点的prev指针(头结点的前一个结点)为newnode
}
功能测试：
2.5 头插
因为哨兵位结点的后继指针next指向第一个结点，所以第一个结点可以直接找到，不需要遍历，第一个结点为：phead->next
注意： 先修改新结点newnode的前驱指针和后继指针，再修改第一个结点的前驱指针和头结点的后继指针。如果先修改后者，那么新结点newnode就成为了第一个结点，而newnode的next指针就不知道指向谁(头结点phead的next指针已修改，指向newnode)，newnode的next指针应该要指向原链表的第一个结点。
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);//哨兵位结点（头结点）不能为空
LTNode* newnode = LTBuyNode(x);//创建一个新结点
newnode->next = phead->next;
newnode->prev = phead;
//下面两步不能调换
phead->next->prev = newnode;
phead->next = newnode;
}
功能测试：
2.6 判断链表是否为空
思路：如果链表为空，则只有一个哨兵位结点，哨兵位结点的后继指针next和前驱指针prev指向自己
//判断链表是否为空
bool LTEmpty(LTNode* phead)
{
assert(phead);//哨兵位结点（头结点）不能为空
if (phead->next == phead)
{
return true;
}
else
{
return false;
}
}
功能测试：
2.7 尾删
思路：首先链表不能为空，将尾结点del删除之后，新的尾节点为del->prev，所以先修改指针连接方向，然后使用free函数释放del结点，最后将del结点指针指向空，否则del会变成一个野指针
//尾删
void LTPopBack(LTNode* phead)
{
assert(phead);//哨兵位结点（头结点）不能为空
assert(!LTEmpty(phead));//链表不为空
LTNode* del = phead->prev;
LTNode* prev = del->prev;
prev->next = phead;
phead->prev = prev;
free(del);//释放内存
del = NULL;//指向空
}
功能测试：
2.8 头删
思路：首先链表不能为空，将第一个结点del删除之后，新的第一个节点为del->next，所以先修改指针连接方向，然后使用free函数释放del结点，最后将del结点指针指向空，否则del会变成一个野指针
//头删（删除的是第一个结点，不是头结点）
void LTPopFront(LTNode* phead)
{
assert(phead);//哨兵位结点（头结点）不能为空
assert(!LTEmpty(phead));//链表不为空
LTNode* del = phead->next;
del->next->prev = phead;
phead->next = del->next;
free(del);//释放内存
del = NULL;//指向空
}
功能测试：
2.9 查找
功能：找到指定结点并返回该结点
思路：创建一个结点指针find指向第一个结点find=phead->next
从find开始遍历链表，循环的条件为find!=phead，如果退出循环前找到指定结点则返回该结点，否则返回NULL
//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);//哨兵位结点（头结点）不能为空
LTNode* find = phead->next;//从第一个结点开始
while (find != phead)
{
if (find->data == x)
{
//找到了
return find;
}
find = find->next;
}
//没有找到
return NULL;
}
功能测试：
2.10 在指定位置之后插入数据
思路：创建一个新节点newnode，先让newnode的前驱指针prev和后继指针next分别指向pos结点和pos结点的下一个节点(pos->next)，再让pos结点的下一个结点(pos->next)的前驱指针prev指向newnode，pos结点的next指针指向newnode
第一种写法：
void LTInsertAfter1(LTNode* pos, LTDataType x)
{
assert(pos);//传入的结点不为空
LTNode* newnode = LTBuyNode(x);//申请新节点
LTNode* next = pos->next;//保存pos结点的next指针
//重新连接
newnode->next = next;
newnode->prev = pos;
next->prev = newnode;
pos->next = newnode;
}
第二种写法：
void LTInsertAfter2(LTNode* phead, LTDataType x, LTDataType y)
{
assert(phead);//哨兵位结点（头结点）不能为空
LTNode* pos = LTFind(phead, x);//找到指定的pos结点
LTNode* newnode = LTBuyNode(y);//申请新节点
LTNode* next = pos->next;//保存pos结点的next指针
//重新连接
newnode->next = next;
newnode->prev = pos;
next->prev = newnode;
pos->next = newnode;
}
功能测试：
2.11 在指定位置之前插入数据
思路：和在指定位置之后插入数据类似，创建一个新节点newnode，先让newnode的前驱指针prev和后继指针next分别指向pos结点的前一个结点(pos->prev)和pos结点，再让pos结点的前一个结点(pos->prev)的后继指针next指向newnode，pos结点的前驱指针prev指向newnode
第一种写法：
void LTInsert1(LTNode* pos, LTDataType x)
{
assert(pos);//传入的结点不为空
LTNode* newnode = LTBuyNode(x);//申请新节点
LTNode* prev = pos->prev;//保存pos结点的前一个结点
//重新连接
newnode->next = pos;
newnode->prev = prev;
prev->next = newnode;
pos->prev = newnode;
}
第二种写法：
void LTInsert2(LTNode* phead, LTDataType x, LTDataType y)
{
assert(phead);//哨兵位结点（头结点）不能为空
LTNode* pos = LTFind(phead, x);//找到指定结点pos
assert(pos);//结点不能为空
LTNode* newnode = LTBuyNode(y);//申请新节点
LTNode* prev = pos->prev;//保存pos结点的前一个结点
//重新连接
newnode->next = pos;
newnode->prev = prev;
prev->next = newnode;
pos->prev = newnode;
}
功能测试：
2.12 删除指定位置结点
思路：首先链表不能为空，先修改pos结点的下一个结点(pos->next)的前驱指针和pos结点的前一个结点(pos->prev)的后继指针，分别指向pos结点的前一个结点(pos->prev)和pos结点的下一个结点(pos->next)。 然后使用free函数释放pos结点，最后将pos结点指针指向空，否则pos会变成一个野指针
第一种写法：
void LTErase1(LTNode* pos)
{
assert(pos);//传入的结点不为空
//重新连接
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);//释放内存
pos = NULL;//指向空
}
第二种写法：
void LTErase2(LTNode* phead, LTDataType x)
{
assert(phead);//哨兵位结点（头结点）不能为空
LTNode* pos = LTFind(phead, x);//找到指定位置的结点pos
//重新连接
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);//释放内存
pos = NULL;//指向空
}
功能测试：
2.13 销毁
思路：创建一个结点指针pcur指向第一个结点，从第一个结点开始遍历链表，然后逐一销毁pcur结点，因为pcur已经被销毁了，为了让pcur还能指向下一个结点继续销毁，所以我们再创建一个结点指针next指向pcur的下一个结点，pcur所指向的结点被销毁了就让pcur指向下一个结点即可。循环条件为pcur!=phead，当pcur指向头结点phead时，退出循环，此时头结点还没被销毁，再继续销毁头结点，不要忘了让头结点指针指向空，否则头结点指针会变成野指针
第一种写法：
因为头结点指针会被修改，所以传入函数内的是头结点的二级指针
void LTDesTroy1(LTNode** pphead)
{
assert(pphead && *pphead);//传入的地址不能为空，哨兵位结点（头结点）也不能为空
LTNode* pcur = (*pphead)->next;//从第一个结点开始遍历链表
while (pcur != *pphead)
{
LTNode* next = pcur->next;//保存下一个结点
free(pcur);//销毁结点
pcur = next;//指向下一个结点
}
free(*pphead);//销毁头结点
*pphead = NULL;//头结点指针指向空
pcur = NULL;//此时pcur也指向头结点，也需要指向空
}
第二种写法：
为了保存接口的一致性，我们可以传入头结点的一级指针，但需要注意的是传入的是指针变量，而不是地址(要想形参改变实参，应该传入实参的地址)，函数外的头结点指针*plist还是指向头结点，所以我们还需要手动将实参(*plist)置为空，否则后续继续使用plist指针就会出现问题
void LTDesTroy2(LTNode* phead)//传一级，需要手动将plist置为NULL
{
LTNode* pcur = phead->next;//从第一个结点开始遍历链表
while (pcur != phead)
{
LTNode* next = pcur->next;//保存下一个结点
free(pcur);//销毁结点
pcur = next;//指向下一个结点
}
free(phead);//销毁头结点
phead = pcur = NULL;//指向空
}
功能测试：
3. 顺序表和链表的对比
4. 源代码
List.h头文件
#pragma once//只包含一次头文件,防止重复调用
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
//定义双链表结点的结构
typedef int LTDataType;
typedef struct LTNode {
LTDataType data;//保存数据
struct LTNode* next;//指向下一个结点的指针
struct LTNode* prev;//指向前一个结点的指针
}LTNode;
//初始化
void LTInit1(LTNode** pphead);
LTNode* LTInit2();
//打印
void LTPrint(LTNode* phead);
//申请一个新结点
LTNode* LTBuyNode(LTDataType x);
//插入
//第一个参传一级还是二级，要看pphead指向的节点会不会发生改变
//如果发生改变，那么pphead的改变要影响实参，传二级
//如何不发生改变，pphead不会影响实参，传一级
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);
//删除
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);
//判断链表是否为空,为空返回true，反之返回false
bool LTEmpty(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//在指定位置之前插入数据
void LTInsert1(LTNode* pos, LTDataType x);
void LTInsert2(LTNode* phead, LTDataType x, LTDataType y);
//在指定位置之后插入数据
void LTInsertAfter1(LTNode* pos, LTDataType x);
void LTInsertAfter2(LTNode* phead, LTDataType x, LTDataType y);
//删除指定位置结点
void LTErase1(LTNode* pos);
void LTErase2(LTNode* phead, LTDataType x);
//销毁
void LTDesTroy1(LTNode** pphead);
void LTDesTroy2(LTNode* phead);//传一级，需要手动将plist置为NULL
List.c源文件
#include "List.h"
//申请一个新结点
LTNode* LTBuyNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//使用malloc函数申请一个结点空间
if (newnode == NULL)
{
//申请失败
perror("malloc fail!");//打印错误信息
exit(1);//异常退出
}
//申请成功
newnode->data = x;
//因为是双向循环链表所以申请的新结点初始时的prev和next先指向自身，即使链表只有头结点也是循环的
newnode->next = newnode;
newnode->prev = newnode;
return newnode;//返回新节点
}
//初始化
void LTInit1(LTNode** pphead)
{
*pphead = LTBuyNode(-1);//创建一个新结点为头结点（哨兵位结点）
}
LTNode* LTInit2()
{
return LTBuyNode(-1);//任意传递一个变量
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);//哨兵位结点（头结点）不能为空
LTNode* newnode = LTBuyNode(x);//创建一个新结点
newnode->next = phead;//新结点next指针为头结点phead
newnode->prev = phead->prev;//新结点prev指针为尾结点即头结点的前一个结点（phead->prev）
//下面两步不能调换
phead->prev->next = newnode;//头结点的前一个结点(尾结点)的next指针为nownode
phead->prev = newnode;//头结点的prev指针(头结点的前一个结点)为nownode
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);//哨兵位结点（头结点）不能为空
LTNode* newnode = LTBuyNode(x);//创建一个新结点
newnode->next = phead->next;
newnode->prev = phead;
//下面两步不能调换
phead->next->prev = newnode;
phead->next = newnode;
}
//打印
void LTPrint(LTNode* phead)
{
if (phead == NULL)
{
//如果链表为空就打印NULL
printf("NULL\n");
return;
}
LTNode* pcur = phead->next;//从第一个结点开始打印
while (pcur!=phead)
{
LTNode* pcurnext = pcur->next;
if (pcurnext != phead)//不等于哨兵位结点
{
printf("%d->", pcur->data);
}
else
{
printf("%d\n", pcur->data);
}
pcur = pcurnext;
}
}
//判断链表是否为空
bool LTEmpty(LTNode* phead)
{
assert(phead);//哨兵位结点（头结点）不能为空
if (phead->next == phead)
{
return true;
}
else
{
return false;
}
}
//尾删
void LTPopBack(LTNode* phead)
{
assert(phead);//哨兵位结点（头结点）不能为空
assert(!LTEmpty(phead));//链表不为空
LTNode* del = phead->prev;
LTNode* prev = del->prev;
prev->next = phead;
phead->prev = prev;
free(del);//释放内存
del = NULL;//指向空
}
//头删（删除的是第一个结点，不是头结点）
void LTPopFront(LTNode* phead)
{
assert(phead);//哨兵位结点（头结点）不能为空
assert(!LTEmpty(phead));//链表不为空
LTNode* del = phead->next;
del->next->prev = phead;
phead->next = del->next;
free(del);//释放内存
del = NULL;//指向空
}
//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);//哨兵位结点（头结点）不能为空
LTNode* find = phead->next;//从第一个结点开始
while (find != phead)
{
if (find->data == x)
{
//找到了
return find;
}
find = find->next;
}
//没有找到
return NULL;
}
//在指定位置之前插入数据
void LTInsert1(LTNode* pos, LTDataType x)
{
assert(pos);//传入的结点不为空
LTNode* newnode = LTBuyNode(x);//申请新节点
LTNode* prev = pos->prev;//保存pos结点的前一个结点
//重新连接
newnode->next = pos;
newnode->prev = prev;
prev->next = newnode;
pos->prev = newnode;
}
void LTInsert2(LTNode* phead, LTDataType x, LTDataType y)
{
assert(phead);//哨兵位结点（头结点）不能为空
LTNode* pos = LTFind(phead, x);//找到指定结点pos
assert(pos);//结点不能为空
LTNode* newnode = LTBuyNode(y);//申请新节点
LTNode* prev = pos->prev;//保存pos结点的前一个结点
//重新连接
newnode->next = pos;
newnode->prev = prev;
prev->next = newnode;
pos->prev = newnode;
}
//在指定位置之后插入结点
void LTInsertAfter1(LTNode* pos, LTDataType x)
{
assert(pos);//传入的结点不为空
LTNode* newnode = LTBuyNode(x);//申请新节点
LTNode* next = pos->next;//保存pos结点的next指针
//重新连接
newnode->next = next;
newnode->prev = pos;
next->prev = newnode;
pos->next = newnode;
}
void LTInsertAfter2(LTNode* phead, LTDataType x, LTDataType y)
{
assert(phead);//哨兵位结点（头结点）不能为空
LTNode* pos = LTFind(phead, x);//找到指定的pos结点
LTNode* newnode = LTBuyNode(y);//申请新节点
LTNode* next = pos->next;//保存pos结点的next指针
//重新连接
newnode->next = next;
newnode->prev = pos;
next->prev = newnode;
pos->next = newnode;
}
//删除指定位置结点
void LTErase1(LTNode* pos)
{
assert(pos);//传入的结点不为空
//重新连接
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);//释放内存
pos = NULL;//指向空
}
void LTErase2(LTNode* phead, LTDataType x)
{
assert(phead);//哨兵位结点（头结点）不能为空
assert(!LTEmpty(phead));//链表不为空
LTNode* pos = LTFind(phead, x);//找到指定位置的结点pos
//重新连接
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);//释放内存
pos = NULL;//指向空
}
//销毁
void LTDesTroy1(LTNode** pphead)
{
assert(pphead && *pphead);//传入的地址不能为空，哨兵位结点（头结点）也不能为空
LTNode* pcur = (*pphead)->next;//从第一个结点开始遍历链表
while (pcur != *pphead)
{
LTNode* next = pcur->next;//保存下一个结点
free(pcur);//销毁结点
pcur = next;//指向下一个结点
}
free(*pphead);//销毁头结点
*pphead = NULL;//头结点指针指向空
pcur = NULL;//此时pcur也指向头结点，也需要指向空
}
void LTDesTroy2(LTNode* phead)//传一级，需要手动将plist置为NULL
{
LTNode* pcur = phead->next;//从第一个结点开始遍历链表
while (pcur != phead)
{
LTNode* next = pcur->next;//保存下一个结点
free(pcur);//销毁结点
pcur = next;//指向下一个结点
}
free(phead);//销毁头结点
phead = pcur = NULL;//指向空
}
test.c源文件
#include "List.h"
void ListTest01()
{
//LTNode* plist = NULL;//建立一个空结点
//LTInit1(&plist);//初始化
LTNode* plist = LTInit2();//初始化
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPrint(plist);
}
void ListTest02()
{
//LTNode* plist = NULL;//建立一个空结点
//LTInit1(&plist);//初始化
LTNode* plist = LTInit2();//初始化
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPrint(plist);
}
void ListTest03()
{
//LTNode* plist = NULL;//建立一个空结点
//LTInit1(&plist);//初始化
LTNode* plist = LTInit2();//初始化
if (LTEmpty(plist))
printf("链表为空\n");
else
printf("链表不为空\n");
LTPushFront(plist, 1);
LTPrint(plist);
if (LTEmpty(plist))
printf("链表为空\n");
else
printf("链表不为空\n");
}
void ListTest04()
{
//LTNode* plist = NULL;//建立一个空结点
//LTInit1(&plist);//初始化
LTNode* plist = LTInit2();//初始化
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPrint(plist);
LTPopBack(plist);
LTPrint(plist);
}
void ListTest05()
{
//LTNode* plist = NULL;//建立一个空结点
//LTInit1(&plist);//初始化
LTNode* plist = LTInit2();//初始化
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
}
void ListTest06()
{
LTNode* plist = LTInit2();//初始化
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPrint(plist);
LTNode* find = LTFind(plist, 1);
if (find == NULL)
printf("没有找到\n");
else
printf("找到了\n");
LTNode* find1 = LTFind(plist, 4);
if (find1 == NULL)
printf("没有找到\n");
else
printf("找到了\n");
}
void ListTest07()
{
//LTNode* plist = NULL;//建立一个空结点
//LTInit1(&plist);//初始化
LTNode* plist = LTInit2();//初始化
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPrint(plist);
LTNode* pos = LTFind(plist, 2);
LTInsert1(pos, 4);
LTPrint(plist);
LTInsert2(plist, 3, 5);
LTPrint(plist);
}
void ListTest08()
{
//LTNode* plist = NULL;//建立一个空结点
//LTInit1(&plist);//初始化
LTNode* plist = LTInit2();//初始化
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPrint(plist);
LTNode* pos = LTFind(plist, 3);
LTInsertAfter1(pos, 4);
LTPrint(plist);
LTInsertAfter2(plist, 3, 5);
LTPrint(plist);
}
void ListTest09()
{
//LTNode* plist = NULL;//建立一个空结点
//LTInit1(&plist);//初始化
LTNode* plist = LTInit2();//初始化
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPrint(plist);
LTNode* pos = LTFind(plist, 3);
LTErase1(pos);
pos = NULL;
LTPrint(plist);
LTErase2(plist, 1);
LTPrint(plist);
}
void ListTest10()
{
//LTNode* plist = NULL;//建立一个空结点
//LTInit1(&plist);//初始化
LTNode* plist = LTInit2();//初始化
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPrint(plist);
LTDesTroy1(&plist);
LTPrint(plist);
LTNode* plist1 = LTInit2();//初始化
LTPushBack(plist1, 1);
LTPushBack(plist1, 2);
LTDesTroy2(plist1);
plist1 = NULL;//需要手动将plist1置为空
LTPrint(plist1);
}
int main()
{
//ListTest01();//尾插
//ListTest02();//头插
//ListTest03();//判断链表是否为空
//ListTest04();//尾删
//ListTest05();//头删
//ListTest06();//查找
//ListTest07();//在指定位置之前插入数据
//ListTest08();//在指定位置之后插入数据
//ListTest09();//删除指定位置结点
ListTest10();//销毁链表
return 0;
}
对以上内容有异议的欢迎各位大佬来讨论，希望对大家有帮助，多多支持哦！
标签：结点,prev,pos,next,链表,LTNode,phead,双向,数据结构 From： https://blog.csdn.net/2301_79601095/article/details/140532063