一、双向链表介绍
双向链表（Doubly Linked List）是一种常见的数据结构，在单链表的基础上增加了向前遍历的功能。与单向链表不同，双向链表的每个节点除了包含指向下一个节点的指针外，还包含指向前一个节点的指针。
作用和原理：
（1）插入和删除操作：由于双向链表中每个节点都有指向前一个节点的指针，所以在双向链表中进行插入或删除操作时，相对于单向链表更加高效。可以通过修改前后节点的指针来完成插入和删除，而无需遍历链表。
（2）双向遍历：双向链表支持从头部到尾部以及从尾部到头部的双向遍历。这在某些场景下非常有用，例如需要反向查找、删除最后一个节点等。
（3）增加了灵活性：由于每个节点都具有指向前一个节点和后一个节点的指针，双向链表在某些特定场景下更灵活。例如，需要在链表中间插入或删除节点，或者需要修改前一个节点的信息。
双向链表的原理很简单。每个节点由数据域和两个指针组成，其中一个指针指向前一个节点，一个指针指向后一个节点。头节点指向链表的第一个节点，尾节点指向链表的最后一个节点。通过调整节点之间的指针，可以在双向链表中执行插入、删除和遍历等操作。
使用场景：
（1）编辑器中的撤销和重做功能：双向链表可以用于实现撤销和重做功能，每次编辑操作都将其结果存储为一个节点，并使用指针链接起来。通过双向链表，可以方便地在撤销和重做之间进行切换。
（2）浏览器的导航历史：浏览器的导航历史可以使用双向链表来保存已访问的页面，每个页面作为一个节点，并使用指针链接起来，以便进行前进和后退操作。
（3）实现LRU缓存替换算法：LRU缓存中，最近最少使用的数据被淘汰，可以使用双向链表来维护缓存中的数据，最近访问的数据位于链表的头部，最久未访问的数据位于链表的尾部。
（4）实现双向队列：双向链表可以用于实现双向队列（Dequeue），支持在队列的两端进行插入和删除操作。
双向链表提供了更多的灵活性和功能，特别是当需要在双向遍历、频繁的插入和删除操作等场景下使用。在许多常见的数据结构和算法中都有广泛的应用。
二、代码实现
以下是使用C语言实现的完整双向链表代码，包含了链表的创建、增加、删除、修改、排序和插入等功能。代码中封装了一套完整的子函数，以方便使用。
#include
#include
// 双向链表节点结构
typedef struct Node {
int data; // 数据域
struct Node* prev; // 指向前一个节点的指针
struct Node* next; // 指向后一个节点的指针
} Node;
// 创建新节点
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Failed to allocate memory for new noden");
return NULL;
}
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
// 在链表末尾添加节点
void append(Node** head, int data) {
Node* newNode = createNode(data);
if (newNode == NULL) {
return;
}
if (*head == NULL) {
*head = newNode;
} else {
Node* current = *head;
while (current->next != NULL) { // 找到链表末尾
current = current->next;
}
current->next = newNode;
newNode->prev = current;
}
}
// 在链表头部添加节点
void prepend(Node** head, int data) {
Node* newNode = createNode(data);
if (newNode == NULL) {
return;
}
if (*head == NULL) {
*head = newNode;
} else {
newNode->next = *head;
(*head)->prev = newNode;
*head = newNode;
}
}
// 在指定位置插入节点
void insert(Node** head, int data, int position) {
if (position < 0) {
printf("Invalid positionn");
return;
}
if (position == 0) {
prepend(head, data);
return;
}
Node* newNode = createNode(data);
if (newNode == NULL) {
return;
}
Node* current = *head;
int count = 0;
while (count next;
count++;
}
if (current == NULL) {
printf("Invalid positionn");
free(newNode);
return;
}
newNode->next = current->next;
newNode->prev = current;
if (current->next != NULL) {
current->next->prev = newNode;
}
current->next = newNode;
}
// 删除指定位置的节点
void removeAt(Node** head, int position) {
if (*head == NULL) {
printf("List is emptyn");
return;
}
if (position next;
if (*head != NULL) {
(*head)->prev = NULL;
}
free(current);
return;
}
while (count next;
count++;
}
if (current == NULL) {
printf("Invalid positionn");
return;
}
current->prev->next = current->next;
if (current->next != NULL) {
current->next->prev = current->prev;
}
free(current);
}
// 修改指定位置的节点值
void modify(Node* head, int position, int data) {
Node* current = head;
int count = 0;
while (count next;
count++;
}
if (current == NULL) {
printf("Invalid positionn");
return;
}
current->data = data;
}
// 对链表进行排序
void sort(Node** head) {
if (*head == NULL) {
printf("List is emptyn");
return;
}
Node* current = *head;
Node* temp = NULL;
int swapped;
do {
swapped = 0;
current = *head;
while (current->next != NULL) {
if (current->data > current->next->data) {
int tmp = current->data;
current->data = current->next->data;
current->next->data = tmp;
swapped = 1;
}
current = current->next;
}
temp = current;
} while (swapped);
}
// 打印链表
void printList(Node* head) {
if (head == NULL) {
printf("List is emptyn");
return;
}
Node* current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("n");
}
// 释放链表内存
void freeList(Node** head) {
if (*head == NULL) {
return;
}
Node* current = *head;
Node* next = NULL;
while (current != NULL) {
next = current->next;
free(current);
current = next;
}
*head = NULL;
}
int main() {
Node* head = NULL;
append(&head, 5);
append(&head, 3);
prepend(&head, 9);
insert(&head, 7, 1);
removeAt(&head, 2);
modify(head, 0, 2);
sort(&head);
printList(head);
freeList(&head);
return 0;
}
代码里实现了创建双向链表、在链表末尾添加节点、在链表头部添加节点、在指定位置插入节点、删除指定位置的节点、修改指定位置的节点值、对链表进行排序、打印链表及释放链表内存等功能。
三、思路讲解
代码里定义了一个双向链表节点结构，包含数据域（data）、指向前一个节点的指针（prev）和指向后一个节点的指针（next）。
typedef struct Node {
int data;
struct Node* prev;
struct Node* next;
} Node;
（1）createNode函数用于创建新节点。分配内存以存储节点，并检查内存分配是否成功。设置节点的数据域为传入的数据，并将前一个节点和后一个节点的指针都设置为NULL。最后，返回新创建的节点的指针。
（2）append函数用于在链表末尾添加节点。首先调用createNode函数创建一个新节点。如果头节点为空，则将新节点设置为头节点。否则，遍历链表直到找到最后一个节点，将新节点连接到最后一个节点的下一个位置，并设置新节点的prev指针指向最后一个节点。
（3）prepend函数用于在链表头部添加节点。首先，调用createNode函数创建一个新节点。如果头节点为空，则将新节点设置为头节点。否则，将新节点的next指针指向当前的头节点，将当前头节点的prev指针指向新节点，然后将新节点设置为头节点。
（4）insert函数用于在指定位置插入节点。首先，检查插入位置是否合法。如果插入位置为0，则调用prepend函数在链表头部插入节点。否则，调用createNode函数创建一个新节点，然后遍历链表直到找到插入位置前一个节点，将新节点插入到这两个节点之间，即将新节点的next指针指向前一个节点的next指针所指向的节点，将新节点的prev指针指向前一个节点，然后更新新节点两侧节点的指针。
（5）removeAt函数用于删除指定位置的节点。首先，检查链表是否为空。如果链表为空，则输出相应的提示信息。如果要删除的位置为0，即删除头节点，需要特殊处理，即将头节点的下一个节点设置为新的头节点，并将新的头节点的prev指针设置为NULL。否则，遍历链表直到找到要删除的节点，将要删除节点的前一个节点的next指针指向要删除节点的下一个节点，然后更新两侧节点的指针。
（6）modify函数用于修改指定位置的节点值。首先，遍历链表直到找到要修改的节点，然后将该节点的数据域设置为传入的新数据。
（7）sort函数用于对链表进行排序。首先，检查链表是否为空。如果链表为空，则输出相应的提示信息。使用冒泡排序算法，重复遍历链表并比较相邻节点的值，如果前一个节点的值大于后一个节点的值，则交换它们的值。重复此过程，直到链表没有发生交换为止。
（8）printList函数用于打印链表中的所有节点的值。首先，检查链表是否为空。如果链表为空，则输出相应的提示信息。遍历链表的每个节点，并输出节点中存储的数据。
（9）freeList函数用于释放链表的内存。首先，检查链表是否为空。如果链表为空，则直接返回。遍历链表的每个节点，使用free函数释放节点的内存，并将节点指针设为NULL，最后将头节点指针设为NULL。
