Xóa nút tại vị trí cho trước trong danh sách liên kết đôi 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 tại vị trí xác định trong danh sách liên kết đôi (doubly linked list).

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

1. Định nghĩa cấu trúc Node với dữ liệu, 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. Xác định vị trí cần xóa.
5. Duyệt đến nút tại vị trí đó.
6. Gọi hàm xóa nút chung (xử lý 3 trường hợp head/giữa/cuối).

Mã nguồn ví dụ

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

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

void deleteNode(struct Node** head_ref, struct 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 deleteNodeAtGivenPosition(struct Node** head_ref, int n) {
    if (*head_ref == NULL || n <= 0) return;
    struct Node* current = *head_ref;
    for (int i = 1; current != NULL && i < n; i++) {
        current = current->next;
    }
    if (current == NULL) return;
    deleteNode(head_ref, current);
}

void insertNode(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct 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(struct Node* head) {
    while (head != NULL) {
        cout << head->data << "->";
        head = head->next;
    }
}

int main() {
    struct Node* head = NULL;
    insertNode(&head, 5);
    insertNode(&head, 2);
    insertNode(&head, 4);
    insertNode(&head, 8);
    insertNode(&head, 10);
    cout << "Danh sách đôi trước khi xóa:" << endl;
    printLinkedList(head);
    int n = 2;
    deleteNodeAtGivenPosition(&head, n);
    cout << "\nDanh sách đôi sau khi xóa vị trí " << n << ":" << endl;
    printLinkedList(head);
    return 0;
}

Kết quả đầu ra

Danh sách đôi trước khi xóa: 10->8->4->2->5->
Danh sách đôi sau khi xóa: 10->4->2->5->

Kết luận

Chương trình xóa thành công nút tại vị trí 2 (giá trị 8) 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.