【数据结构 · 初阶】- 带头双向循环链表

目录

1.尾插

2.初始化

3.尾删、头插、头删

4.查找，返回 pos 指针

5.pos 前插入

优化头插，直接复用

优化尾插，直接复用

6.pos 位删除

头删尾删简化

7.销毁

整体代码

List.h

List.c

Test.c

---

循环：1.尾 next 指向哨兵位的头。2.哨兵位的头的 prev 指向尾

基本结构：

typedef int LTDataType;typedef struct ListNode
{struct ListNode* prev;struct ListNode* next;LTDataType data;}LTNode;

1.尾插

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);LTNode* tail = phead->prev;//phead             tail  newnodetail->next = newnode;newnode->prev = tail;phead->prev = newnode;newnode->next = phead;
}

为什么要 assert ？
这里的 phead 是结构体指针，存放的是 plist 的值。plist 指向 malloc 的新节点。
malloc 的新节点的地址一定不为空。如果为空，就是传错了，所以要 assert

为什么不用二级指针？
改变的都是结构体的变量，用结构体指针足矣。这也是哨兵位的优势所在。

无头单向不循环（单链表）里面，要遍例来找尾；还要判断链表是否为空，如果为空，先赋值
这里就不用刻意找尾；且可以兼容空的情况，方便很多。下面是单链表的尾插

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySLTNode(x);if (*pphead == NULL){*pphead = newnode;}else{// 找尾SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}

2.初始化

目标：malloc 一个哨兵位的头节点，让 plist 指向哨兵位头节点
现象：要将头节点的地址传给 plist ，会改变 plist 的值
结论：要用二级指针，不能用一级指针

LTNode* plist = NULL;
LTInit(plist);void LTInit(LTNode** pphead);

后面的插入，删除都是改变结构体成员，用一级指针，只有这里用二级指针。
还有更好的方式：OJ 题中普遍用

List.c

LTNode* BuyListNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail");return NULL;}node->data = x;node->next = NULL;node->prev = NULL;return node;
}LTNode* LTInit()
{LTNode* phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;
}void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;printf("<=head=>");while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}printf("\n");
}void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);LTNode* tail = phead->prev;//phead             tail  newnodetail->next = newnode;newnode->prev = tail;phead->prev = newnode;newnode->next = phead;
}

Test.c

void ListTest1()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);
}

3.尾删、头插、头删

空链表不能删（只有哨兵位的头节点），所以要判断链表是否为空

bool LTEmpty(LTNode* phead)
{assert(phead);/*if (phead->next == phead){return true;}else{return false;}*/return phead->next == phead;
}

尾删

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;
}

头插

（1）2个指针的错误写法

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);phead->next = newnode;newnode->prev = phead;......
}

如果先搞这两步，就不能轻易找到原来的第一个了

（2）2个指针的正确写法

一定先处理离的远的那一边

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

（3）3个指针，顺序随便，效率更高

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);LTNode* first = phead->next; // 第三个指针first->prev = newnode;newnode->next = first;phead->next = newnode;newnode->prev = phead
}

头删

void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* first = phead->next->next;LTNode* del = phead->next;phead->next = first;first->prev = phead;free(del);del = NULL;
}

4.查找，返回 pos 指针

LTNode* LTFind(LTNode* phead, LTDataType x); // List.hLTNode* LTFind(LTNode* phead, LTDataType x) // List.c
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}void ListTest2() // Test.c
{LTNode* plist = LTInit();......LTNode* pos = LTFind(plist, 2);
}

5.pos 前插入

要配合查找使用
单链表要遍例找前一个，现在不需要这么麻烦

要用2个指针，先动离的远的，即 pos->prev 和 newnode 的链接
为高效，我们用3个指针

void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = BuyListNode(x);LTNode* prev = pos->prev; // 第3个指针prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}

优化头插，直接复用

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTInsert(phead->next, x);
}

优化尾插，直接复用

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTInsert(phead, x);
}

 遍例是从 LTNode* cur = phead->next ；开始。从逻辑上就是尾插

6.pos 位删除

配合查找使用

void LTErase(LTNode* pos)
{assert(pos);LTNode* p = pos->prev;LTNode* n = pos->next;p->next = n;n->prev = p;free(pos);//pos = NULL;
}

