C语言如何实现带头双向循环链表

这篇文章主要介绍了C语言如何实现带头双向循环链表，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。

前言

在实际生活中最常用的就是这两种链表。无头单向非循环链表。和带头双向循环链表。
无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

1. 创建结构体

注意：typedef起作用是在第7行哦。所以第5,6还需要写struct Listnode类型。

typedef int LNDataType;typedef struct ListNode{  struct ListNode* prev;   struct ListNode* next;      LNDataType val;}LN;

2.malloc新节点

注意：需判断新开辟的节点是否为空。

//申请一个新节点LN* BuynewNode(LNDataType x){LN* newNode = (LN*)malloc(sizeof(LN));if (newNode == NULL){printf("malloc fail");exit(-1);}newNode->next = NULL;newNode->prev = NULL;newNode->val = x;return newNode;}

3.创建哨兵位节点

注意：这里因为需要改变plist指针的内容，也就是改变plist指针的指向，所以需要传递plist的地址。

一句话就是：需要改变谁的内容，就传谁的地址。

这里有一点非常巧非常妙，就是phead的后继和前驱都是指向自己（phead），这里是模仿c++STL库里的哨兵位节点。

只能佩服想出来这些东西的大神。这样设计哨兵位节点的话，后续尾插，尾删，都特别的巧妙。

test.c

LN* plist = NULL;ListNodeInit(&plist);

List.h

//初始化节点void ListNodeInit(LN** pphead){LN* newNode = BuynewNode(0);*pphead = newNode;(*pphead)->next = *pphead;(*pphead)->prev = *pphead;}

4.尾插

注意：需要断言的原因是因为，即使链表没有一个节点，那链表至少还有个头，所以phead肯定不为空。

这里没有传地址的原因是因为，你不需要改变plist的指向，你改变的是plist指向的结构体里面的值。

多个节点尾插的情况如图。

一个节点的尾插。

//尾插void ListNodePushBack(LN* phead, LNDataType x){assert(phead);LN* newNode = BuynewNode(x);LN* tail = phead->prev;tail->next = newNode;newNode->prev = tail;newNode->next = phead;phead->prev = newNode;}

5.打印

注意：因为带个头，所以cur从第二个位置开始。

//打印void ListNodePrint(LN* phead){LN* cur = phead->next;while (cur != phead){printf("%d ", cur->val);cur = cur->next;}printf("\n");}

6.尾删

注意不能删掉头结点，free掉头结点的话会造成野指针，再次访问时会造成非法访问。
所以要用assert断言不为首节点。

//尾删void ListNodePopBack(LN* phead){assert(phead);assert(phead->next != phead);LN* tail = phead->prev;LN* tailPrev = tail->prev;free(tail);tail = NULL;phead->prev = tailPrev;tailPrev->next = phead;}

7.头插

最好用next记录下一个节点。这样方便，思路清晰

//头插void ListNodePushFront(LN* phead, LNDataType x){assert(phead);LN* newNode = BuynewNode(x);LN* next = phead->next;phead->next = newNode;newNode->prev = phead;newNode->next = next;next->prev = newNode;}

8.在指定位置pos的前面进行插入

一般情况

只有一个节点时。

两种情况都适用以下代码。

//指定位置前插入，极限是头插void ListNodeInsert(LN* pos, LNDataType x){if (pos == NULL){printf("没有找到这个数\n");return;}LN* newNode = BuynewNode(x);LN* tailPrev = pos->prev;tailPrev->next = newNode;newNode->prev = tailPrev;newNode->next = pos;pos->prev = newNode;}

9. 删除指定位置pos节点

正常情况

极限尾删

两种情况都适用以下代码。

//指定位置删除void ListNodeErease(LN* phead, LN* pos){if (pos == phead || pos == NULL){printf("pos指向头，或为空\n");return;}LN* posPrev = pos->prev;LN* posNext = pos->next;posPrev->next = posNext;posNext->prev = posPrev;free(pos);pos = NULL;}

10.销毁链表

注意：这里相当于malloc用完之后的free。否则会造成内存泄漏。
cur可以置空，但用处不大，因为cur是形参，形参是实参的一份临时拷贝，形参置空并不能改变实参。外部的实参还是依旧能非法访问到cur所指向的空间。

//链表销毁void ListNodeDestroy(LN* phead){assert(phead);LN* cur = phead->next;LN* next = cur->next;while (cur != phead){next = cur->next;free(cur);cur = NULL;cur = next;}free(phead);phead = NULL;}

感谢你能够认真阅读完这篇文章，希望小编分享的“C语言如何实现带头双向循环链表”这篇文章对大家有帮助，同时也希望大家多多支持编程网，关注编程网其他教程频道，更多相关知识等着你来学习!