Bài 34.4: Bài tập thực hành danh sách liên kết đôi trong C++

Chào mừng các bạn trở lại với chuỗi bài viết về C++ trên blog của FullhouseDev! Sau khi đã tìm hiểu về khái niệm cơ bản và ưu nhược điểm của danh sách liên kết đôi, hôm nay chúng ta sẽ xắn tay áo lên và đi vào phần thực hành đầy thú vị: triển khai cấu trúc dữ liệu này trong C++. Đây là cơ hội tuyệt vời để củng cố kiến thức lý thuyết bằng cách tự mình viết code và hiểu rõ cách các con trỏ hoạt động!

Danh sách liên kết đôi, hay Doubly Linked List, là một biến thể nâng cấp của danh sách liên kết đơn. Điểm khác biệt cốt lõi nằm ở việc mỗi nút (node) không chỉ trỏ đến nút tiếp theo (next) mà còn trỏ ngược lại đến nút trước đó (prev). Sự "hai chiều" này mang lại nhiều lợi ích, đặc biệt là khả năng duyệt danh sách theo cả hai hướng và thao tác xóa nút hiệu quả hơn đáng kể.

Trong bài thực hành này, chúng ta sẽ cùng nhau xây dựng một lớp (class) C++ đơn giản để quản lý danh sách liên kết đôi và triển khai một số thao tác cơ bản nhưng quan trọng nhất.

1. Cấu trúc của một Node trong Danh sách Liên kết Đôi

Trước hết, chúng ta cần định nghĩa cấu trúc của một nút (node). Mỗi nút sẽ chứa dữ liệu (data) và hai con trỏ: next (trỏ tới nút kế tiếp) và prev (trỏ tới nút đứng trước).

#include <iostream>

struct Node {
    int d;
    Node* sau;
    Node* trc;
    Node(int gt) : d(gt), sau(nullptr), trc(nullptr) {}
};

Giải thích:

struct Node: Chúng ta sử dụng struct để tạo một kiểu dữ liệu tùy chỉnh cho các nút.
int data;: Thành phần này lưu trữ giá trị thực tế của nút. Bạn có thể thay int bằng bất kỳ kiểu dữ liệu nào khác tùy theo nhu cầu.
Node* next;: Đây là con trỏ kiểu Node*, trỏ đến nút tiếp theo trong danh sách. Nếu nút này là nút cuối cùng, next sẽ là nullptr.
Node* prev;: Đây cũng là con trỏ kiểu Node*, trỏ đến nút trước đó trong danh sách. Nếu nút này là nút đầu tiên, prev sẽ là nullptr.
Node(int val) : data(val), next(nullptr), prev(nullptr) {}: Đây là một constructor. Khi bạn tạo một Node mới với cú pháp Node newNode(someValue);, constructor này sẽ được gọi để khởi tạo data bằng val, và quan trọng là thiết lập next và prev ban đầu là nullptr.

2. Xây dựng Lớp Quản lý Danh sách Liên kết Đôi

Để quản lý toàn bộ danh sách (như biết nút đầu tiên ở đâu, nút cuối cùng ở đâu), chúng ta sẽ tạo một lớp DoublyLinkedList. Lớp này sẽ chứa các con trỏ trỏ đến nút đầu (head) và nút cuối (tail) của danh sách.

#include <iostream>

struct Node {
    int d;
    Node* sau;
    Node* trc;
    Node(int gt) : d(gt), sau(nullptr), trc(nullptr) {}
};

class DoublyLinkedList {
private:
    Node* dau;
    Node* cuoi;

public:
    DoublyLinkedList() : dau(nullptr), cuoi(nullptr) {}

    ~DoublyLinkedList() {
        Node* h = dau;
        while (h != nullptr) {
            Node* k = h->sau;
            delete h;
            h = k;
        }
        dau = nullptr;
        cuoi = nullptr;
        cout << "\nDa giai phong bo nho danh sach." << endl;
    }

    void displayForward() const {
        Node* h = dau;
        cout << "Danh sach (xuoi): ";
        while (h != nullptr) {
            cout << h->d;
            if (h->sau != nullptr) {
                cout << " <-> ";
            }
            h = h->sau;
        }
        cout << endl;
    }

    void displayBackward() const {
        Node* h = cuoi;
        cout << "Danh sach (nguoc): ";
        while (h != nullptr) {
            cout << h->d;
            if (h->trc != nullptr) {
                cout << " <-> ";
            }
            h = h->trc;
        }
        cout << endl;
    }
};

Giải thích:

