目录
?
前言
在之前讲的链表中，有了头结点时，我们可以用O(1)的时间访问第一个结点，但对于要访问到最后一个结点，却需要O(n)的时间，因此出现了双向链表。
定义
在单链表的每个结点中，在设置一个指向其前驱结点的指针域，最后一个结点又指向头结点，头节点的前驱指针指向最后一个结点，从而构成一个回路。
?双向循环链表的构建
typedef int LTDatype;
typedef struct ListNode
{
struct ListNode* next;//后驱指针
struct ListNode* prev;//前驱指针
LTDatype data;
}ListNode;双向循环链表的初始化
ListNode* ListInit(void)
{
ListNode* phead = BuyListNode(0);
phead->next = phead;
phead->prev = phead;
return phead;
}初始化后
?新节点的创建
ListNode* BuyListNode(LTDatype x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}双向循环链表的尾插
void pushback(ListNode* phead, LTDatype x)
{
assert(phead);
ListNode* tail = phead->prev;
ListNode* newnode = BuyListNode(x);
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}双向循环链表的头插
void pushfront(ListNode* phead,LTDatype x)
{
assert(phead);
ListNode* newnode = BuyListNode(0);
ListNode* first = phead->next;
newnode->data = x;
newnode->next = first;
newnode->prev = phead;
first->prev = newnode;
phead->next = newnode;
}双向循环链表数据的逐一打印
void ListPrint(ListNode*phead)
{
ListNode* cur = phead->next;
while (cur!= phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}双向循环链表的尾删
void popback(ListNode* phead)
{
assert(phead);
assert(phead->next != phead);
ListNode* tail = phead->prev;
ListNode* tail2 = tail->prev;
phead->prev = tail2;
tail2->next = phead;
free(tail);
}双向循环链表的头删
void popfront(ListNode* phead)
{
assert(phead);
assert(phead->next != phead);
ListNode* first = phead->next;
ListNode* second = first->next;
phead->next = second;
second->prev = phead;
free(first);
}双向循环链表某数据位置的查找
ListNode* ListFind(ListNode* phead, LTDatype x)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}双向循环链表任意位置的插入
void ListInsert(ListNode* pos, LTDatype x)
{
assert(pos);
ListNode* prev = pos->prev;
ListNode* newnode = BuyListNode(0);
newnode->data = x;
newnode->next = pos;
prev->next = newnode;
newnode->prev = prev;
pos->prev = newnode;
}双向循环链表任意位置的删除
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* next = pos->next;
ListNode* prev = pos->prev;
next->prev = prev;
prev->next = next;
free(pos);
}