前言
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。
现在我们来通过代码实现带头双向循环链表，结构上虽然是链表最复杂的，但是并没有我们想象的那么困难，恰恰相反，其代码实现比较简单,话不多说，开始我们今天的主题
关于程序的三个部分前面已经说了很多次了，这里就不展开说明了，直接说一说我们要实现的功能：
代码实现
List.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int LTDataType; typedef struct ListNode { struct ListNode* next; struct ListNode* prev; LTDataType data; }LTNode; 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); bool ListEmpty(LTNode*phead); size_t ListSize(LTNode*phead); LTNode* ListFind(LTNode* phead,LTDataType x); //在pos之前插入 void ListInsert(LTNode* pos, LTDataType x); //删除pos位置 void ListErase(LTNode* pos); void ListDestory(LTNode* phead);
List.c
#include "List.h" LTNode* ListInit() { LTNode* guard = (LTNode*)malloc(sizeof(LTNode)); if (guard == NULL) { perror("malloc fail"); exit(-1); } guard->next = guard; guard->prev = guard; return guard; } LTNode* BuyListNode(LTDataType x) { LTNode* node = (LTNode*)malloc(sizeof(LTNode)); if (node == NULL) { perror("malloc fail"); exit(-1); } node->next = NULL; node->prev = NULL; node->data = x; return node; } void ListPrint(LTNode* phead) { assert(phead); printf("phead<=>"); LTNode* cur = phead->next; while (cur != phead) { printf("%d<=>", cur->data); cur = cur->next; } printf("\n"); } void ListPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyListNode(x); LTNode* tail = phead->prev; tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; } void ListPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyListNode(x); //考虑先后顺序 /*newnode->next = phead->next; phead->next->prev = newnode; phead->next = newnode; newnode->prev = phead;*/ //记录下一位，就不用考虑顺序 LTNode* first = phead->next; phead->next = newnode; newnode->prev = phead; newnode->next = first; first->prev = newnode; } void ListPopBack(LTNode* phead) { assert(phead); assert(!ListEmpty(phead)); LTNode* tail = phead->prev; LTNode* prev = tail->prev; prev->next = phead; phead->prev = prev; free(tail); tail = NULL; } void ListPopFront(LTNode* phead) { assert(phead); assert(!ListEmpty(phead)); LTNode* first = phead->next; LTNode* second = first->next; phead->next = second; second->prev = phead; free(first); first = NULL; } bool ListEmpty(LTNode* phead) { assert(phead); return phead->next == phead; } size_t ListSize(LTNode*phead) { assert(phead); size_t n = 0; LTNode* cur = phead->next; while (cur != phead) { ++n; cur = cur->next; } return n; } LTNode* ListFind(LTNode* phead, int x) { assert(phead); size_t n = 0; LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } } return NULL; } //在pos之前插入 void ListInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* prev = pos->prev; LTNode* newnode = BuyListNode(x); prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; } //删除pos位置 void ListErase(LTNode* pos) { assert(pos); LTNode* prev = pos->prev; LTNode* next = pos->next; prev->next = next; next->prev = prev; free(pos); } //可以传二级，内部置空 //一级指针外部置空 void ListDestory(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next; free(cur); cur = next; } free(phead); }
test.c
#include "List.h" //测试尾插、头插、尾删、打印 void TestList1() { LTNode* plist = ListInit(); ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPrint(plist); ListPushFront(plist, 10); ListPushFront(plist, 20); ListPushFront(plist, 30); ListPushFront(plist, 40); ListPrint(plist); ListPopBack(plist); ListPopBack(plist); ListPopBack(plist); ListPopBack(plist); ListPrint(plist); ListPopBack(plist); ListPopBack(plist); ListPopBack(plist); ListPopBack(plist); ListPrint(plist); ListPopBack(plist); ListPrint(plist); } //测试头删、销毁 void TestList2() { LTNode* plist = ListInit(); ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPrint(plist); ListPopFront(plist); ListPopFront(plist); ListPrint(plist); ListPopFront(plist); ListPopFront(plist); ListPrint(plist); ListDestory(plist); plist = NULL; } int main() { //TestList1(); TestList2(); return 0; }
这里的函数测试并没有测试完全，可以自己动手去测试，就不在这里展开了哈。
总结
我们已经系统地学过了链表和顺序表，我们应该对比一下之间的差别：
| 不同点 | 顺序表 | 链表 |
| 存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定 连续 |
| 随机访问 | 支持O(1) | 不支持：O(N) |
| 任意位置插入或者删除 元素 | 可能需要搬移元素，效率低 O(N) | 只需修改指针指向 |
| 插入 | 动态顺序表，空间不够时需要 扩容 | 没有容量的概念 |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
| 缓存利用率 | 高 | 低 |
缓存利用率参考存储体系结构 以及 局部原理性
至此，我们结束了链表的学习🌹