Node* head;, Node* tail;: Hai con trỏ thành viên private này giúp chúng ta luôn biết được điểm bắt đầu và kết thúc của danh sách.
DoublyLinkedList() : head(nullptr), tail(nullptr) {}: Constructor khởi tạo head và tail là nullptr, biểu thị một danh sách rỗng.
~DoublyLinkedList(): Đây là destructor. Nó được gọi tự động khi một đối tượng DoublyLinkedList bị hủy (ví dụ: khi nó ra khỏi phạm vi). Nhiệm vụ của nó là giải phóng bộ nhớ mà chúng ta đã cấp phát động cho các nút bằng new Node(...). Nếu không có destructor này, sẽ xảy ra hiện tượng rò rỉ bộ nhớ (memory leak). Vòng lặp duyệt qua từng nút và dùng delete để giải phóng bộ nhớ.
displayForward(): Duyệt danh sách từ head đến tail bằng cách đi theo con trỏ next.
displayBackward(): Duyệt danh sách từ tail đến head bằng cách đi theo con trỏ prev. Đây là ưu điểm nổi bật của danh sách liên kết đôi so với danh sách liên kết đơn!

3. Các Thao Tác Chèn Nút

Bây giờ, chúng ta sẽ thêm các phương thức để thêm nút mới vào danh sách.

3.1. Chèn vào đầu danh sách (`insertAtHead`)

Thao tác này thêm một nút mới làm nút đầu tiên của danh sách.

// Thêm vào trong class DoublyLinkedList:
void insertAtHead(int gt) {
    Node* m = new Node(gt);

    if (dau == nullptr) {
        dau = m;
        cuoi = m;
    } else {
        m->sau = dau;
        dau->trc = m;
        dau = m;
    }
    cout << "Da chen " << gt << " vao dau danh sach." << endl;
}

Giải thích:

Tạo nút mới: Node* newNode = new Node(val); cấp phát bộ nhớ và tạo một nút mới với dữ liệu val. next và prev của nó ban đầu là nullptr nhờ constructor.
Kiểm tra danh sách rỗng: Nếu head là nullptr, danh sách đang trống. Nút mới là nút duy nhất, nên nó vừa là head vừa là tail.
Danh sách không rỗng:
- newNode->next = head;: Nút mới sẽ đứng trước head cũ, nên con trỏ next của nó phải trỏ đến head cũ.
- head->prev = newNode;: Nút head cũ bây giờ có một nút đứng trước nó là newNode, nên con trỏ prev của head cũ phải trỏ đến newNode.
- head = newNode;: Cuối cùng, cập nhật head của danh sách là newNode.

3.2. Chèn vào cuối danh sách (`insertAtTail`)

Thao tác này thêm một nút mới làm nút cuối cùng của danh sách.

// Thêm vào trong class DoublyLinkedList:
void insertAtTail(int gt) {
    Node* m = new Node(gt);

    if (cuoi == nullptr) {
        dau = m;
        cuoi = m;
    } else {
        m->trc = cuoi;
        cuoi->sau = m;
        cuoi = m;
    }
    cout << "Da chen " << gt << " vao cuoi danh sach." << endl;
}

Giải thích:

Tạo nút mới: Tương tự insertAtHead.
Kiểm tra danh sách rỗng: Tương tự insertAtHead.
Danh sách không rỗng:
- newNode->prev = tail;: Nút mới sẽ đứng sau tail cũ, nên con trỏ prev của nó phải trỏ đến tail cũ.
- tail->next = newNode;: Nút tail cũ bây giờ có một nút đứng sau nó là newNode, nên con trỏ next của tail cũ phải trỏ đến newNode.
- tail = newNode;: Cuối cùng, cập nhật tail của danh sách là newNode.

3.3. Chèn sau một nút cho trước (`insertAfterNode`)

Thao tác này yêu cầu tìm hoặc được cung cấp một con trỏ đến một nút hiện có, sau đó chèn nút mới vào sau nút đó. Thao tác này đặc biệt hữu ích và minh họa rõ ràng việc cập nhật cả hai con trỏ next và prev.

// Thêm vào trong class DoublyLinkedList:
void insertAfterNode(Node* q, int gt) {
    if (q == nullptr) {
        cout << "Loi: prevNode khong duoc la nullptr." << endl;
        return;
    }

    Node* m = new Node(gt);

    m->sau = q->sau;
    m->trc = q;

    q->sau = m;

    if (m->sau != nullptr) {
        m->sau->trc = m;
    } else {
        cuoi = m;
    }
    cout << "Da chen " << gt << " sau node co data = " << q->d << "." << endl;
}

Node* search(int gt) const {
    Node* h = dau;
    while (h != nullptr) {
        if (h->d == gt) {
            return h;
        }
        h = h->sau;
    }
    return nullptr;
}

