前言
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的链表的结构总共有8种，我们这里来进行带头双向循环链表的增删查改实现
双向循环链表的优势是什么？ 双向循环链表每个节点都有两个指针分别指向前一个节点和后一个节点（头节点（也叫哨兵位节点）和尾节点又相互链接），所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点，而且在实际使用的链表数据结构中，都是用带头双向循环链表来单独存储数据。 对于增删操作的时间复杂度为O(1).
对双向链表的理解
双向链表定义两个指针（跟单链表的区别），分别指向前驱节点和后继节点
typedef int LTDataType; typedef struct ListNode { LTDataType _data; struct ListNode* _next; struct ListNode* _prev; }ListNode;
图示：
代码实现
函数声明
#include<stdio.h> #include<stdlib.h> #include<assert.h> // 带头+双向+循环链表增删查改实现 typedef int LTDataType; typedef struct ListNode { LTDataType _data; struct ListNode* _next; struct ListNode* _prev; }ListNode; // 创建返回链表的头结点. ListNode* ListCreate(); // 双向链表销毁 void ListDestory(ListNode* pHead); // 双向链表打印 void ListPrint(ListNode* pHead); // 双向链表尾插 void ListPushBack(ListNode* pHead, LTDataType x); // 双向链表尾删 void ListPopBack(ListNode* pHead); // 双向链表头插 void ListPushFront(ListNode* pHead, LTDataType x); // 双向链表头删 void ListPopFront(ListNode* pHead); // 双向链表查找 ListNode* ListFind(ListNode* pHead, LTDataType x); // 双向链表在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x); // 双向链表删除pos位置的节点 void ListErase(ListNode* pos);
代码实现
#include "List.h" //动态申请节点 ListNode* ListCreate(LTDataType x) { ListNode* node = (ListNode*)malloc(sizeof(ListNode)); if (node == NULL) { perror("malloc fail!"); exit(-1); } node->_data = x; node->_next = NULL; node->_prev = NULL; return node; } //双向链表销毁 void ListDestory(ListNode* pHead) { assert(pHead); ListNode* cur = pHead->_next; while (cur != pHead) { ListNode* next = cur->_next; free(cur); cur = next; } free(pHead); //记得对头结点指向空间释放，若要对头结点置空需要传入双指针 } //双向链表打印 void ListPrint(ListNode* pHead) { assert(pHead); ListNode* cur = pHead->_next; while (cur != pHead) { printf("%d ", cur->_data); cur = cur->_next; } printf("\n"); } //双向链表尾插 void ListPushBack(ListNode* pHead, LTDataType x) { assert(pHead); ListNode* newnode = ListCreate(x); newnode->_prev = pHead->_prev; //先对新尾节点和旧尾节点进行链接，原因是防止旧尾节点地址数据丢失 pHead->_prev->_next = newnode; newnode->_next = pHead; pHead->_prev = newnode; } //双向链表尾删 void ListPopBack(ListNode* pHead) { assert(pHead); assert(pHead->_next != pHead); //防止只有头结点 ListNode* tail = pHead->_next; ListNode* tailprev = tail->_prev; tailprev->_next = pHead; pHead->_prev = tailprev; free(tail); } //双向链表头插 void ListPushFront(ListNode* pHead, LTDataType x) { assert(pHead); ListNode* newnode = ListCreate(x); ListNode* first = pHead->_next; //这里防止只有头结点（哨兵节点） pHead->_next = newnode; newnode->_prev = pHead; newnode->_next = first; first->_prev = newnode; } //双向链表头删 void ListPopFront(ListNode* pHead) { assert(pHead); assert(pHead->_next != pHead); //防止只有头结点 ListNode* first = pHead->_next; ListNode* second = first->_next; //如果只有一个节点，second就是头结点 free(first); pHead->_next = second; second->_prev = pHead; } //双链表查找 ListNode* ListFind(ListNode* pHead, LTDataType x) { assert(pHead); ListNode* cur = pHead->_next; while (cur != pHead) { if (cur->_data == x) return cur; cur = cur->_next; } return NULL; //如果找不到 } //双向链表pos位置前插入数据 void ListInsert(ListNode* pos, LTDataType x) //实现后可以对头插尾插函数进行简化 { assert(pos); ListNode* prev = pos->_next; //先对旧pos前节点进行保存 ListNode* newnode = ListCreate(x); prev->_next = newnode; newnode->_prev = prev; newnode->_next = pos; pos->_prev = newnode; } //双向链表删除pos位置节点 void ListErase(ListNode* pos) { assert(pos); ListNode* prev = pos->_prev; ListNode* next = pos->_next; free(pos); prev->_next = next; next->_prev = prev; }
对于插入节点函数，操作时需将上一个节点prev保存起来，避免链接时的顺序问题，如果链表是只有一个哨兵位，则是实现newnode节点和哨兵位节点链接。 当然实现了插入节点函数后，对于头插和尾插就可以复用此函数了
修改后：
void ListPushFront(ListNode* pHead, LTDataType x) { assert(pHead); ListInsert(pHead->_next,x); } void ListPushBack(ListNode* pHead, LTDataType x) { assert(pHead); ListInsert(pHead,x); }
本节完
