基本定义
双向链表每个元素都是一个对象，每个对象包括一个数据域和两个指针域next和prev。
我们知道，单链表可以从后往前轻松的前进，但是它很难实现后退。它一般只能从头到尾或者从尾到头。
那么当我们需要实现更加灵活的操作时，就可以使用双向链表：拥有两个指针域，一个指向前驱节点，一个指向后继节点，在操作时既可以前进也可以后退，灵活性大大提高。
双向链表的操作普遍上比单向链表简单，因为它多了一个指针域所以操作的灵活性大大提高。
初始化和定义
如果头指针指向自己，那么此时的链表就自然是一个空表，完成双向链表的初始化
LTNode* LTInit() { LTNode* phead = LTBuyNode(-1); return phead; }
定义两个指针分别指向前和后，并且定义一个数据域来存放数据
typedef int ElemType; typedef struct LTNode{ ElemType data; struct LTNode *prev;//直接前驱指针 struct LTNode *next; //直接后继指针 }LTNode,*DuLinkList;
插入
头插：在第一个有效节点之前插入，即头结点之后插入；
//头插 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = LTBuyNode(x); //phead newnode phead->next newnode->next = phead->next; newnode->prev = phead; phead->next->prev = newnode; phead->next = newnode; }
尾插：在头结点之前插入结点，最后一个有效节点之后插入
//尾插 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = LTBuyNode(x); //phead phead->prev(ptail) newnode newnode->next = phead; newnode->prev = phead->prev; phead->prev->next = newnode; phead->prev = newnode; }
在pos位置之后插入数据
//在pos位置之后插入数据 void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = LTBuyNode(x); //pos newnode pos->next newnode->next = pos->next; newnode->prev = pos; pos->next->prev = newnode; pos->next = newnode; }
删除
尾删
//尾删 void LTPopBack(LTNode* phead) { assert(phead); //链表为空：只有一个哨兵位节点 assert(phead->next != phead); LTNode* del = phead->prev; LTNode* prev = del->prev; prev->next = phead; phead->prev = prev; free(del); del = NULL; }
头结点不能跟着一起删除，要保留下来，否则就会被视为直接销毁整个表；而当只有一个头结点的时候，该表即为空表
头删
//头删 void LTPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead); LTNode* del = phead->next; LTNode* next = del->next; //phead del next next->prev = phead; phead->next = next; free(del); del = NULL; }
删除pos位置的结点
//删除pos位置的数据 void LTErase(LTNode* pos) { assert(pos); //pos->prev pos pos->next pos->next->prev = pos->prev; pos->prev->next = pos->next; free(pos); pos = NULL; }
实际上该操作就是让指定位置的前一个结点指向头结点
查找
LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* pcur = phead->next; while (pcur != phead) { if (pcur->data == x) { return pcur; } pcur = pcur->next; } return NULL; }
销毁
void LTDesTroy(LTNode* phead) { //哨兵位不能为空 assert(phead); LTNode* pcur = phead->next; while (pcur != phead) { LTNode* next = pcur->next; free(pcur); pcur = next; } //链表中只有一个哨兵位 free(phead); phead = NULL; }
遍历释放各个结点直到只有一个哨兵位，最后再释放哨兵位
双向循环链表
双向循环链表是一种特殊的双向链表，它的最后一个节点的指针指向第一个节点，形成一个环形结构。这种结构可以实现循环遍历，即从任意一个节点开始遍历整个链表，直到回到起始节点为止。
双向循环链表的特点包括：
- 最后一个节点的指针指向第一个节点，形成一个循环结构，可以实现循环遍历。
- 可以在任意节点开始遍历整个链表，不需要从头节点开始。
而实际上双向循环链表就是对于双向链表的一个优化，相当于单链表优化为循环链表，从而可以实现更多的操作。
#include <stdio.h> #include <stdlib.h> // 定义双向循环链表节点结构 typedef struct Node { int data; struct Node* prev; struct Node* next; } Node; // 初始化双向循环链表 Node* initList() { Node* head = (Node*)malloc(sizeof(Node)); head->data = -1; head->prev = head; head->next = head; return head; } // 在链表尾部插入节点 void insert(Node* head, int data) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = data; newNode->prev = head->prev; newNode->next = head; head->prev->next = newNode; head->prev = newNode; } // 打印链表元素 void printList(Node* head) { Node* current = head->next; while (current != head) { printf("%d ", current->data); current = current->next; } printf("\n"); } int main() { Node* head = initList(); insert(head, 1); insert(head, 2); insert(head, 3); printf("双向循环链表的元素为：\n"); printList(head); return 0; }
双向链表的应用场景和作用
- 需要频繁在链表中间插入或删除节点的情况：双向链表可以在O(1)的时间复杂度内完成插入或删除操作，因此适合在需要频繁插入或删除节点的场景中使用。
- 需要双向遍历链表的情况：双向链表可以方便地从头到尾或从尾到头遍历链表，因此适合在需要双向遍历链表的场景中使用。
- 需要实现栈或队列的情况：双向链表可以方便地在两端进行插入或删除操作，因此适合用来实现栈或队列。
- 需要实现LRU缓存淘汰算法的情况：LRU缓存淘汰算法中经常需要删除最近最少使用的节点，双向链表可以方便地删除尾节点，因此适合用来实现LRU缓存淘汰算法。
- 需要频繁在链表中间插入或删除节点的情况：双向链表可以在O(1)的时间复杂度内完成插入或删除操作，因此适合在需要频繁插入或删除节点的场景中使用。
- 需要双向遍历链表的情况：双向链表可以方便地从头到尾或从尾到头遍历链表，因此适合在需要双向遍历链表的场景中使用。
- 需要实现栈或队列的情况：双向链表可以方便地在两端进行插入或删除操作，因此适合用来实现栈或队列。
- 需要实现LRU缓存淘汰算法的情况：LRU缓存淘汰算法中经常需要删除最近最少使用的节点，双向链表可以方便地删除尾节点，因此适合用来实现LRU缓存淘汰算法。