Giải thích:

Kiểm tra tính hợp lệ của prevNode.
Tạo nút mới newNode.
Thiết lập liên kết cho newNode:
- newNode->next = prevNode->next;: Con trỏ next của newNode sẽ trỏ tới nút mà prevNode đang trỏ tới (nút sau prevNode).
- newNode->prev = prevNode;: Con trỏ prev của newNode trỏ ngược lại prevNode.
Cập nhật liên kết của prevNode:
- prevNode->next = newNode;: Con trỏ next của prevNode bây giờ trỏ tới newNode.
Cập nhật liên kết của nút sau newNode (nếu có):
- if (newNode->next != nullptr): Kiểm tra xem nút sau newNode có tồn tại không.
- newNode->next->prev = newNode;: Nếu có, con trỏ prev của nút đó (là newNode->next) phải được cập nhật để trỏ ngược về newNode.
- Nếu newNode->next là nullptr, tức là newNode được chèn vào vị trí cuối cùng, chúng ta cần cập nhật tail của danh sách.

Lưu ý: Để sử dụng insertAfterNode một cách thực tế, bạn sẽ cần một cách để lấy con trỏ đến nút prevNode mong muốn, ví dụ như bằng cách duyệt hoặc dùng một phương thức search. Tôi đã thêm một phương thức search đơn giản để bạn dễ hình dung cách sử dụng.

4. Thao Tác Xóa Nút

Xóa một nút trong danh sách liên kết đôi dễ dàng hơn nhiều so với danh sách liên kết đơn, đặc biệt là khi xóa một nút ở giữa hoặc cuối danh sách, vì chúng ta có con trỏ prev để truy cập nút đứng trước nó mà không cần duyệt lại từ đầu.

Chúng ta sẽ viết một phương thức để xóa một nút cụ thể dựa vào con trỏ tới nút đó.

// Thêm vào trong class DoublyLinkedList:
void deleteNode(Node* x) {
    if (dau == nullptr || x == nullptr) {
        cout << "Khong the xoa. Danh sach rong hoac node xoa la nullptr." << endl;
        return;
    }

    if (x->trc != nullptr) {
        x->trc->sau = x->sau;
    } else {
        dau = x->sau;
    }

    if (x->sau != nullptr) {
        x->sau->trc = x->trc;
    } else {
        cuoi = x->trc;
    }

    cout << "Da xoa node co data = " << x->d << "." << endl;
    delete x;

    if (dau == nullptr) {
         cuoi = nullptr;
    }
}

void deleteByValue(int gt) {
    Node* x = search(gt);
    if (x != nullptr) {
        deleteNode(x);
    } else {
        cout << "Khong tim thay node co data = " << gt << " de xoa." << endl;
    }
}

Giải thích:

Kiểm tra các trường hợp lỗi: danh sách rỗng hoặc con trỏ truyền vào là nullptr.
Cập nhật con trỏ của nút trước: Nếu nodeToDelete không phải là head (tức là nodeToDelete->prev không phải nullptr), thì con trỏ next của nút đứng trước nó (nodeToDelete->prev) phải được bỏ qua nodeToDelete và trỏ thẳng tới nút đứng sau nodeToDelete (nodeToDelete->next). Nếu nodeToDelete là head, chúng ta chỉ cần cập nhật head lên nút tiếp theo.
Cập nhật con trỏ của nút sau: Tương tự, nếu nodeToDelete không phải là tail (tức là nodeToDelete->next không phải nullptr), thì con trỏ prev của nút đứng sau nó (nodeToDelete->next) phải được bỏ qua nodeToDelete và trỏ ngược về nút đứng trước nodeToDelete (nodeToDelete->prev). Nếu nodeToDelete là tail, chúng ta chỉ cần cập nhật tail lùi về nút trước đó.
Giải phóng bộ nhớ: Sau khi các liên kết đã được sửa, chúng ta sử dụng delete nodeToDelete để giải phóng vùng nhớ đã cấp phát cho nút đó.
Phương thức deleteByValue minh họa cách bạn có thể kết hợp search và deleteNode để xóa một nút dựa trên giá trị của nó.

Lưu ý: Việc xử lý các trường hợp đặc biệt (xóa head, xóa tail, xóa nút duy nhất trong danh sách) được tự động xử lý bởi logic cập nhật con trỏ head và tail trong phương thức deleteNode. Nếu nút bị xóa là head, head được cập nhật. Nếu là tail, tail được cập nhật. Nếu danh sách chỉ còn một nút và nó bị xóa, cả head và tail sẽ trở thành nullptr.