pos置空没用，形参改变不影响实参。
为保持接口风格一致，没有必要用二级指针，通常由使用的人在外面置空

里面变如果改变外面的话，一定有 解引用 操作

void ListTest2()
{LTNode* plist = LTInit();......LTNode* pos = LTFind(plist, 2);if (pos){LTErase(pos);pos = NULL;}LTPrint(plist);
}

LTErase 肯定不能删哨兵位的头节点
但 C语言中不好检查，所以我们暂且不做处理。删哨兵程序会挂
C++的结构好检查

头删尾删简化

void LTPopBack(LTNode* phead)
{assert(phead);LTErase(phead->prev);
}void LTPopFront(LTNode* phead)
{assert(phead);LTErase(phead->next);
}

7.销毁

void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;LTNode* next = cur->next;while (cur != phead){free(cur);cur = next;next = next->next;}free(phead);//phead = NULL;
}void ListTest2()
{LTNode* plist = LTInit();......LTDestroy(plist);plist = NULL;
}

整体代码

List.h

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>typedef int LTDataType;typedef struct ListNode
{struct ListNode* prev;struct ListNode* next;LTDataType data;}LTNode;LTNode* LTInit();void LTPrint(LTNode* phead);bool LTEmpty(LTNode* phead); // 判断链表是否为空void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);LTNode* LTFind(LTNode* phead, LTDataType x);void LTInsert(LTNode* pos, LTDataType x); // pos前插入
void LTErase(LTNode* pos); // pos位删除void LTDestroy(LTNode* phead);

List.c

#include "List.h"
LTNode* BuyListNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail");return NULL;}node->data = x;node->next = NULL;node->prev = NULL;return node;
}LTNode* LTInit()
{LTNode* phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;
}void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;printf("<=head=>");while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}printf("\n");
}bool LTEmpty(LTNode* phead)
{assert(phead);/*if (phead->next == phead){return true;}else{return false;}*/return phead->next == phead;
}void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);/*LTNode* newnode = BuyListNode(x);LTNode* tail = phead->prev;//phead             tail  newnodetail->next = newnode;newnode->prev = tail;phead->prev = newnode;newnode->next = phead;*/LTInsert(phead, x);
}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;*/LTErase(phead->prev);
}void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);/*LTNode* newnode = BuyListNode(x);LTNode* first = phead->next;first->prev = newnode;newnode->next = first;phead->next = newnode;newnode->prev = phead*/LTInsert(phead->next, x);
}//void LTPushFront(LTNode* phead, LTDataType x)
//{
//	assert(phead);
//	LTNode* newnode = BuyListNode(x);
//  // 先
//	phead->next->prev = newnode;
//	newnode->next = phead->next;
//  // 后
//	phead->next = newnode;
//	newnode->prev = phead;
//}void LTPopFront(LTNode* phead)
{assert(phead);/*assert(!LTEmpty(phead));LTNode* first = phead->next->next;LTNode* del = phead->next;phead->next = first;first->prev = phead;free(del);del = NULL;*/LTErase(phead->next);
}LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = BuyListNode(x);LTNode* prev = pos->prev;prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}void LTErase(LTNode* pos)
{assert(pos);LTNode* p = pos->prev;LTNode* n = pos->next;p->next = n;n->prev = p;free(pos);//pos = NULL;
}void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;LTNode* next = cur->next;while (cur != phead){free(cur);cur = next;next = next->next;}free(phead);//phead = NULL;
}

Test.c

#include "List.h"
void ListTest1()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTPopBack(plist);LTPopBack(plist);LTPopBack(plist);LTPopBack(plist);LTPrint(plist);LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);LTPopFront(plist);LTPopFront(plist);LTPrint(plist);
}void ListTest2()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTNode* pos = LTFind(plist, 2);LTInsert(pos, 9);LTPrint(plist);if (pos){LTErase(pos);pos = NULL;}LTPrint(plist);LTDestroy(plist);plist = NULL;
}int main()
{ListTest2();return 0;
}

本篇的分享就到这里了，感谢观看，如果对你有帮助，别忘了点赞+收藏+关注。
小编会以自己学习过程中遇到的问题为素材，持续为您推送文章