什么是双向循环链表
双向：即该节点即可以指向前一个节点，又可以指向下一个节点。
循环：节点的头指向尾，节点的尾指向头。
类型的创建
为什么要把int类型的数据进行重新命名。是为了以后修改数据类型的方便。
该结构体类型包括前驱指针，后驱指针以及数据。
typedef int ListTypeDate; typedef struct ListNode { struct ListNode* prev; struct ListNode* next; ListTypeDate val; }LNode;
创建双向循环链表的头节点(初始化)
初始化也就是给这个链表弄了一个头，该头的前驱指针和后驱指针都指向它自己。里面的值不管是多少都是一个随机的值。
LNode* BuyNewNode(ListTypeDate x) { LNode* newnode = (LNode*)malloc(sizeof(LNode)); newnode->val = x; return newnode; } LNode* InitList() { LNode* head = BuyNewNode(-1); head->prev = head; head->next = head; return head; }
该初始化的接口返回的是头节点的地址。
打印出链表里面的数据
因为是循环的，所以从链表头节点的下一个节点开始遍历打印，终止的打印的条件是遇到头节点。
void PrintList(LNode* head) { LNode* cur = head->next; while (cur != head) { printf("%d ", cur->val); cur = cur->next; } printf("\n"); }
首插，尾插，首删，尾删
首插
void ListPushFront(LNode* head, ListTypeDate x) { assert(head); LNode* newnode = BuyNewNode(x); LNode* cur = head->next; head->next = newnode; newnode->prev = head; newnode->next = cur; cur->prev = newnode; }
尾插
链表的尾就是头节点的前驱指针指向的节点。
void ListPushBack(LNode* head, ListTypeDate x) { LNode* newnode = BuyNewNode(x); LNode* tail = head->prev; head->prev = newnode; newnode->next = head; tail->next = newnode; newnode->prev = tail; }
首删
当链表中没有节点的时候不能进行删除
void ListPopFront(LNode* head) { assert(head); //链表没有节点的时候不能进行删除 assert(head->next != head); LNode* cur = head->next; LNode* curnext = cur->next; head->next = curnext; curnext->prev = head; free(cur); }
尾删
void ListPopBack(LNode* head) { assert(head); //链表没有节点的时候不能进行删除 assert(head->next != head); LNode* tail = head->prev; LNode* tailprev = tail->prev; head->prev = tailprev; tailprev->next = head; free(tail); }
pos位置前插入，pos位置删除
pos位置前插入
void ListInsert(LNode* head, LNode* pos, ListTypeDate x) { assert(head); LNode* newnode = BuyNewNode(x); LNode* posprev = pos->prev; posprev->next = newnode; newnode->prev = posprev; newnode->next = pos; pos->prev = newnode; }
pos位置删除
void ListErase(LNode* head, LNode* pos) { assert(head); assert(head->next != head); LNode* posnext = pos->next; LNode* posprev = pos->prev; posprev->next = posnext; posnext->prev = posprev; free(pos); }
利用这两个接口实现，首尾插，删。
void ListPushFront(LNode* head, ListTypeDate x) { ListInsert(head,head->next, x); } void ListPushBack(LNode* head, ListTypeDate x) { ListInsert(head,head, x); } void ListPopFront(LNode* head) { ListErase(head,head->next); } void ListPopBack(LNode* head) { ListErase(head,head->prev); }
销毁链表
void ListDestroy(LNode* head) { while (head!=head->next) { ListPopBack(head); } free(head); }