5. Ví dụ Minh Họa Toàn Bộ

Bây giờ, chúng ta hãy ghép tất cả lại trong một hàm main để thấy cách các phương thức hoạt động cùng nhau.

#include <iostream>

struct Node {
    int d;
    Node* sau;
    Node* trc;
    Node(int gt) : d(gt), sau(nullptr), trc(nullptr) {}
};

class DoublyLinkedList {
private:
    Node* dau;
    Node* cuoi;

public:
    DoublyLinkedList() : dau(nullptr), cuoi(nullptr) {}

    ~DoublyLinkedList() {
        Node* h = dau;
        while (h != nullptr) {
            Node* k = h->sau;
            delete h;
            h = k;
        }
        dau = nullptr;
        cuoi = nullptr;
        cout << "\nDa giai phong bo nho danh sach." << endl;
    }

    void insertAtHead(int gt) {
        Node* m = new Node(gt);
        if (dau == nullptr) {
            dau = m;
            cuoi = m;
        } else {
            m->sau = dau;
            dau->trc = m;
            dau = m;
        }
        cout << "Da chen " << gt << " vao dau danh sach." << endl;
    }

    void insertAtTail(int gt) {
        Node* m = new Node(gt);
        if (cuoi == nullptr) {
            dau = m;
            cuoi = m;
        } else {
            m->trc = cuoi;
            cuoi->sau = m;
            cuoi = m;
        }
        cout << "Da chen " << gt << " vao cuoi danh sach." << endl;
    }

    Node* search(int gt) const {
        Node* h = dau;
        while (h != nullptr) {
            if (h->d == gt) {
                return h;
            }
            h = h->sau;
        }
        return nullptr;
    }

    void insertAfterNode(Node* q, int gt) {
        if (q == nullptr) {
            cout << "Loi: prevNode khong duoc la nullptr." << endl;
            return;
        }
        Node* m = new Node(gt);
        m->sau = q->sau;
        m->trc = q;
        q->sau = m;
        if (m->sau != nullptr) {
            m->sau->trc = m;
        } else {
            cuoi = m;
        }
        cout << "Da chen " << gt << " sau node co data = " << q->d << "." << endl;
    }

    void deleteNode(Node* x) {
        if (dau == nullptr || x == nullptr) {
            cout << "Khong the xoa. Danh sach rong hoac node xoa la nullptr." << endl;
            return;
        }

        if (x->trc != nullptr) {
            x->trc->sau = x->sau;
        } else {
            dau = x->sau;
        }

        if (x->sau != nullptr) {
            x->sau->trc = x->trc;
        } else {
            cuoi = x->trc;
        }

        cout << "Da xoa node co data = " << x->d << "." << endl;
        delete x;

        if (dau == nullptr) {
             cuoi = nullptr;
        }
    }

    void deleteByValue(int gt) {
        Node* x = search(gt);
        if (x != nullptr) {
            deleteNode(x);
        } else {
            cout << "Khong tim thay node co data = " << gt << " de xoa." << endl;
        }
    }

    void displayForward() const {
        Node* h = dau;
        cout << "Danh sach (xuoi): ";
        if (h == nullptr) {
             cout << "rong";
        }
        while (h != nullptr) {
            cout << h->d;
            if (h->sau != nullptr) {
                cout << " <-> ";
            }
            h = h->sau;
        }
        cout << endl;
    }

    void displayBackward() const {
        Node* h = cuoi;
        cout << "Danh sach (nguoc): ";
         if (h == nullptr) {
             cout << "rong";
        }
        while (h != nullptr) {
            cout << h->d;
            if (h->trc != nullptr) {
                cout << " <-> ";
            }
            h = h->trc;
        }
        cout << endl;
    }

};

