目录
前言
在之前讲的链表中，有了头结点时，我们可以用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); }
