【数据结构】线性表之链表
目录
一、顺序表的问题
上篇博客陈述了顺序表，是线性表的一种，本博客将陈述另一种常见的线性表——链表。
顺序表虽然在存储数据时较为方便，但仍存在一些问题：
1. 顺序表中间/头部的插入和删除效率较低（时间复杂度为O(N)）
2. 动态数组增容时需要申请新空间、拷贝数据、释放旧空间，会造成不小的内存消耗。
3. 增容一般以2倍增长，这样势必会有一定的空间浪费。（例如当前容量为100，满了以后增容到200，但如果此时只需要再继续插入了5个数据即可，那么就浪费了95个数据空间。）
为了解决以上问题，前人创造了一种新的线性结构来存储数据，它就是链表。
二、 链表
链表是一种物理结构上非连续、非顺序的存储结构，其中的数据元素的逻辑顺序由其中的指针链接次序实现，指针链接的每一个结构体都是一个节点。
链表的结构多种多样，有单向或双向、带头或不带头、循环或非循环之分。
· 单向或双向
· 带头或不带头
· 循环或非循环
但实际中，最常用的是以下两种组合：
· 无头单向非循环链表
· 带头双向循环链表
本博客主要梳理以上两种链表，且通过C语言来模拟实现。
· 无头单向非循环链表
struct SListNode
{
int data;
struct SListNode* next;
}无头单向非循环链表又简称单链表。
单链表拥有两个通过结构体封装的结构体成员——当前节点数据元素和指向下一个节点的指针。
与顺序表一样，它也有一系列通过函数实现的接口，如下：
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
void SLTPrint(SLTNode* phead); //打印单链表
SLTNode* BuySLTNode(SLTDataType x); //动态申请一个新节点
void SLTPushBack(SLTNode** pphead,SLTDataType x); //尾插
void SLTPushFront(SLTNode** pphead, SLTDataType x); //头插
void SLTPopBack(SLTNode** pphead); //尾删
void SLTPopFront(SLTNode** pphead); //头删
SLTNode* SLTFind(SLTNode* phead, SLTDataType x); //查找
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); //pos前插入
void SLTErase(SLTNode** pphead, SLTNode* pos); //pos处删除
void SLTInsertAfter(SLTNode* pos, SLTDataType x); //pos后插入
void SLTEraseAfter(SLTNode* pos); //pos后删除
void SLTDestroy(SLTNode** pphead); //销毁链表1、打印单链表
创建一个SLTPrint()函数，因对链表本身进行操作，故参数类型为指向链表头节点的指针（一般访问和控制链表，都是从头节点切入。可以借以下接口慢慢体会这一点）；因无须返回值，故返回类型为void。
要打印链表，就得先从头节点的数据开始打印。创建一个临时节点cur，初始化为头节点的地址（代替跑腿）。打印头节点的数据后，将下一个节点的next指针覆盖至当前节点cur，然后重复操作，相当于cur每次打印后，都向后移动到下一个节点。
void SLTPrint(SLTNode* phead)
{
//phead可为空，空链表仍可打印，故不必用assert断言
SLTNode* cur = phead;
while(cur!=NULL)
{
printf("%d->", cur->data); //打印当前节点的数据
cur = cur->next; //将下一个节点的地址覆盖至当前结构的地址，相当于cur向后移动一个节点
//cur++; //注：这是顺序表的写法，不是链表的，无法实现数据调用
}
printf("NULL\n"); //尾节点默认为空
}
//[补]
//cur在链表之间移动，是逻辑结构（为方便理解，形象化画出来的）；
//真实情况是cur所存的地址值一直在改变，是物理结构（实实在在的数据在内存中的变化）2、动态申请一个新节点
创建一个BuySLTNode()函数，因建立节点需要存储的数据，故参数为节点的数据；因建立完毕须返回创建的节点的地址，故参数类型为链表的结构体类型SLTNode*。
用malloc申请一个动态空间，然后将所传参数赋给当前数据data，因当下没有下一个节点存在，故将next指针指向空。
SLTNode* BuySLTNode(SLTDataType x)
{
//开辟空间
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
//赋值
newnode->data = x;
newnode->next = NULL;
return newnode;
}该BuySLTNode()函数会频繁地在其他接口函数中复用。
3、尾插
创建一个SLTPushBack()函数，因对链表的头节点本身和插入数据进行操作，故参数为头节点的二级指针和待插入的数据；因无须返回值，故返回类型为空。
注：该函数涉及链表头节点的部分需传二级指针，即头节点指针的指针，这是因为直接通过传参头节点指针访问和控制链表，不会对链表有实际的改变，也可能有野指针的隐患。例如，在下列代码中，头节点为空时，传参为头节点指针，直接连接新的尾节点，就可能出现野指针。
要进行尾插，就需要先找尾，再尾插。用待插入的数据创建一个新的节点后，向后找到尾节点，再将新节点链接在原先的尾节点上，此时新创建的节点即为新的尾节点。
void SLTPushBack(SLTNode** pphead/*SLTNode* phead*/, SLTDataType x)
{
assert(pphead); //空链表可插入，故phead无须断言，但pphead需断言
SLTNode* newnode = BuySLTNode(x); //用待插入的数据，创建一个新节点
if (*pphead == NULL/*phead == NULL*/) //若头节点为空，则无须找尾，直接将创建的新节点连接上即可
{
*pphead = newnode;
}
else //头节点不为空就找尾
{
SLTNode* tail = *pphead; //定义一个链表结构体tail（尾巴）去代替跑腿
while (tail->next != NULL) //找尾
{
tail = tail->next;
}
tail->next = newnode; //将旧尾部与新创建的链表连接起来
}
}
//尾插的本质：原本的尾节点中，要存储新尾节点的地址关于传参二级指针的更多说明：
//[补]传参
void Func(int* ptr)
{
ptr = (int*)malloc(sizeof(int));
}
int main()
{
int* px = NULL;
Func(px);
return 0;
}
//ptr的改变不会影响px
void Func2(int** pptr)
{
**pptr = (int*)malloc(sizeof(int));
}
int main()
{
int* px = NULL;
Func2(&px);
free(px);
return 0;
}
//形参为二级指针pptr，接收一级指针px的地址
//此时改变pptr可影响px
//这其实是c语言的一种缺陷，在c++中并没有如此麻烦
//本博客旨在更好地展示和还原底层，故选用c语言模拟实现4、头插
创建一个SLTPushFront()函数，因对链表的头节点本身和插入数据进行操作，故参数为头节点的二级指针和待插入的数据；因无须返回值，故返回类型为空。
创建一个新节点后，将新节点与原先的头节点连接，使新节点成为新的头节点。
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
newnode->next = *pphead; //将新节点的next指针指向原先的头节点，使两者连接起来
*pphead = newnode; //头节点的二级指针置为新节点指针
}5、尾删
创建一个SLTPopBack()函数，因对链表的头节点本身进行操作，故参数为头节点的二级指针；因无须返回值，故返回类型为空。
要进行尾删，就必须先找到尾，再尾删。
void SLTPopBack(SLTNode** pphead)
{
//检查链表是否为空
assert(pphead);
assert(*pphead);
//若不为空，
//情况1：只有一个节点
//情况2：有多个节点
//故：
if ((*pphead)->next == NULL) //头节点的next指针为空，则说明链表当前只有一个节点
{
free(*pphead);
*pphead = NULL;
}
else
{
//找尾
SLTNode* tail = *pphead;
while (tail->next->next != NULL) //当前节点的下下个节点为空时，就找到尾了
{
tail = tail->next;
}
free(tail->next); //释放tail的下一个节点（真正的尾节点）
tail->next = NULL;
}
}
//注：
//tail->next->next为空则停止找尾、释放tail->next，
//这样写是为了控制链表的边界和相关节点的指针6、头删
创建一个SLTPopFront()函数，因对链表的头节点本身进行操作，故参数为头节点的二级指针；因无须返回值，故返回类型为空。
要进行头删，就必须先将第二个节点设为新的头节点，再删除原先的头节点。
void SLTPopFront(SLTNode** pphead)
{
assert(*pphead != NULL);
SLTNode* first = *pphead; //先将头节点储存在first变量
*pphead = first->next; //再将first变量的下一个节点（即头节点的下一个节点）设为新的头节点
free(first); //释放原先的头节点
first = NULL;
}
7、查找
创建一个SLTFind()函数，因对链表的头节点本身进行操作，故参数为头节点的指针；因需返回要查找的数据所在节点的地址，故返回类型为SLTNode*。
查找数据实则是查找数据所在的节点。遍历链表逐个节点匹配即可。
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) //因无须修改节点，故此时不用传二级指针了
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x) //从头节点开始，逐个节点匹配要查找的数据
{
return cur; //找到后，返回要查找数据所在的当前节点的地址
}
cur = cur->next;
}
return NULL; //遍历链表后还没找到，就返回空
}8、pos前插入
创建一个SLTInsert()函数，因对链表的头节点本身、要插入的节点位置和插入数据进行操作，故参数为头节点的二级指针、待插入节点位置的指针和待插入的数据；因无须返回值，故返回类型为空。
若pos位置为头节点，则直接复用头插即可；若不为头节点，则先遍历链表找到pos位置，再创建一个新节点插入pos位置前。
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pos); //此处链表不可为空，最好加断言
if (pos == *pphead)
{
SLTPushFront(pphead, x); //若插入的位置为头节点，直接复用头插即可
}
else //不为头节点则遍历链表，寻找待插入节点
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuySLTNode(x); //找到后，插入创建的新节点
prev->next = newnode;
newnode->next = pos;
}
}9、pos处删除
创建一个SLTErase()函数，因对链表的头节点本身、要删除的节点位置进行操作，故参数为头节点的二级指针和待删除节点位置的指针；因无须返回值，故返回类型为空。
若pos位置为头节点，直接复用头删即可；若不为头节点，则先遍历链表找到pos位置，找到后，将pos的前一个节点和pos的后一个节点连接，再删除pos节点。
（以下代码为“找到pos的前一个节点而非pos节点”，是因为这样方便控制变量和调整链表）
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
assert(*pphead); //若pos不为空，则*pphead基本不为空，故其实此时断不断皆可
if (*pphead == pos)
{
SLTPopFront(pphead); //若删除的位置为头节点，直接复用头删即可
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next; //不为头节点则遍历链表，寻找pos节点的前一个节点
}
prev->next = pos->next; //找到后，将pos的前一个节点和pos的后一个节点连接
free(pos); //再释放pos
//pos = NULL;//此后pos不再使用，置空与否皆可
}
}10、pos后插入
创建一个SLTInsertAfter()函数，因对要插入的节点位置和插入数据进行操作，故参数为待插入节点位置的指针和待插入的数据；因无须返回值，故返回类型为空。
创建一个新节点，将其连接在pos节点与pos的下一个节点之间即可。
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos->next; //将pos的下一个节点，赋给创建的新节点的next指针
pos->next = newnode; //然后将新节点赋给pos节点的next指针
//从而将新节点插入在pos节点与pos的下一个节点之间
}11、pos后删除
创建一个SLTEraseAfter()函数，因对要删除的节点进行操作，故参数为待删除节点的指针；因无须返回值，故返回类型为空。
将pos节点和pos的下下节点连接起来，再删除pos的下一个节点即可。
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);
SLTNode* del = pos->next; //将pos的下一个节点地址用del变量存起来
pos->next = del->next; //将del的下一个节点（即pos的下下个节点）赋给pos的next指针
//相当于连接pos节点和pos的下下个节点
free(del); //释放del指向的节点（即pos的下个节点）
del = NULL; //del原本代表的值仍可能使用，故此处需置空
}
12、销毁链表
创建一个SLTDestroy()函数，因对链表的头节点本身进行操作，故参数为头节点的二级指针；因无须返回值，故返回类型为空。
遍历链表，将逐个节点释放即可。
void SLTDestroy(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead; //cur变量代替跑腿
while (cur) //将逐个节点释放
{
SLTNode* tmp = cur->next; //将cur的下一个节点用tmp暂时存起来，
free(cur);
cur = tmp; //释放cur所指的当前节点后，又赋给cur
//方便后续cur继续向后移动
}
*pphead = NULL; //全部释放结束后，将头节点置空
}· 一些小tips
1、关于是否二级指针传参：只访问链表的时候传一级指针即可，无须传二级指针；但调整改动链表的时候，须传二级指针。
2、关于访问或遍历链表：一般通过一个代替跑腿（初始值为头节点的指针）的结构指针变量。
· 代码汇总
SList.h
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
void SLTPrint(SLTNode* phead);
void SLTPushBack(SLTNode** pphead,SLTDataType x);
SLTNode* BuySLTNode(SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
void SLTEraseAfter(SLTNode* pos);
void SLTDestroy(SLTNode** pphead);SList.c
#include"SList.h"
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while(cur!=NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
SLTNode* BuySLTNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
void SLTPopFront(SLTNode** pphead)
{
assert(*pphead != NULL);
SLTNode* first = *pphead;
*pphead = first->next;
free(first);
first = NULL;
}
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pos);
if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuySLTNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
assert(*pphead);
if (*pphead == pos)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);
SLTNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
void SLTDestroy(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* tmp = cur->next;
free(cur);
cur = tmp;
}
*pphead = NULL;
}· 带头双向循环链表
带头双向循环链表又简称双向链表，与单链表最大的区别是，节点与节点之间首尾相连。
除了当前节点数据元素之外，它还有两个结构体成员，指向上一个节点的指针和指向下一个节点的指针，首尾相连的特性也是通过这两个结构体成员实现的。
同时，它还拥有一系列通过函数实现的接口，如下：
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
LTDataType data;
}LTNode;
LTNode* BuyListNode(LTDataType x); //动态申请一个新节点
LTNode* LTInit(); //创建一个只有头节点的双向链表
void LTPrint(LTNode* phead); //打印双向链表
bool LTEmpty(LTNode* phead); //验空
void LTPushBack(LTNode* phead, LTDataType x); //尾插
void LTPopBack(LTNode* phead); //尾删
void LTPushFront(LTNode* phead, LTDataType x); //头插
void LTPopFront(LTNode* phead); //头删
void LTInsert(LTNode* pos, LTDataType x); //pos处插入
void LTErase(LTNode* pos); //pos处删除
LTNode* LTFind(LTNode* phead, LTDataType x); //查找
void LTDestroy(LTNode* phead); //销毁链表1、动态申请一个节点
LTNode* BuyListNode(LTDataType x) //传入数据元素x来创建新节点
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)
{
perror("malloc fail");
return NULL;
}
//动态申请空间后，将数据变量data、指向上一个节点的指针prev
//和指向下一个节点的指针next，分别初始化为空和传入的数据元素x
node->next = NULL;
node->prev = NULL;
node->data = x;
return node;
}2、创建一个只有头节点的双向链表
LTNode* LTInit()
{
LTNode* phead = BuyListNode(-1); //暂时以数据元素-1创建一个头节点
//因为是双向链表，故需首尾相连
//将头节点与自己首尾相连
phead->next = phead;
phead->prev = phead;
return phead;
}3、打印双向链表
void LTPrint(LTNode* phead)
{
assert(phead);
printf("<=head=>"); //先打印“头”
LTNode* cur = phead->next;
while (cur != phead) //遍历链表，逐个节点地打印数据
{
printf("%d <=>", cur->data);
cur = cur->next;
}
printf("\n");
}4、验空
bool LTEmpty(LTNode* phead) //返回值为真/假（为空/非空），故返回类型为bool
{
assert(phead);
return phead->next == phead; //当头节点的next指针仅指向头节点，说明链表为空
}5、pos位置（前）插入
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* newnode = BuyListNode(x);
//将新节点连接在pos前的节点与当前pos位置的节点之间
//新节点将取代原pos位置的节点占在pos位置，原pos位置的节点成为当前pos位置的下一个节点
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}6、pos位置删除
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* p = pos->prev;
LTNode* n = pos->next;
//将pos前后连接，然后释放pos
p->next = n;
n->prev = p;
free(pos);
//pos=NULL;
}7、尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead); //phead不可能为空，为空必然是传错了
LTNode* newnode = BuyListNode(x); //与单链表类似，创建一个新节点然后尾插
LTNode* tail = phead->prev;
//将新节点与双向链表的尾部连接起来
tail->next = newnode; //尾的next接新节点
newnode->prev = tail; //新节点的prev接尾
newnode->next = phead; //新节点的next接头
phead->prev = newnode; //头的prev接新节点
}优化，复用LTInsert()：
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTInsert(phead, x);
}8、尾删
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead)); //链表不为空，尾删才有意义
LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev; //这样写是为了方便控制
//将尾的上一个节点与头节点相接
tailPrev->next = phead;
phead->prev = tailPrev;
//然后释放尾节点
free(tail);
tail = NULL;
}优化，复用LTErase ():
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTErase(phead->prev);
}9、头插
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = BuyListNode;
LTNode* first = phead->next;
//将新节点连接在原头节点与其下一个节点之间
phead->next = newnode;
newnode->prev = phead;
newnode->next = first;
first->prev = newnode;
}
//这里头插是插入在头后面的位置，否则与尾插效果重复了优化，复用LTInsert()：
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTInsert(phead->next, x);
}10、头删
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTErase(phead->next); //复用LTErase()
}11、查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}12、销毁链表
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
//从头节点的下一个节点开始遍历链表，逐个释放
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
//最终，释放头节点
free(phead);
//phead=NULL;
}· 代码汇总
List.h
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
LTDataType data;
}LTNode;
LTNode* BuyListNode(LTDataType x);
LTNode* LTInit();
void LTPrint(LTNode* phead);
bool LTEmpty(LTNode* phead);
void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);
LTNode* LTFind(LTNode* phead, LTDataType x);
void LTDestroy(LTNode* phead);List.c
#include"list.h"
LTNode* BuyListNode(LTDataType x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)
{
perror("malloc fail");
return NULL;
}
node->next = NULL;
node->prev = NULL;
node->data = x;
return node;
}
LTNode* LTInit()
{
LTNode* phead = BuyListNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
void LTPrint(LTNode* phead)
{
assert(phead);
printf("<=head=>");
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d <=>", cur->data);
cur = cur->next;
}
printf("\n");
}
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
}
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTInsert(phead, x);
}
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTErase(phead->prev);
}
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
assert(!LTEmpty(phead));
LTInsert(phead->next, x);
}
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTErase(phead->next);
}
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* newnode = BuyListNode(x);
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* p = pos->prev;
LTNode* n = pos->next;
p->next = n;
n->prev = p;
free(pos);
}
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}[补] 顺序表和链表的区别
ps：缓存利用率可参考存储体系结构以及局部原理性。
