ลบโหนดที่มีค่าน้อยกว่าค่าที่กำหนดใน Doubly Linked List ด้วย C++

ในบทช่วยสอนนี้ เราจะเรียนรู้วิธีการลบโหนดที่มีค่าน้อยกว่าค่าที่กำหนดจาก doubly linked list

ขั้นตอนในการแก้ปัญหา:

• เขียน struct ที่มี data, prev และ next pointers
• เขียนฟังก์ชัน insert node เข้า doubly linked list
• เริ่มต้น doubly linked list ด้วยข้อมูลตัวอย่าง
• วนลูปผ่าน doubly linked list ตรวจสอบว่าโหนดปัจจุบันมีค่าน้อยกว่าค่าที่กำหนดหรือไม่
• ถ้าค่าปัจจุบันน้อยกว่าค่าที่กำหนด ให้ลบโหนดนั้น
• เขียนฟังก์ชันลบโหนด พิจารณา 3 กรณี:
  • ถ้าโหนดเป็น head node ให้ย้าย head ไปโหนดถัดไป
  • ถ้าโหนดเป็นโหนดกลาง ให้ลิงก์โหนดถัดไปกับโหนดก่อนหน้า
  • ถ้าโหนดเป็นโหนดท้าย ให้ลบลิงก์ของโหนดก่อนหน้า

ตัวอย่างโค้ด

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

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

void insertNode(Node** head_ref, int new_data) {
    Node* new_node = (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 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);
    return;
}

void deleteSmallerNodes(Node** head_ref, int K) {
    Node* temp = *head_ref;
    Node* next;
    while (temp != NULL) {
        next = temp->next;
        if (temp->data < K) {
            deleteNode(head_ref, temp);
        }
        temp = next;
    }
}

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

int main() {
    Node* head = NULL;
    insertNode(&head, 1);
    insertNode(&head, 2);
    insertNode(&head, 3);
    insertNode(&head, 4);
    insertNode(&head, 10);
    insertNode(&head, 11);
    insertNode(&head, 12);
    int K = 10;
    cout << "Linked List before deletion:" << endl;
    printLinkedList(head);
    deleteSmallerNodes(&head, K);
    cout << "\nLinked List after deletion:" << endl;
    printLinkedList(head);
}

Output

หากรันโปรแกรมข้างต้น จะได้ผลลัพธ์ดังนี้:

Linked List before deletion: 12 -> 11 -> 10 -> 4 -> 3 -> 2 -> 1 ->
Linked List after deletion: 12 -> 11 -> 10 ->

สรุป

หากมีข้อสงสัยในบทช่วยสอนนี้ สามารถถามได้ในส่วนความคิดเห็น