int main() {
    DoublyLinkedList dslk;
    cout << "Khoi tao danh sach rong." << endl;
    dslk.displayForward();

    cout << "\n--- Chen vao dau ---" << endl;
    dslk.insertAtHead(10);
    dslk.insertAtHead(20);
    dslk.insertAtHead(5);
    dslk.displayForward();
    dslk.displayBackward();

    cout << "\n--- Chen vao cuoi ---" << endl;
    dslk.insertAtTail(30);
    dslk.insertAtTail(40);
    dslk.displayForward();
    dslk.displayBackward();

    cout << "\n--- Chen sau node 20 ---" << endl;
    Node* nut20 = dslk.search(20);
    if (nut20 != nullptr) {
        dslk.insertAfterNode(nut20, 25);
        dslk.displayForward();
        dslk.displayBackward();
    } else {
         cout << "Khong tim thay node 20 de chen sau." << endl;
    }

    cout << "\n--- Xoa node theo gia tri ---" << endl;
    dslk.deleteByValue(10);
    dslk.displayForward();
    dslk.deleteByValue(5);
    dslk.displayForward();
    dslk.deleteByValue(40);
    dslk.displayForward();
    dslk.deleteByValue(100);
    dslk.displayForward();

    cout << "\n--- Chen lai de test xoa ---" << endl;
    dslk.insertAtHead(1);
    dslk.insertAtTail(50);
    dslk.displayForward();
    dslk.displayBackward();

    cout << "\n--- Xoa het danh sach ---" << endl;
    dslk.deleteByValue(25);
    dslk.displayForward();
    dslk.deleteByValue(1);
    dslk.displayForward();
    dslk.deleteByValue(50);
    dslk.displayForward();
    dslk.deleteByValue(20);
    dslk.displayForward();
    dslk.deleteByValue(30);
    dslk.displayForward();

    return 0;
}

Giải thích hàm main:

Chúng ta tạo một đối tượng DoublyLinkedList có tên dll.
Lần lượt gọi các phương thức insertAtHead, insertAtTail để thêm các phần tử và hiển thị kết quả sau mỗi lần chèn.
Sử dụng phương thức search để tìm con trỏ đến nút có giá trị 20, sau đó gọi insertAfterNode để chèn 25 vào sau nó. Điều này minh họa cách bạn cần có con trỏ tới nút muốn chèn sau.
Thực hiện các thao tác xóa khác nhau bằng cách gọi deleteByValue, lần lượt xóa một nút ở giữa, nút đầu, nút cuối. Sau mỗi lần xóa, chúng ta hiển thị danh sách để kiểm tra.
Cuối cùng, chúng ta xóa từng nút còn lại cho đến khi danh sách rỗng để kiểm tra đầy đủ các trường hợp xóa.
Khi hàm main kết thúc, đối tượng dll sẽ bị hủy, và destructor ~DoublyLinkedList() mà chúng ta đã viết sẽ tự động được gọi để giải phóng tất cả bộ nhớ đã cấp phát cho các nút còn lại, tránh rò rỉ bộ nhớ. Thông báo "Da giai phong bo nho danh sach." sẽ xuất hiện ở cuối output.

Output:

Khoi tao danh sach rong.
Danh sach (xuoi): rong

--- Chen vao dau ---
Da chen 10 vao dau danh sach.
Da chen 20 vao dau danh sach.
Da chen 5 vao dau danh sach.
Danh sach (xuoi): 5 <-> 20 <-> 10
Danh sach (nguoc): 10 <-> 20 <-> 5

--- Chen vao cuoi ---
Da chen 30 vao cuoi danh sach.
Da chen 40 vao cuoi danh sach.
Danh sach (xuoi): 5 <-> 20 <-> 10 <-> 30 <-> 40
Danh sach (nguoc): 40 <-> 30 <-> 10 <-> 20 <-> 5

--- Chen sau node 20 ---
Da chen 25 sau node co data = 20.
Danh sach (xuoi): 5 <-> 20 <-> 25 <-> 10 <-> 30 <-> 40
Danh sach (nguoc): 40 <-> 30 <-> 10 <-> 25 <-> 20 <-> 5

--- Xoa node theo gia tri ---
Da xoa node co data = 10.
Danh sach (xuoi): 5 <-> 20 <-> 25 <-> 30 <-> 40
Da xoa node co data = 5.
Danh sach (xuoi): 20 <-> 25 <-> 30 <-> 40
Da xoa node co data = 40.
Danh sach (xuoi): 20 <-> 25 <-> 30
Khong tim thay node co data = 100 de xoa.
Danh sach (xuoi): 20 <-> 25 <-> 30

--- Chen lai de test xoa ---
Da chen 1 vao dau danh sach.
Da chen 50 vao cuoi danh sach.
Danh sach (xuoi): 1 <-> 20 <-> 25 <-> 30 <-> 50
Danh sach (nguoc): 50 <-> 30 <-> 25 <-> 20 <-> 1

--- Xoa het danh sach ---
Da xoa node co data = 25.
Danh sach (xuoi): 1 <-> 20 <-> 30 <-> 50
Da xoa node co data = 1.
Danh sach (xuoi): 20 <-> 30 <-> 50
Da xoa node co data = 50.
Danh sach (xuoi): 20 <-> 30
Da xoa node co data = 20.
Danh sach (xuoi): 30
Da xoa node co data = 30.
Danh sach (xuoi): rong

Da giai phong bo nho danh sach.

Comments

There are no comments at the moment.