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

2023-11-06 19:55| 来源: 网络整理| 查看: 265

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

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

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

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

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

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

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

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

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

C #include #include // 定义双向链表节点结构 struct Node { int data; struct Node* prev; struct Node* next; }; // 初始化双向链表 struct Node* initializeList() { return NULL; // 返回一个空链表 } // 在链表尾部插入节点 struct Node* insertAtEnd(struct Node* head, int data) { //开辟space struct 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 // 定义双向链表节点结构 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 Node* temp = current; current = current->next; delete temp; } } }; int main() { DoublyLinkedList list; int choice, data, oldData, newData; while (true) { std::cout std::cout

【本文地址】

公司简介

联系我们