Trong hướng dẫn này, chúng ta sẽ tìm hiểu cách xóa một nút trong danh sách được liên kết kép với vị trí đã cho.
Hãy xem các bước để giải quyết vấn đề.
-
Viết cấu trúc với dữ liệu, con trỏ trước và tiếp theo.
-
Viết một hàm để chèn nút vào danh sách được liên kết kép.
-
Khởi tạo danh sách được liên kết kép với dữ liệu giả.
-
Khởi tạo vị trí để xóa nút.
-
Lặp lại danh sách được liên kết và tìm nút có vị trí đã cho để xóa nút.
-
Viết hàm xóa nút. Hãy xem xét ba trường hợp sau khi xóa nút.
-
Nếu nút là nút đầu, thì hãy chuyển phần đầu sang nút tiếp theo.
-
Nếu nút là nút giữa, thì hãy liên kết nút tiếp theo với nút trước đó
-
Nếu nút là nút kết thúc, hãy xóa liên kết nút trước đó.
-
Ví dụ
Hãy xem mã.
#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;
}
// head node
if (*head_ref == del) {
*head_ref = del->next;
}
// middle node
if (del->next != NULL) {
del->next->prev = del->prev;
}
// end node
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;
int i;
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 << "Doubly linked list before deletion" << endl;
printLinkedList(head);
int n = 2;
deleteNodeAtGivenPosition(&head, n);
cout << "\nDoubly linked list after deletion" << endl;
printLinkedList(head);
return 0;
} Đầu ra
Nếu bạn thực hiện chương trình trên, bạn sẽ nhận được kết quả sau.
Doubly linked list before deletion 10->8->4->2->5-> Doubly linked list after deletion 10->4->2->5->
Kết luận
Nếu bạn có bất kỳ câu hỏi nào trong hướng dẫn, hãy đề cập đến chúng trong phần bình luận.