链表——双向循环链表 _循环链表

双向循环链表物理存储结构
双向循环链表与单链表一样，都是逻辑连续、物理不连续的存储方式，但它的效果要远远优于单链表，其结构如下：
双向循环链表首先要有一个头节点，头节点中不存放数据，真正的数据从头节点的下一个节点开始存放；然后每一个节点都有两个指针，分别指向前一个节点和后一个节点；最后头尾相连，就成了双向循环链表。
代码实现
#include#includetypedef int Type;typedef struct Node{Type data;struct Node* next;//指向下一个节点struct Node* prev;//指向前一个节点}Node;typedef struct Link{Node* head;//头节点}Link;//初始化void LinkInit(Link* L);//创建节点Node* CreateNode(Type data);//头插void HeadPush(Link* L, Type data);//尾插void TailPush(Link* L, Type data);//在pos位置前插入void LinkInsert(Node* pos, Type data);//头删void HeadPop(Link* L);//尾删void TailPop(Link* L);//删除pos位置元素void LinkDelete(Node* pos);//查找Node* LinkFind(Link* L, Type data);//打印void LinkPrint(Link* L);//销毁void LinkDestroy(Link* L);//初始化void LinkInit(Link* L){L->head = (Node*)malloc(sizeof(Node));L->head->data = http://www.kingceram.com/post/0;L->head->next = L->head;L->head->prev = L->head;}//创建节点Node* CreateNode(Type data){Node* node = (Node*)malloc(sizeof(Node));node->data = http://www.kingceram.com/post/data;node->next = NULL;node->prev = NULL;return node;}//头插void HeadPush(Link* L, Type data){/*Node* node = CreateNode(data);Node* next = L->head->next;node->next = next;L->head->next = node;next->prev = node;node->prev = L->head;*/LinkInsert(L->head->next, data);}//尾插void TailPush(Link* L, Type data){/*Node* node = CreateNode(data);Node* last = L->head->prev;last->next = node;node->next = L->head;node->prev = last;L->head->prev = node;*/LinkInsert(L->head, data);}//在pos位置前插入void LinkInsert(Node* pos, Type data){Node* node = CreateNode(data);Node* prev = pos->prev;prev->next = node;node->next = pos;pos->prev = node;node->prev = prev;}//头删void HeadPop(Link* L){if (L->head->next == L->head){return;}/*Node* cur = L->head->next;Node* next = cur->next;L->head->next = next;next->prev = L->head;free(cur);*/LinkDelete(L->head->next);}//尾删void TailPop(Link* L){if (L->head->next == L->head){return;}/*Node* last = L->head->prev;Node* prev = last->prev;L->head->prev = prev;prev->next = L->head;free(last);*/LinkDelete(L->head->prev);}//删除pos位置元素void LinkDelete(Node* pos){if (pos->next == pos){return;}Node* next = pos->next;Node* prev = pos->prev;prev->next = next;next->prev = prev;free(pos);}//查找Node* LinkFind(Link* L, Type data){Node* cur = L->head->next;while (cur != L->head){if (cur->data =http://www.kingceram.com/post/= data){return cur;}cur = cur->next;}return NULL;}//打印void LinkPrint(Link* L){Node* cur = L->head->next;while (cur != L->head){printf("%d ", cur->data);cur = cur->next;}printf("\n");}//销毁void LinkDestroy(Link* L){Node* cur = L->head->next;while (cur != L->head){Node* next = cur->next;free(cur);cur = next;}free(L->head);L->head = NULL;}
优缺点优点
比起单链表和顺序表来说，执行插入删除操作更加方便，时间复杂度均为O(1)

文章插图
缺点
不能像顺序表那样支持随机访问，结构较为复杂
没有增容的问题，直接用一个开一个
适用场景
【链表——双向循环链表】需要频繁插入删除元素