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

对我个人而言，在开发过程中使用的比较多的就是双向链表了。
很多重要的代码优化都会使用到基于双向链表实现的数据机构。
比如我们常用的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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205

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 << 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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

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

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