数据结构初阶|数据结构初阶之双向链表（C语言实现）数据结构初阶|数据结构

【数据结构初阶|数据结构初阶之双向链表（C语言实现）】接上节实现的单链表，今天更新带头循环双向链表，这个的实现还是比较简单的。
首先带头循环双向链表的接口函数其实和单链表是差不多的
首先看一下带头双向循环链表的结构是什么样的

文章图片

给出接口函数，首先要定义数据类型，一个数据加两个指针，组成结构体作为链表的元素。
接下来分别是初始化，打印，尾插，头插，尾删，头删，插入和删除

#include #include #include #includetypedef int LTDataType; typedef struct ListNode { struct ListNode* next; struct ListNode* prev; LTDataType data; }LTNode; //void ListInit(LTNode** pphead); LTNode* ListInit(); void ListPrint(LTNode* phead); void ListPushBack(LTNode* phead, LTDataType x); void ListPushFront(LTNode* phead, LTDataType x); void ListPopBack(LTNode* phead); void ListPopFront(LTNode* phead); // 在pos位置之前插入x void ListInsert(LTNode* pos, LTDataType x); //删除pos位置的节点 void ListErase(LTNode* pos);

接下来一个一个实现：
1.创建节点函数
首先应该有一个创建元素类型的函数，用来实现后续的一切操作：动态开辟在头文件定义的元素类型的一个元素，赋值给data，两个指针置空

LTNode* BuyListNode(LTDataType x) { LTNode* node = (LTNode*)malloc(sizeof(LTNode)); if (node == NULL) { perror("malloc fail"); exit(-1); } node->data = https://www.it610.com/article/x; node->next = NULL; node->prev = NULL; return node; }

2.初始化函数
这里初始化其实就是创建一个哨兵位节点，元素和链表内的元素是一样的，只不过里面的数据可给可不给。
这里还有一点就是使用返回值来初始化可以避免传二级指针。
创建一个哨兵位，将两个指针都指向自己。

LTNode* ListInit() { LTNode* phead = BuyListNode(-1); phead->next = phead; phead->prev = phead; return phead; }

3.打印函数
这里要注意的就是判断停下来的条件，因为是需要遍历的，其实就是指向phead就要停下来。

void ListPrint(LTNode* phead) { assert(phead); LTNode* cur = phead; while (cur->next != phead) { printf("%d", cur->data); cur = cur->next; } printf("\n"); }

4.尾插函数
思路非常简单啊，记住原来的尾，依次连接即可

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

5.头插函数

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

6.尾删函数
这里需要注意的就是断言的第二句，哨兵位的头节点可不能删掉

void ListPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead); LTNode* tail = phead->prev; LTNode* tailPrev = tail->prev; free(tail); tailPrev->next = phead; phead->prev = tailPrev; }

7.头删函数

void ListPopFront(LTNode* phead) { assert(plist->next); //链表不能为空 LTNode* next = phead->next; phead->next = next->next; //1 next->next->prev = phead; //2 free(next); next = NULL; }

8.插入
这个函数就是在pos位置之前插入，所以还要记住未插入前的pos的前一个位置是谁

void ListInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* prev = pos->prev; LTNode* newnode = BuyListNode(x); // prve newnode pos prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; }

9.删除
删除pos位置的节点，需要记住前后两个节点，然后链接即可