©2020-2024 ioDraw All rights reserved,
Privacy Policy
双向循环链表是最优链表，能补齐单链表的缺点，是个结构复杂，操作简单的链表。其插入和删除节点的时间复杂度是O(1)。
双向链表：
和单链表不同的是双向链表有两个指针，一个指向下一个节点，一个指向上一个节点
typedef int LTDataType; typedef struct ListNode { LTDataType _data; struct
ListNode* _next; struct ListNode* _prev; }ListNode;
PS：一般建立此链表，要使用哨兵位来简化操作，链表的哨兵位的_pre指向尾节点，尾结点是_next指向哨兵位。
打印链表：
因为此链表尾结点没有置空，所以无法判断尾结点。但是因为其哨兵位不存数据，所以可以判断节点是否为哨兵位来退出循环。
void ListPrint(ListNode* pHead) { assert(pHead); ListNode* cur = pHead->_next;
//这里传入哨兵位的下一个 while (cur!=pHead) { printf("%d -> ",cur->_data); cur =
cur->_next; } printf("head\n"); }
数据插入：
因为其使用了哨兵位，哨兵位的下一个节点才是头节点，不用改动头节点，所以不用使用二级指针。所以这里插入节点时候先申请一个哨兵位，建立链表。
ListNode* ListCreate() { ListNode* newNode =
(ListNode*)malloc(sizeof(ListNode)); if (!newNode) { perror("申请失败\n"); return
NULL; } newNode->_next = newNode; newNode->_prev = newNode; return newNode; }
PS：只有一个节点的时候，要自己指向自己，这样会方便后面的操作。
插入节点：
架设已经有一段链表，要在P节点前面插入一个新节点newNode。
这里双向链表的优势就体现出来了，往节点前面插入的时候不用遍历链表，因为前面一个节点就连接在 p 前面 (p->_pre) ，直接就可以连接。
void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* newNode
= (ListNode*)malloc(sizeof(ListNode)); newNode->_data = x; ListNode* cur = pos;
ListNode* pre = pos->_prev; pre->_next = newNode; newNode->_prev = pre;
newNode->_next = pos; pos->_prev = newNode; }
PS：这里操作的时候可以直接把上一个节点保存起来，这样就不用担心连接时候的顺序问题。如果不保存起来，一定要注意连接顺序。
如果链表为NULL只有一个哨兵位时，因为其是自己指向自己，所以连接的时候自然也可以使用此函数
这哨兵位的下一个和上一个节点都是指向newNode，而newNode的下一个和上一个节点都是指向哨兵位。
头部插入节点：
前面先写了插入链表，是因为头部插入链表可以直接复用函数，这里链表的头节点是哨兵位的下一个节点，传入此节点就相当于在头部插入节点。
void ListPushFront(ListNode* pHead, LTDataType x) { assert(pHead);
ListInsert(pHead->_next,x); }
尾部插入节点：
这里链表的尾结点就在哨兵位的前面，所以在哨兵位前面插入节点，就相当于在尾插节点，也可以直接复用插入函数。
void ListPushBack(ListNode* pHead, LTDataType x) { assert(pHead);
ListInsert(pHead,x); }
判断链表是否为空：
因为哨兵位不存数据，所以如果哨兵位的下一个就是自己，那么就说明链表为空。
bool ListEmtpy(ListNode* head) { //如果下一个节点是自己那么其就是空链表。 assert(head); return
head->_next==head; }
删除节点：
把要删除的节点的上一个节点，和下一个节点连接起来，然后释放节点就行了。
void ListErase(ListNode* pos) { assert(pos); ListNode* pre = pos->_prev;
ListNode* next = pos->_next; pre->_next = next; next->_prev = pre; free(pos); }
头部删除：
和前面插入一样，可以直接复用删除节点的函数，删除哨兵位的下一个节点就是删除链表头节点。
void ListPopFront(ListNode* pHead) { assert(pHead); assert(!ListEmtpy(pHead));
ListErase(pHead->_next); }
PS：注意要判断一下链表是不是为NULL。
尾部删除：
还是跟尾插一样，删除哨兵位前面的节点就是链表的尾部删除。
void ListPopBack(ListNode* pHead) { assert(pHead);
assert(!ListEmtpy(pHead));//如果链表为NULL,返回 ListErase(pHead->_prev); }
查找节点位置：
跟前面打印链表一样，遍历链表的时候不好找尾节点，所以判断是否遍历到了哨兵位，如果到了说明没找到数据，就退出循环返回NULL。
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; }
删除链表：
删除链表也可以复用删除节点函数，只不过是把链表的所有节点都删除了。
void ListDestory(ListNode* pHead) { assert(pHead); ListNode* cur =
pHead->_next; while (cur!=pHead) { ListNode* temp = cur; cur = cur->_next;
free(temp); } free(pHead); }
拓展：
顺序表优点：下标随机访问、cup高速缓冲命中率高（物理空间连续）
顺序表缺点：头部插入或者中间插入数据效率低，扩容消耗性能，存在空间的浪费。
链表优点：任意位置插入和删除为O(1)，按需释放。
链表缺点：不支持随机访问。
cup高速缓冲命中率高：
数据存在内存中，cpu和内存交换数据时，中有一个高速缓存区，缓存区一次性读取一定字节的数据，顺序表由于物理空间连续，读取开头的地址时会把后面的数据一起带进去，这样就会减少遍历的时间。而链表物理空间不连续，遍历需要的时间就会大一点。