. 结构图和哨兵位
我们先来看它的结构图
这里的结构大体如上
我们可以发现的是 这里其实是有一个哨兵位
那么什么是哨兵位呢？
之前的一期我们讲过，可以看我的往期文章
二. 代码实现
我们还是跟以前一样 先创建三个工程文件
创建一个节点所需要的指针和值
typedef int LTDateType; typedef struct ListNode { struct ListNode* next; struct ListNode* prev; LTDateType date; }LTNode;
这样子如果我们想要改变双链表存储的值的话只需要改变typedef的类型就可以了
三. 初始化双链表
这里很简单 我们只需要创建一个哨兵位就可以
这个哨兵位的头尾指针都要指向自身
代码表示如下
LTNode* BuyListNode(LTDateType x) { LTNode* node = (LTNode*)malloc(sizeof(LTNode)); if (node == NULL) { perror("malloc fail"); //return NULL; exit(-1); } node->next = NULL; node->prev = NULL; node->date = x; return node; } LTNode* LTInit() { LTNode* phead = BuyListNode(-1); phead->next = phead; phead->prev = phead; return phead; }
四. 尾插数据
我们来看图
首先我们需要通过tail找到一个尾
之后通过这个尾来向后插入一个新的数据
一共有四个箭头需要链接（尾2 新节点2）
之后我们开始找尾 插入数据
代码表示如下
void LTPushBack(LTNode* phead, LTDateType x) { assert(phead); LTNode* newnode = BuyListNode(x); LTNode* tail = phead->prev; tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; /*LTInsert(phead, x);*/ }
五. 打印数据
没有什么难度
代码表示如下
void LTPrint(LTNode* phead) { assert(phead); printf("<=head=>"); LTNode* cur = phead->next; while (cur != phead) { printf("%d<=>", cur->date); cur = cur->next; } printf("\n"); }
接下来我们试试看打印尾插的数据
我们发现没有问题
六. 尾删数据
首先我们需要找到tail之前的一个数据 我们将这个数据称之为prev
然后按照上图链接就可以
但是又一种特殊情况 如果说 head 既是头又是尾 我们这里就需要报错
因为哨兵位不可以删除
代码表示如下
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; }
然后效果表示如下 
七. 头插数据
还是一样 我们先看图
代码表示如下
void LTPustFront(LTNode* phead, LTDateType x) { assert(phead); LTNode* newnode = BuyListNode(x); LTNode* first = phead->next; phead->next = newnode; newnode->prev = phead; newnode->next = first; first->prev = newnode; //不能随便换顺序 //newnode->next = phead->next; //phead->next->prev = newnode; // //phead->next = newnode; //newnode->prev = phead; /*LTInsert(phead->next, x);*/ }
显示效果如下
八. 头删数据
我们发现要头删除数据的话要使用三个指针
哨兵位指针
头指针
头指针的下一位
开始写代码
void LTPopFront(LTNode* phead) { assert(phead); assert(!LTEmpty(phead)); LTNode* first = phead->next; phead->next = first->next; first->next->prev = phead; free(first); first = NULL; }
显示效果如下
九. 查找指定位置
这个实现起来也很简单 跟打印的思路差不多
LTFind(LTNode* phead, LTDateType x) { assert(phead); LTNode* cur = phead->next; while (cur!=phead) { if (cur->date == x) { return cur; } cur = cur->next; } return NULL; }
如果找到return pos的位置
如果找不到我们就返回一个空指针
十. 指定位置前插入数
如图
看图敲代码
void LTInsert(LTNode* pos, LTDateType x) { assert(pos); LTNode* prev = pos->prev; LTNode* newnode = BuyListNode(x); newnode->next = pos; pos->prev = newnode; prev->next = newnode; newnode->prev = prev; }
我们来看看效果
十一. 删除指定位置的数
还是一样 先看图
这里我们需要三个指针 一个前面的一个后面的
但是这里我们需要注意
Pos指针不能为空
并且Pos指针不能指向头节点
我们来看看代码
void LTErase(LTNode* pos) { assert(pos); LTNode* prev = pos->prev; LTNode* next = pos->next; prev->next = next; next->prev = prev; free(pos); pos = NULL; }
我们再看看效果图怎么样
以上便是本文所有内容了，如有错误请各位大佬不吝赐教，感谢留言
