链表——双向循环链表

双向循环链表 物理存储结构

双向循环链表与单链表一样，都是逻辑连续、物理不连续的存储方式，但它的效果要远远优于单链表，其结构如下：

双向循环链表首先要有一个头节点，头节点中不存放数据，真正的数据从头节点的下一个节点开始存放；然后每一个节点都有两个指针，分别指向前一个节点和后一个节点；最后头尾相连，就成了双向循环链表。

代码实现

#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 = 0;L->head->next = L->head;L->head->prev = L->head;
}//创建节点
Node* CreateNode(Type data)
{Node* node = (Node*)malloc(sizeof(Node));node->data = 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 == 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)

缺点

不能像顺序表那样支持随机访问，结构较为复杂

没有增容的问题，直接用一个开一个

适用场景

需要频繁插入删除元素