【数据结构】-- 单链表 vs 双向链表

🌈 个人主页：白子寰
🔥 分类专栏：python从入门到精通，魔法指针，进阶C++，C语言，C语言题集，C语言实现游戏👈 希望得到您的订阅和支持~
💡 坚持创作博文(平均质量分82+)，分享更多关于深度学习、C/C++，python领域的优质内容！（希望得到您的关注~） 

目录

 单链表和双向链表的比较

链表的打印

单链表

双向链表 

初始化

双向链表

开辟空间，写入新数据

单链表

双向链表

尾部插入数据

单链表

双向链表

头部插入数据

单链表 

双向链表

尾部删除数据

单链表

双向链表

头部删除数据

单链表

双向链表

查找

单链表 

双向链表 

在指定位置之前插入数据 

单链表

在指定位置之后插入数据

单链表

双向链表 

 删除指定位置数据

单链表

双向链表

删除指定位置后的数据

单链表

销毁链表

单链表

双向链表

---

 单链表和双向链表的比较

	单向链表	双向链表
指代不同	链表的链接方向是单向的，访问链表时时要顺序读取从头开始访问	每个数据的节点都有两个指针，即直接前驱和直接后驱
优点不同	单个节点创建方便，普通的线性内存通常在创建的时候就需要设定数据的大小，节点的访问方便，可以通过循环/递归的方法访问到任意数据	从双向链表中的任意一个节点开始，方便访问前驱节点和后继节点
缺点不同	增加/删除节点复杂，需要多分配一个指针存储空间	平均访问效率低于线性表，只能从头到尾遍历，只能找到后继，无法找到前驱（只能前进）

链表的打印

单链表

//链表的打印
void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}

双向链表 

//打印
void LTPrint(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->dada);pcur = pcur->next;}printf("\n");
}

初始化

双向链表

//双向链表初始化
LTNode* LTInit()
{//哨兵位设置为-1LTNode* phead = SLTBuyNode(-1);return phead;
}

开辟空间，写入新数据

单链表

//开辟空间，写入新数据
SLTNode* SLTbuyNode(SLTDatatype x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc");exit(1);}//先插入，后数据为空（后为空）newnode->data = x;newnode->next = NULL;return newnode;//返回数据
}

双向链表

//扩容，申请新节点
LTNode* SLTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//扩容if (newnode == NULL){perror("malloc");exit(1);}//数据赋值newnode->dada = x;//指向自己newnode->next = newnode->prev = newnode;return newnode;
}

尾部插入数据

单链表

//尾插
void SLTPushBack(SLTNode** pphead, SLTDatatype x)
{//传的参数不为空assert(pphead);SLTNode*newnode = SLTbuyNode(x);//链表为空，新节点作为phead//*pphead是指向第一个节点的指针if (*pphead == NULL)//头节点为空{*pphead = newnode;return;}//链表不为空，找尾节点//ptail作为尾节点SLTNode* ptail = *pphead;//先方向，后数据while (ptail->next){ptail = ptail->next;}ptail->next = newnode;
}

双向链表

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = SLTBuyNode(x);newnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}

头部插入数据

单链表 

//头插
void SLTPushFront(SLTNode** pphead, SLTDatatype x)
{//传参有效assert(pphead);//开辟空间，新数据进入SLTNode* newnode = SLTbuyNode(x);//先方向，后数据newnode->next = *pphead;*pphead = newnode;
}

双向链表

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = SLTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next = newnode;phead->prev = newnode->prev->prev;
}

尾部删除数据

单链表

//尾删
void SLTPopBack(SLTNode** pphead)
{//保证传参数据有效assert(pphead);//链表不能为空assert(*pphead);//链表不为空//链表只有一个节点if ((*pphead)->next==NULL){free(*pphead);*pphead = NULL;return;}//有多个节点SLTNode* prev = NULL;SLTNode* ptail = *pphead;while (prev->next){prev = ptail;ptail = ptail->next;}prev = NULL;//销毁尾节点free(ptail);ptail = NULL;
}

双向链表

//尾删
void LTPopBack(LTNode* phead)
{assert(phead);LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}

头部删除数据

单链表

//头删
void SLTPopFront(SLTNode** pphead)
{//保证传参有效assert(pphead);//保证链表有效assert(*pphead);//让第二个节点成为新的头SLTNode* next = (*pphead)->next;//把旧的头节点释放掉free(*pphead);*pphead = next;//第一个节点 = 原来第二个节点
}

双向链表

//头删
void LTPopFront(LTNode* phead)
{assert(phead);LTNode* del = phead->next;phead->next = del->next;del->next->prev = phead;free(del);del = NULL;
}

查找

单链表 

SLTNode* SLTFind(SLTNode** pphead, SLTDatatype x)
{//保证传参有效assert(pphead);//遍历链表SLTNode* pcur = *pphead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到return NULL;
}

双向链表 

//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->dada == x){return pcur;}pcur = pcur->next;}return NULL;
}

在指定位置之前插入数据 

单链表

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDatatype x)
{//保证传参有效assert(pphead);//保证指定位置数据有效assert(pos);//链表也不能为空assert(*pphead);//新节点，开辟新空间SLTNode* newnode = SLTbuyNode(x);//pos刚好是头节点if (newnode->next = *pphead){//头插SLTPushFront(pphead, x);return;}//pos不是头节点的情况SLTNode* prev = *pphead;if (prev->next != pos){prev = prev->next;}prev->next = newnode;newnode->next = pos;
}

在指定位置之后插入数据

单链表

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDatatype x)
{//保证目标数据有效assert(pos);//创建新节点SLTNode* newnode = SLTbuyNode(x);//先方向，后数据newnode->next = pos->next;pos->next = newnode;
}

双向链表 

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = SLTBuyNode(x);newnode->prev = pos;newnode->next = pos->next;pos->next = newnode;pos->next->prev = newnode;
}

 删除指定位置数据

单链表

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{//保证传的参数有效assert(pphead);//保证单链表有效assert(*pphead);//保证目标数据有效assert(pos);//pos刚好是头节点，没有前驱节点if (*pphead == pos){//头删SLTPopFront(pphead);return;}//pos不是头节点SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//释放prev->next = pos->next;free(pos);pos = NULL;
}

双向链表

//删除pos位置的数据
void LTErase(LTNode* pos)
{assert(pos);LTNode* del = pos;pos->prev->next = pos->next;pos->next->prev = pos->prev;free(del);del = NULL;
}

删除指定位置后的数据

单链表

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{//保证目标数据有效assert(pos);//pos->next数据有效assert(pos->next);SLTNode* del = pos->next;pos->next = pos->next->next;//释放free(del);del = NULL;
}

销毁链表

单链表

//销毁链表
void SListDesTroy(SLTNode** pphead)
{//保证传的参数有效assert(pphead);//保证链表有效assert(*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

双向链表

//销毁
void LTDesTroy(LTNode* phead)
{//哨兵位不能为空assert(phead);LTNode* pcur = phead->next;while(pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;
}

---

***********************************************************分割线*****************************************************************************
完结！！！
感谢浏览和阅读。
等等等等一下，分享最近喜欢的一句话:

“成为正确答案的第一步，相信自己会是正确答案”。

我是白子寰，如果你喜欢我的作品，不妨你留个点赞+关注让我知道你曾来过。
你的点赞和关注是我持续写作的动力！！！ 
好了划走吧。