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

迈不过友情╰ 2024-02-23 07:29 2阅读 0赞

#### 文章目录 ####

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

对我个人而言，在开发过程中使用的比较多的就是双向链表了。  
很多重要的代码优化都会使用到基于双向链表实现的数据机构。  
比如我们常用的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) {
        
    	//开辟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 <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_C_C_Continually updating]  
这个模块是我应一些朋友的需求，希望我能开一个专栏，专门提供考研408中各种常用的数据结构的代码，并且希望我附上比较完整的注释以及提供用户输入功能，ok，fine，这个专栏会一直更新，直到我认为没有新的数据结构可以讲解了。  
目前我比较熟悉的数据结构如下：  
数组、链表、队列、栈、树、B/B+树、红黑树、Hash、图。  
所以我会先有空更新出如下几个数据结构的代码，欢迎关注。 当然，在我前两年的博客中，对于链表、哈夫曼树等常用数据结构，我都提供了比较完整的详细的实现以及思路讲解，有兴趣可以去考古。

[408_C_C_Continually updating]: https://blog.csdn.net/Zhangsama1/article/details/133676491?spm=1001.2014.3001.5502