Xóa một nút trong danh sách liên kết đôi trong C++

Giới thiệu

Trong hướng dẫn này, chúng ta sẽ học cách xóa một nút cụ thể trong danh sách liên kết đôi (doubly linked list) bằng C++.

Các bước thực hiện

1. Định nghĩa cấu trúc Node với dữ liệu, con trỏ prev và next.
2. Viết hàm chèn nút vào danh sách.
3. Khởi tạo danh sách với dữ liệu mẫu.
4. Chọn nút cần xóa (ví dụ: nút thứ 2 từ đầu).
5. Viết hàm xóa nút, xử lý 3 trường hợp:
   • Nút là head: cập nhật head sang nút tiếp theo.
   • Nút là nút giữa: liên kết prev->next với next và next->prev với prev.
   • Nút là nút cuối: cập nhật prev->next = NULL.

Mã nguồn ví dụ

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *prev, *next;
};

void deleteNode(Node** head_ref, Node* del) {
    if (*head_ref == NULL || del == NULL) return;
    if (*head_ref == del) *head_ref = del->next;
    if (del->next != NULL) del->next->prev = del->prev;
    if (del->prev != NULL) del->prev->next = del->next;
    free(del);
}

void insertNode(Node** head_ref, int new_data) {
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->prev = NULL;
    new_node->next = (*head_ref);
    if ((*head_ref) != NULL) (*head_ref)->prev = new_node;
    (*head_ref) = new_node;
}

void printLinkedList(Node* node) {
    while (node != NULL) {
        cout << node->data << " -> ";
        node = node->next;
    }
}

int main() {
    Node* head = NULL;
    insertNode(&head, 1);
    insertNode(&head, 2);
    insertNode(&head, 3);
    insertNode(&head, 4);
    insertNode(&head, 5);
    cout << "Danh sách trước khi xóa:" << endl;
    printLinkedList(head);
    deleteNode(&head, head->next); // Xóa nút thứ 2 (giá trị 4)
    cout << "\nDanh sách sau khi xóa:" << endl;
    printLinkedList(head);
    return 0;
}

Kết quả đầu ra

Danh sách trước khi xóa: 5 -> 4 -> 3 -> 2 -> 1 ->
Danh sách sau khi xóa: 5 -> 3 -> 2 -> 1 ->

Kết luận

Hàm deleteNode xử lý đúng mọi trường hợp xóa nút trong danh sách liên kết đôi. Nếu bạn có thắc mắc, hãy để lại bình luận bên dưới.