【数据结构C/C++】双向链表的增删改查

对我个人而言，在开发过程中使用的比较多的就是双向链表了。
很多重要的代码优化都会使用到基于双向链表实现的数据机构。
比如我们常用的HashMap，我们知道Key其实是无序存放的，
而LinkedHashMap底层使用HashMap+双向链表的方式实现了对key的有序遍历。

双向链表的一些重要特点和优点：

双向遍历：
双向链表具有两个指针，一个指向前一个节点（前驱），一个指向后一个节点（后继）。这使得在链表中的任何位置都可以轻松地进行双向遍历，而不仅仅是单向遍历。

前向和后向操作： 可以在双向链表中执行前向和后向操作，这意味着可以轻松地在链表中的任何位置插入、删除或修改节点。

插入和删除效率高： 相对于单向链表，双向链表在某些情况下可以更高效地进行插入和删除操作，因为可以通过两个方向的指针更快地访问前后节点。

反向遍历： 在某些情况下，需要以相反的顺序遍历链表。双向链表使得反向遍历变得容易，无需重新构建链表。

实现双端队列： 双向链表还可以用于实现双端队列（Deque），这是一种允许在两端进行插入和删除操作的数据结构。

尽管双向链表提供了上述优点，但也需要额外的内存来存储每个节点的前向指针，这会增加内存开销。此外，由于维护前向指针和后向指针的关系，代码的实现可能相对复杂一些。

双向链表相对于单链表的区别在于，单链表只有一个指向下一个节点的指针域，而双向链表有两个。因此再管理指针上，需要更多的去注意。
不过原理都大差不差，只不过是再添加和删除一个节点的时候，需要记住去管理当前节点的前后指针域，使得其最终依旧能连起来。
因此我认为在学习双向链表的时候，比较推荐先再草纸上画出大概的思路。
比如再链表中间某个位置添加一个元素，那么应该遍历到当前元素前一个位置就停下，然后去创建新节点，并且将新节点的前后指针域指向当前节点和当前节点的下一个节点。
以此类推，删除也差不多。
所以，继续 show u my code。

C

