一. 结构图和哨兵位
我们先来看它的结构图
这里的结构大体如上
我们可以发现的是 这里其实是有一个哨兵位
那么什么是哨兵位呢？
哨兵位
我们可以把它理解成一个站岗的哨兵 它不存储值
它不参与任何的行动 只是负责站岗 标识一个唯一的头节点
二. 代码实现
我们还是跟以前一样 先创建三个工程文件
创建一个节点所需要的指针和值
struct List { int val; struct List* prev; struct List* next; };
还是和以前的类型定义一样 为了能够代码的复用 我们重定义下类型
typedef int ListNodeType; typedef struct ListNode { ListNodeType val; struct ListNode* prev; struct ListNode* next; }LN;
这样子如果我们想要改变双链表存储的值的话只需要改变typedef的类型就可以了
三. 初始化双链表
这里很简单 我们只需要创建一个哨兵位就可以
这个哨兵位的头尾指针都要指向自身
代码表示如下
struct ListNode* InitListNode(LN* head) { head = (struct ListNode*)malloc(sizeof(LN)); head->prev = head; head->next = head; return head; }
我们来调试下看看道理能不能初始化成功
成功！
四. 尾插数据
我们来看图
首先我们需要通过tail找到一个尾
之后通过这个尾来向后插入一个新的数据
一共有四个箭头需要链接（尾2 新节点2）
在实现这个函数之前我们首先先来写一个创造新节点的函数
struct ListNode* BuyListNode() { struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode)); return newnode; }
代码表示如上
之后我们开始找尾 插入数据
代码表示如下
void ListNodePushBack(LN* head, ListNodeType x) { assert(head); struct ListNode* newnode = BuyListNode(); struct ListNode* tail = head->prev; newnode->val = x; tail->next = newnode; newnode->prev = tail; head->prev = newnode; newnode->next= head; }
五. 打印数据
没有什么难度
代码表示如下
void ListNodePrint(LN* head) { assert(head); struct ListNode* cur = head->next; while (cur!=head) { printf("%d-> ", cur->val); cur = cur->next; } printf("NULL"); }
接下来我们试试看打印尾插的数据
我们发现没有问题
六. 尾删数据
首先我们需要找到tail之前的一个数据 我们将这个数据称之为prev
然后按照上图链接就可以
但是又一种特殊情况 如果说 head 既是头又是尾 我们这里就需要报错
因为哨兵位不可以删除
代码表示如下
void ListNodePushBack(LN* head) { assert(head); assert(head->next != head); struct ListNode* tail = head->prev; struct ListNode* prev = tail->prev; prev->next = head; head->next = prev; free(tail); }
然后效果表示如下
七. 头插数据
还是一样 我们先看图
代码表示如下
void ListNodePushFront(LN* head, ListNodeType x) { assert(head); struct ListNode* Phead = head; struct ListNode* Next = head->next; struct ListNode* newnode = BuyListNode(); newnode->val = x; Phead->next = newnode; newnode->prev = Phead; newnode->next = Next; Next->prev = newnode; }
显示效果如下
八. 头删数据
我们发现要头删除数据的话要使用三个指针
哨兵位指针
头指针
头指针的下一位
开始写代码
void ListNodePopFront(LN* head) { assert(head); assert(head->next != head); LN* Phead = head->next; LN* Next = Phead->next; head->next = Next; Next->prev = head; free(Phead); }
显示效果如下
九. 查找指定位置
这个实现起来也很简单 跟打印的思路差不多
struct ListNode* ListNodeFindPos(LN* head, ListNodeType x) { assert(head); struct ListNode* cur = head->next; while (cur!=head) { if (cur->val == x) { return cur; } cur=cur->next; } return NULL; }
如果找到return pos的位置
如果找不到我们就返回一个空指针
十. 指定位置前插入数
如图
看图敲代码
void ListNodeInsertPos(LN* Pos,ListNodeType x) { assert(Pos); LN* Prev = Pos->prev; LN* newnode = BuyListNode(); newnode->val = x; Prev->next = newnode; newnode->prev = Prev; newnode->next = Pos; Pos->prev = newnode; }
我们来看看效果
十一. 删除指定位置的数
还是一样 先看图
这里我们需要三个指针 一个前面的一个后面的
但是这里我们需要注意
Pos指针不能为空
并且Pos指针不能指向头节点
我们来看看代码
void ListNodeEasePos(LN* Pos) { assert(Pos); assert(Pos->next != Pos->prev); LN* Prev = Pos->prev; LN* Next = Pos->next; Prev->next = Next; Next->prev = Prev; free(Pos); }
我们再看看效果图怎么样
以上就是本篇博客的全部内容啦 由于博主才疏学浅 所以难免会出现纰漏
希望大佬们看到错误之后能够不吝赐教 在评论区或者私信指正 博主一定及时修正
那么大家下期再见咯
