这里最好先了解无哨兵位单向非循环链表再来看看这个链表
连接放这里:https://blog.csdn.net/m0_46343224/article/details/127725822
感谢支持哦!
1. 有哨兵位双向循环链表结构
typedef int DLLDataType; typedef struct DoubleLinkListNode { struct DoubleLinkListNode* pre; DLLDataType data; struct DoubleLinkListNode* next; }DLLNode;
循环必定要两个结点相互连接，所以有两个指针域
2. 生成一个结点
DLLNode* BuyDLLNode(DLLDataType x) { DLLNode* newnode = (DLLNode*)malloc(sizeof(DLLNode)); if (newnode == NULL) { perror("BuyDLLNode:malloc is err:"); exit(-1); } newnode->data = x; newnode->pre = NULL; newnode->next = NULL; return newnode; }
为什么两个指针域初始都指向NULL？
和单链表一样，都是为了尾部结点不需要再进行置空操作
为什么malloc？
堆区可以保留数据，栈区不可以保留数据
3. 初始化链表
DLLNode* DLLInit() { //此时的guard绝对不为NULL，因为malloc检查过了 DLLNode* guard = BuyDLLNode(-1); guard->pre = guard; guard->next = guard; return guard; }
为什么有哨兵位双向循环链表需要初始化呢？
原因：有哨兵位头节点，这个初始化就是初始化的哨兵位
为什么要自己指向自己呢？
这个问题在后面尾插的时候说明
4. 打印链表
void DLLPrint(DLLNode* guard) { assert(guard); DLLNode* cur = guard->next; //当cur等于guard时结束 while (cur != guard) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
为什么后面操作过程中需要对guard断言呢？
初始化中guard绝对不可能为NULL，否则初始化不了，有malloc检查。那么断言的意义是什么，就是防止没有初始化，而是直接guard = NULL进行传参
为什么cur == guard结束呢？
因为是循环，头尾都是相互连接的
5. 尾插
void DLLPushBack(DLLNode* guard, DLLDataType x) { assert(guard); DLLNode* newnode = BuyDLLNode(x); //找到尾结点 DLLNode* tail = guard->pre; //尾部连接新节点 tail->next = newnode; newnode->pre = tail; //头部连接 guard->pre = newnode; newnode->next = guard; }
为什么初始化要自己指向自己？
6. 尾删
void DLLPopBack(DLLNode* guard) { assert(guard); assert(guard->next != guard);//不能删除哨兵位,当只有一个哨兵位时表示链表为NULL DLLNode* tail = guard->pre; DLLNode* tailBefore = tail->pre; //尾部之前的结点和哨兵位进行连接 guard->pre = tailBefore; tailBefore->next = guard; //释放尾结点 free(tail); }
free后需不需要置空？
无需置空，tail为局部变量，出作用域后无效.并不会改变tail所在位置的指针
7. 头插
void DLLPushFront(DLLNode* guard, DLLDataType x) { assert(guard); DLLNode* newnode = BuyDLLNode(x); //记录头节点之后的第一个结点 DLLNode* guardNext = guard->next; //新节点和第一个结点连接 newnode->next = guardNext; guardNext->pre = newnode; //哨兵位和新节点连接 guard->next = newnode; newnode->pre = guard; }
8. 头删
void DLLPopFront(DLLNode* guard) { assert(guard); assert(guard->next != guard); //记录 DLLNode* cur = guard->next; DLLNode* curNext = cur->next; //哨兵位和curNext连接 guard->next = curNext; curNext->pre = guard; //释放cur free(cur); //需不需要置空? //无需置空,cur是局部变量出作用域销毁,并不改变什么 }
为什么单链表中需要传二级指针，而这里双向链表无需二级呢？
原因就是有哨兵位头节点，这几个操作并不影响哨兵位头节点的指向
9. 查找
DLLNode* DLLFind(DLLNode* guard, DLLDataType x) { assert(guard); //只有哨兵位头节点的时候找不了 //如果只有哨兵位头节点,则死循环 assert(guard->next != guard);//只有哨兵位的结点的话无法查找 DLLNode* cur = guard->next; while (cur != NULL) { if (cur->data == x) { return cur; } cur = cur->next; } //遍历完没找到返回NULL return NULL; }
10. 在pos之前插入
void DLLInsert(DLLNode* pos, DLLDataType x) { //为什么断言? //防止pos为NULL时插入 assert(pos); //记录 DLLNode* posBefore = pos->pre; //buy一个新节点 DLLNode* newnode = BuyDLLNode(x); //新节点和前一个结点连接 posBefore->next = newnode; newnode->pre = posBefore; //新结点和pos连接 newnode->next = pos; pos->pre = newnode; }
11. 删除pos位置数据
void DLLErase(DLLNode* pos) { assert(pos); //记录pos之前的结点 DLLNode* posBefore = pos->pre; //记录pos之后的结点 DLLNode* posNext = pos->next; //连接pos前后结点 posBefore->next = posNext; posNext->pre = posBefore; //释放pos free(pos); //无需置空,同样原因 }
12. 检查链表是否为NULL
int DLLSearchEmpty(DLLNode* guard) { assert(guard); //只有哨兵位头结点时为NULL链表 return guard->next == guard; }
13. 记录链表中结点个数
size_t DLLRecordSize(DLLNode* guard) { assert(guard); DLLNode* cur = guard->next; size_t size = 0; //cur返回到哨兵位时结束 while (cur != guard) { ++size; cur = cur->next; } return size; }
为什么要用这种方式，而不是每生成一个结点，guard->data++?
举例子:如果类型是char类型,范围是-128 ~ 127,不能
14. 销毁双向链表
void DLLDestroy(DLLNode* guard) { assert(guard); //链表为NULL,free掉guard DLLNode* cur = guard->next; //销毁 while (cur != guard) { DLLNode* curNext = cur->next; free(cur); cur = curNext; } //关键一步:释放掉哨兵位 free(guard); //无需置空,局部变量问题 }
这里置空必须手动在销毁之后置空