#include <stdio.h>
#include <stdlib.h>// 定义双向链表节点结构
struct Node {int data;struct Node* prev;struct Node* next;
};// 初始化双向链表
struct Node* initializeList() {return NULL; // 返回一个空链表
}// 在链表尾部插入节点
struct Node* insertAtEnd(struct Node* head, int data) {//开辟spacestruct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->data = data;newNode->next = NULL;if (head == NULL) {newNode->prev = NULL;return newNode; // 如果链表为空，新节点成为链表头}struct Node* current = head;while (current->next != NULL) {current = current->next; // 移动到链表末尾}current->next = newNode;newNode->prev = current;return head;
}// 在链表头部插入节点
struct Node* insertAtBeginning(struct Node* head, int data) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->data = data;newNode->next = head;newNode->prev = NULL;if (head != NULL) {head->prev = newNode;}return newNode; // 新节点成为链表头
}// 删除节点
struct Node* deleteNode(struct Node* head, int data) {if (head == NULL) {return NULL; // 空链表，无需删除}if (head->data == data) {struct Node* temp = head;head = head->next;if (head != NULL) {head->prev = NULL;}free(temp);return head; // 删除链表头节点}struct Node* current = head;while (current != NULL && current->data != data) {current = current->next;}if (current != NULL) {struct Node* prevNode = current->prev;struct Node* nextNode = current->next;if (prevNode != NULL) {prevNode->next = nextNode;}if (nextNode != NULL) {nextNode->prev = prevNode;}free(current); // 删除中间或末尾节点}return head;
}// 查找节点
struct Node* searchNode(struct Node* head, int data) {struct Node* current = head;while (current != NULL) {if (current->data == data) {return current; // 找到匹配的节点}current = current->next;}return NULL; // 未找到匹配的节点
}// 修改节点的数据
void modifyNode(struct Node* head, int oldData, int newData) {struct Node* nodeToModify = searchNode(head, oldData);if (nodeToModify != NULL) {nodeToModify->data = newData; // 修改节点的数据}
}// 打印链表（正向）
void printListForward(struct Node* head) {struct Node* current = head;while (current != NULL) {printf("%d -> ", current->data);current = current->next;}printf("NULL\n");
}// 打印链表（反向）
void printListBackward(struct Node* tail) {struct Node* current = tail;while (current != NULL) {printf("%d -> ", current->data);current = current->prev;}printf("NULL\n");
}// 释放链表内存
void freeList(struct Node* head) {struct Node* current = head;while (current != NULL) {struct Node* temp = current;current = current->next;free(temp);}
}int main() {struct Node* list = initializeList();int choice, data, oldData, newData;while (1) {printf("\nMenu:\n");printf("1. Insert at the end\n");printf("2. Insert at the beginning\n");printf("3. Delete node\n");printf("4. Search node\n");printf("5. Modify node\n");printf("6. Print list forward\n");printf("7. Print list backward\n");printf("8. Exit\n");printf("Enter your choice: ");scanf("%d", &choice);switch (choice) {case 1:printf("Enter data to insert: ");scanf("%d", &data);list = insertAtEnd(list, data);break;case 2:printf("Enter data to insert: ");scanf("%d", &data);list = insertAtBeginning(list, data);break;case 3:printf("Enter data to delete: ");scanf("%d", &data);list = deleteNode(list, data);break;case 4:printf("Enter data to search: ");scanf("%d", &data);if (searchNode(list, data) != NULL) {printf("Found node with data %d\n", data);} else {printf("Node with data %d not found\n", data);}break;case 5:printf("Enter data to modify: ");scanf("%d", &oldData);printf("Enter new data: ");scanf("%d", &newData);modifyNode(list, oldData, newData);break;case 6:printf("List (forward): ");printListForward(list);break;case 7:printf("List (backward): ");printListBackward(list);break;case 8:freeList(list);exit(0);default:printf("Invalid choice! Please try again.\n");}}return 0;
}

C++

#include <iostream>// 定义双向链表节点结构
class Node {
public:int data;Node* prev;Node* next;Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};// 定义双向链表类
class DoublyLinkedList {
public:Node* head;DoublyLinkedList() : head(nullptr) {}// 插入节点到链表尾部void insertAtEnd(int val) {Node* newNode = new Node(val);if (head == nullptr) {head = newNode;} else {Node* current = head;while (current->next != nullptr) {current = current->next;}current->next = newNode;newNode->prev = current;}}// 删除节点void deleteNode(int val) {if (head == nullptr) {return; // 空链表，无需删除}Node* current = head;while (current != nullptr && current->data != val) {current = current->next;}if (current == nullptr) {return; // 未找到匹配的节点}if (current->prev != nullptr) {current->prev->next = current->next;} else {head = current->next;}if (current->next != nullptr) {current->next->prev = current->prev;}delete current;}// 查找节点Node* searchNode(int val) {Node* current = head;while (current != nullptr) {if (current->data == val) {return current; // 找到匹配的节点}current = current->next;}return nullptr; // 未找到匹配的节点}// 修改节点的数据void modifyNode(int oldVal, int newVal) {Node* nodeToModify = searchNode(oldVal);if (nodeToModify != nullptr) {nodeToModify->data = newVal; // 修改节点的数据}}// 打印链表void printList() {Node* current = head;while (current != nullptr) {std::cout << current->data << " <-> ";current = current->next;}std::cout << "nullptr" << std::endl;}// 释放链表内存~DoublyLinkedList() {Node* current = head;while (current != nullptr) {Node* temp = current;current = current->next;delete temp;}}
};int main() {DoublyLinkedList list;int choice, data, oldData, newData;while (true) {std::cout << "\nMenu:\n";std::cout << "1. Insert at the end\n";std::cout << "2. Delete node\n";std::cout << "3. Search node\n";std::cout << "4. Modify node\n";std::cout << "5. Print list\n";std::cout << "6. Exit\n";std::cout << "Enter your choice: ";std::cin >> choice;switch (choice) {case 1:std::cout << "Enter data to insert: ";std::cin >> data;list.insertAtEnd(data);break;case 2:std::cout << "Enter data to delete: ";std::cin >> data;list.deleteNode(data);break;case 3:std::cout << "Enter data to search: ";std::cin >> data;if (list.searchNode(data) != nullptr) {std::cout << "Found node with data " << data << std::endl;} else {std::cout << "Node with data " << data << " not found" << std::endl;}break;case 4:std::cout << "Enter data to modify: ";std::cin >> oldData;std::cout << "Enter new data: ";std::cin >> newData;list.modifyNode(oldData, newData);break;case 5:std::cout << "List: ";list.printList();break;case 6:return 0;default:std::cout << "Invalid choice! Please try again." << std::endl;}}return 0;
}

408考研各数据结构C/C++代码（Continually updating）

408考研各数据结构C/C++代码（Continually updating）
这个模块是我应一些朋友的需求，希望我能开一个专栏，专门提供考研408中各种常用的数据结构的代码，并且希望我附上比较完整的注释以及提供用户输入功能，ok，fine，这个专栏会一直更新，直到我认为没有新的数据结构可以讲解了。
目前我比较熟悉的数据结构如下：
数组、链表、队列、栈、树、B/B+树、红黑树、Hash、图。
所以我会先有空更新出如下几个数据结构的代码，欢迎关注。 当然，在我前两年的博客中，对于链表、哈夫曼树等常用数据结构，我都提供了比较完整的详细的实现以及思路讲解，有兴趣可以去考古。