👀个人简介：一个正在努力奋斗逆天改命的二本觉悟生
前言：上篇博客我们学习了链表的分类和头节点的初始化，那么这篇博客就给大家实现剩余的全部接口，希望大家继续坚持下去🌹🌹🌹
目录
一、双向链表的尾插
还是老样子，想要插入节点，首先要申请一个节点的空间，我们还是封装一个函数，专门用来申请节点空间
LTNode* LTBuyNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror(malloc);
exit(1);
}
(newnode)->data = x;
(newnode)->next = (newnode)->prev = newnode;
return newnode;
}List.c：
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
newnode->prev = phead->prev;//新节点prev指针指向尾节点（头节点的prev指针）
newnode->next = phead;//新节点的next指针指向头节点
phead->prev->next = newnode;//尾节点的next指针指向新节点
phead->prev = newnode;//头节点的prev指针指向新节点
}注意事项：
首先处理newnode，让newnode的prev指针指向头节点的prev指向的节点（尾节点）,newnode->next指向头节点，尾节点的next指针指向新节点，头节点的prev指针指向新节点，这样就把尾插过后的节点全部连接起来了
在测试之前，我们先写一下打印的接口：
void LTPrint(LTNode* phead)
{
LTNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d-> ", pcur->data);
pcur = pcur->next;
}
printf("\n");
}注：pcur是头节点的下一个节点，因为这里的头节点（哨兵位）是不存储任何值的！！！
test.c：
#include"List.h"
void test1()
{
//初始化，明天优化
ListNode* plist = NULL;
LTInit(&plist);
//尾插
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);
}
int main()
{
test1();
return 0;
}测试结果：
二、双向链表的头插
注意这里的头插可不是插入在哨兵位节点的前面哈，而是第一个节点的前面，一定不要搞错了
List.c：
//头插
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;
}注意事项：
先把newcode的前驱指针和后继指针指向对应位置，再处理需要用phead寻找的phead->next，最后再把phead需要处理的连上就可以了
test.c:
#include"List.h"
void test1()
{
//初始化，明天优化
ListNode* plist = NULL;
LTInit(&plist);
//尾插
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);
//头插
LTPushFront(plist, 5);
LTPrint(plist);
}
int main()
{
test1();
return 0;
}测试结果：
三、双向链表的尾删
我们需要先实现一个判空的接口，如果链表为空则不能继续删除了
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
}List.c:
//尾删
void LTPopBack(LTNode* phead)
{
assert(!LTEmpty(phead));
LTNode* del = phead->prev;
del->prev->next = phead;
phead->prev = del->prev;
free(del);
del = NULL;
}注意事项：
我们先进行一下判空，如果链表不为空继续后面的操作，首先我们需要删除的节点通过phead->prev找到，我们定义一个del，然后尾删操作受到影响的其它两个节点一个为del->prev，一个为head，把它们两个需要连的连上，再释放掉del指针就可以了
test.c:
#include"List.h"
void test1()
{
//初始化，明天优化
ListNode* plist = NULL;
LTInit(&plist);
//尾插
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);
//头插
LTPushFront(plist, 5);
LTPrint(plist);
//尾删
LTPopBack(plist);
LTPrint(plist);
}
int main()
{
test1();
return 0;
}测试结果：
四、双向链表的头删
List.c:
//头删
void LTPopFront(LTNode* phead)
{
assert(!LTEmpty(phead));
LTNode* del = phead->next;
del->next->prev = phead;
phead->next = del->next;
free(del);
del = NULL;
}
注意事项：
头删操作的思路和尾删相似，先还是判空，然后后续需要通过del记录下phead->next这个我们要删除的节点，再找到两个受到影响的节点，对应连上，最后释放掉del就可以了
test.c:
#include"List.h"
void test1()
{
//初始化，明天优化
ListNode* plist = NULL;
LTInit(&plist);
//尾插
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);
//头插
LTPushFront(plist, 5);
LTPrint(plist);
//尾删
LTPopBack(plist);
LTPrint(plist);
//头删
LTPopFront(plist);
LTPrint(plist);
}
int main()
{
test1();
return 0;
}测试结果：
五、双向链表查找
在实现指定位置之前插入以及删除之前，我们需要实现一个查找的接口，方便我们后续直接调用
List.c：
//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
LTNode* pcur = phead->next;
while (pcur!=phead)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}注意事项：
注：遍历的方法和打印是一样的，如果在遍历过程中找到了我们需要查找的数据就返回当前位置的节点，没有就返回空
test.c:
#include"List.h"
void test1()
{
//初始化，明天优化
ListNode* plist = NULL;
LTInit(&plist);
//尾插
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);
//头插
LTPushFront(plist, 5);
LTPrint(plist);
//尾删
LTPopBack(plist);
LTPrint(plist);
//头删
LTPopFront(plist);
LTPrint(plist);
//查找
ListNode*pos=LTFind(plist, 2);
if (pos)
printf("找到了\n");
else
printf("没找到\n");
}
int main()
{
test1();
return 0;
}测试结果：
六.双向链表在指定位置之后插入
我们在这里只实现指定位置之后插入，指定之前的插入大家可以下去自己动手实现一下，（代码放到补充位置了，大家可以参考）非常简单
List.c:
//在pos位置之后插入
void LTInsertAfter(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = LTBuyNode(x);
newnode->next = pos->next;
newnode->prev = pos;
pos->next = newnode;
pos->next->prev = newnode;
}注意事项：
test.c:
#include"List.h"
void test1()
{
//初始化，明天优化
ListNode* plist = NULL;
LTInit(&plist);
//尾插
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);
//头插
LTPushFront(plist, 5);
LTPrint(plist);
//尾删
LTPopBack(plist);
LTPrint(plist);
//头删
LTPopFront(plist);
LTPrint(plist);
//查找
ListNode* pos = LTFind(plist, 2);
//指定位置之后插入
LTInsert(pos, 100);
LTPrint(plist);
}
int main()
{
test1();
return 0;
}测试结果：
七.双向链表指定位置删除
List.c:
//删除pos位置节点
void LTErase(LTNode* pos)
{
assert(pos);
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
pos = NULL;
}注意事项：
先断言，后续操作思路和头删尾删也很像，这里是通过pos指针找到两个受到影响的节点，我们直接处理好这两个节点之前的关系就可以了，最后再直接释放掉pos
test.c:
#include"List.h"
void test1()
{
//初始化，明天优化
ListNode* plist = NULL;
LTInit(&plist);
//尾插
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);
//头插
LTPushFront(plist, 5);
LTPrint(plist);
//尾删
LTPopBack(plist);
LTPrint(plist);
//头删
LTPopFront(plist);
LTPrint(plist);
//查找
ListNode* pos = LTFind(plist, 2);
//指定位置之后插入
LTInsert(pos, 100);
LTPrint(plist);
//指定位置删除
LTErase(pos);
LTPrint(plist);
}
int main()
{
test1();
return 0;
}测试结果：
八.双向链表的销毁
在这里我们先来实现一下双向链表的销毁，具体的遍历操作和之前一样，我们在遍历过程中每次销毁一个节点之前先把它的下一个节点存下来，最后销毁完后利用存下来的使它来到下一个位置，具体操作代码如下：
//销毁
void LTDesTroy(LTNode* phead)
{
LTNode* pcur = (phead)->next;
while (pcur != phead)
{
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
//销毁头节点
free(phead);
phead = NULL;
}九、初始化部分优化
我们这里其实按道理来说是要用二级指针的，但是前面其它接口都用的一级，这里和初始化部分也需要统一比较好点，我们可以在测试文件中最后销毁完手动将头节点置为空就可以了
LTNode* LTInit()
{
LTNode* phead = LTBuyNode(-1);
return phead;
}十、全部代码展现
List.h：
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
LTDataType data;
//前驱指针,指向前一个指针
struct ListNode* prev;
//后继指针，指向后一个指针
struct ListNode* next;
}ListNode;
//初始化头节点
void LTInit(ListNode** pphead);
//ListNode* LTInit();
//打印
void LTPrint(ListNode* phead);
//销毁
void LTDestory(ListNode* phead);
//尾插
void LTPushBack(ListNode* phead, LTDataType x);
//头插
void LTPushFront(ListNode* phead, LTDataType x);
//尾删
void LTPopBack(ListNode* phead);
//头删
void LTPopFront(ListNode* phead);
//查找
ListNode* LTFind(ListNode* phead,LTDataType x);
//判空
bool LTEmpty(ListNode* phead);
//指定位置之后插入
void LTInsert(ListNode* pos, LTDataType x);
//指定位置删除
void LTErase(ListNode* pos);
List.c：
#include"List.h"
//头节点初始化
void LTInit(ListNode** pphead)
{
ListNode* ph = (ListNode*)malloc(sizeof(ListNode));
if (ph==NULL)
{
perror("malloc fail!");
exit(1);
}
*pphead = ph;
(*pphead)->data = -1;//随便给个不用的就行
(*pphead)->prev = *pphead;
(*pphead)->next = *pphead;
}
//头节点初始化的优化
//ListNode* LTInit()
//{
// ListNode* phead = LTBuyNode(-1);
// phead->prev = phead;
// phead->next = phead;
// return phead;
//}
//打印
void LTPrint(ListNode* phead)
{
ListNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d -> ", pcur->data);
pcur = pcur->next;
}
printf("\n");
}
//销毁
void LTDestory(ListNode* phead)
{
ListNode* pcur = phead->next;
while (pcur != phead)
{
ListNode* next = pcur->next;
free(pcur);
pcur = next;
}
free(phead);
phead =NULL;
}
//判空
bool LTEmpty(ListNode* phead)
{
assert(phead);
return phead->next == NULL;
}
ListNode* LTBuyNode(LTDataType x)
{
ListNode* newcode = (ListNode*)malloc(sizeof(ListNode));
newcode->data = x;
newcode->next =newcode;
newcode->prev =newcode;
return newcode;
}
//尾插
void LTPushBack(ListNode* phead, LTDataType x)
{
assert(phead);
//申请一个新节点
ListNode* newcode = LTBuyNode(x);
//phead->prev newcode phead
//先连newcode
newcode->prev = phead->prev;
newcode->next = phead;
//再把phead->prev的先处理掉
phead->prev->next = newcode;
phead->prev = newcode;
}
//头插
void LTPushFront(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* newcode = LTBuyNode(x);
//phead newcode phead->next
newcode->prev = phead;
newcode->next = phead->next;
phead->next->prev = newcode;
phead->next = newcode;
}
//尾删
void LTPopBack(ListNode* phead)
{
assert(!LTEmpty(phead));
ListNode* del = phead->prev;
//del->prev del phead
del->prev->next = phead;
phead->prev = del->prev;
free(del);
del = NULL;
}
//头删
void LTPopFront(ListNode* phead)
{
assert(!LTEmpty(phead));
ListNode* del = phead->next;
//phead del del->next
phead->next = del->next;
del->next->prev = phead;
free(del);
del = NULL;
}
//查找
ListNode* LTFind(ListNode* phead,LTDataType x)
{
assert(!LTEmpty(phead));
ListNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)
return pcur;
pcur = pcur->next;
}
return NULL;
}
//指定位置之后插入
void LTInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* newcode = LTBuyNode(x);
//pos newcode pos->next
newcode->prev = pos;
newcode->next = pos->next;
pos->next->prev = newcode;
pos->next = newcode;
}
//指定位置删除
void LTErase(ListNode* pos)
{
assert(pos);
//pos->prev pos pos->next
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
pos = NULL;
}test.c：
#include"List.h"
void test1()
{
//初始化
ListNode* plist = NULL;
LTInit(&plist);
////优化
//ListNode* plist = LTInit();
//尾插
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);
//头插
LTPushFront(plist, 5);
LTPrint(plist);
//尾删
LTPopBack(plist);
LTPrint(plist);
//头删
LTPopFront(plist);
LTPrint(plist);
//查找
ListNode* pos = LTFind(plist, 2);
/*if (pos)
printf("找到了\n");
else
printf("没找到\n");*/
//指定位置之后插入
LTInsert(pos, 100);
LTPrint(plist);
//指定位置删除
LTErase(pos);
LTPrint(plist);
//销毁
LTDestory(plist);
plist == NULL;
}
int main()
{
test1();
return 0;
}补充：双向链表在指定位置前插入
//在pos位置之前插入
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = LTBuyNode(x);
newnode->next = pos;
pos->prev->next = newnode;
newnode->prev = pos->prev;
pos->prev = newnode;
}十一、顺序表与链表对比：
往期回顾：
总结：在这篇博客中我们实现了双向链表的所有接口，大家下来也可以自己去尝试实现以下，可以通过画图来锻炼自己的逻辑思维，希望大家坚持下去，如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持。 🌹🌹🌹