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

Chào mừng quay trở lại với series C++!

Sau khi đã cùng nhau tìm hiểu lý thuyết đằng sau danh sách liên kết (Linked List) - một trong những cấu trúc dữ liệu cơ bản nhưng cực kỳ quan trọng, giờ là lúc chúng ta xắn tay áo lên và bắt tay vào thực hành! Lý thuyết chỉ là nền tảng, việc thao tác trực tiếp với các con trỏ, tạo, sửa, xóa các nút mới là cách tốt nhất để nắm vững khái niệm này.

Bài viết này sẽ tập trung vào một số bài tập thực tế và cơ bản nhất khi làm việc với danh sách liên kết đơn trong C++. Chúng ta sẽ đi qua từng bài tập, phân tích logic và cung cấp code minh họa chi tiết.

Trước khi bắt đầu, hãy nhắc lại cấu trúc cơ bản của một nút (Node) trong danh sách liên kết đơn mà chúng ta sẽ sử dụng:

#include <iostream> // Cần cho nhập xuất
#include <cstdlib>  // Cần cho các hàm tiện ích khác nếu dùng (như exit, không dùng trong ví dụ này)

struct Node {
    int data;      // Dữ liệu mà nút lưu giữ
    Node* next;    // Con trỏ trỏ tới nút kế tiếp trong danh sách

    // Constructor tiện lợi để tạo nút mới
    Node(int val) : data(val), next(nullptr) {}
};

Mỗi Node chứa dữ liệu (data) và một con trỏ (next) trỏ đến nút tiếp theo. Con trỏ next của nút cuối cùng trong danh sách sẽ trỏ đến nullptr để đánh dấu điểm kết thúc. Danh sách được quản lý bằng một con trỏ head (hoặc first) trỏ đến nút đầu tiên. Nếu danh sách trống, head sẽ là nullptr.

Bây giờ, hãy đi vào các bài tập thực hành!

Bài tập 1: Duyệt (Traversal) và In danh sách

Bài tập đầu tiên và cơ bản nhất là duyệt qua toàn bộ danh sách và in ra giá trị của từng nút. Điều này giúp chúng ta hình dung được trạng thái hiện tại của danh sách.

Logic:

Bắt đầu với một con trỏ tạm thời (ví dụ: current) trỏ đến nút đầu tiên (head).
Lặp lại quá trình:
- In ra giá trị của nút hiện tại (current->data).
- Di chuyển con trỏ tạm thời đến nút kế tiếp (current = current->next).
Dừng lại khi con trỏ tạm thời trở thành nullptr (nghĩa là đã đi qua nút cuối cùng).

Code minh họa:

void printList(Node* head) {
    Node* current = head; // Bắt đầu từ đầu danh sách
    cout << "Danh sach: ";
    while (current != nullptr) { // Lặp cho đến khi gặp nút cuối cùng (next là nullptr)
        cout << current->data;
        if (current->next != nullptr) {
            cout << " -> "; // In mũi tên nếu chưa phải nút cuối
        }
        current = current->next; // Di chuyển đến nút kế tiếp
    }
    cout << " -> nullptr" << endl; // Đánh dấu kết thúc danh sách
}

Giải thích code:

Hàm nhận vào con trỏ head (truyền theo giá trị vì ta không sửa đổi head gốc, chỉ duyệt).
Node* current = head;: Khởi tạo con trỏ current để đi theo danh sách, bắt đầu từ head.
while (current != nullptr): Vòng lặp tiếp tục miễn là current vẫn trỏ đến một nút hợp lệ (chưa phải là nullptr).
cout << current->data;: Truy cập và in ra dữ liệu của nút hiện tại.
if (current->next != nullptr): Kiểm tra xem có phải nút cuối cùng chưa để in mũi tên cho đúng.
current = current->next;: Đây là bước quan trọng để di chuyển đến nút kế tiếp. Ta gán current bằng giá trị của con trỏ next trong nút hiện tại.

Bài tập 2: Chèn một nút vào đầu danh sách

Chèn một nút mới vào vị trí đầu tiên là một thao tác khá đơn giản trong danh sách liên kết đơn.

Logic:

Tạo một nút mới với dữ liệu cần chèn.
Thiết lập con trỏ next của nút mới này trỏ đến nút hiện tại đang là đầu danh sách (head).
Cập nhật con trỏ head để trỏ đến nút mới này.

Code minh họa:

void insertAtBeginning(Node*& head, int newData) { // Truyền head theo tham chiếu!
    Node* newNode = new Node(newData); // 1. Tạo nút mới

    // 2. Thiết lập con trỏ next của nút mới
    newNode->next = head;

    // 3. Cập nhật head để trỏ đến nút mới
    head = newNode;

    cout << "Da chen " << newData << " vao dau danh sach." << endl;
}

Giải thích code:

Hàm nhận vào Node*& head: Đây là điểm mấu chốt! Chúng ta cần truyền con trỏ head theo tham chiếu (&) vì thao tác chèn vào đầu sẽ làm thay đổi chính giá trị của con trỏ head (nó sẽ trỏ đến một vị trí bộ nhớ khác). Nếu truyền theo giá trị, sự thay đổi chỉ xảy ra trong hàm và không ảnh hưởng đến con trỏ head bên ngoài.
Node* newNode = new Node(newData);: Tạo một đối tượng Node mới trên heap sử dụng new và khởi tạo dữ liệu cho nó.
newNode->next = head;: Con trỏ next của nút mới giờ đây sẽ trỏ đến nút mà head đang trỏ tới (nút đầu tiên cũ).
head = newNode;: Cập nhật con trỏ head toàn cục để nó trỏ đến newNode, biến newNode thành nút đầu tiên mới.

Bài tập 3: Chèn một nút vào cuối danh sách

Chèn vào cuối danh sách phức tạp hơn một chút so với chèn vào đầu, vì ta cần phải tìm đến nút cuối cùng hiện tại.

Logic:

Tạo một nút mới với dữ liệu cần chèn.
Kiểm tra xem danh sách có trống không (head == nullptr). Nếu có, nút mới chính là head.
Nếu danh sách không trống, duyệt qua danh sách bằng một con trỏ tạm thời cho đến khi tìm thấy nút cuối cùng (nút mà con trỏ next của nó là nullptr).
Thiết lập con trỏ next của nút cuối cùng này trỏ đến nút mới.

Code minh họa:

void insertAtEnd(Node*& head, int newData) { // Truyền head theo tham chiếu
    Node* newNode = new Node(newData); // 1. Tạo nút mới

    // 2. Kiểm tra danh sách trống
    if (head == nullptr) {
        head = newNode; // Nút mới là head nếu danh sách trống
        cout << "Da chen " << newData << " vao dau danh sach (danh sach ban dau trong)." << endl;
        return;
    }

    // 3. Tìm nút cuối cùng nếu danh sách không trống
    Node* last = head;
    while (last->next != nullptr) { // Duyệt cho đến khi last->next là nullptr
        last = last->next; // Di chuyển đến nút kế tiếp
    }

    // 4. Thiết lập con trỏ next của nút cuối cùng trỏ đến nút mới
    last->next = newNode;

    cout << "Da chen " << newData << " vao cuoi danh sach." << endl;
}

Giải thích code:

Hàm nhận vào Node*& head (truyền tham chiếu) vì head có thể bị thay đổi nếu danh sách ban đầu trống.
if (head == nullptr): Xử lý trường hợp danh sách rỗng. Nút mới trở thành head duy nhất.
Node* last = head;: Khởi tạo con trỏ last để duyệt.
while (last->next != nullptr): Vòng lặp này duyệt cho đến khi last trỏ đến nút cuối cùng (nút mà con trỏ next của nó là nullptr).
last->next = newNode;: Gán con trỏ next của nút cuối cùng hiện tại trỏ đến newNode, thêm newNode vào cuối danh sách. Con trỏ next mặc định của newNode là nullptr, nên nó tự động trở thành nút cuối mới.

Bài tập 4: Xóa một nút theo giá trị

Xóa một nút là thao tác phức tạp nhất trong số các thao tác cơ bản, đòi hỏi phải quản lý các con trỏ một cách cẩn thận để không làm mất phần còn lại của danh sách và giải phóng bộ nhớ đúng cách. Chúng ta sẽ xóa lần xuất hiện đầu tiên của một giá trị.

Logic:

Kiểm tra xem danh sách có trống không. Nếu trống, không làm gì cả.
Kiểm tra xem nút cần xóa có phải là nút đầu tiên (head) không. Nếu đúng:
- Lưu lại con trỏ head hiện tại vào một biến tạm.
- Cập nhật head trỏ đến nút kế tiếp (head->next).
- Giải phóng bộ nhớ của nút tạm đã lưu.
- Kết thúc hàm.
Nếu nút cần xóa không phải là head:
- Duyệt qua danh sách bằng hai con trỏ: current (nút hiện tại) và previous (nút ngay trước current).
- Trong khi duyệt, di chuyển previous theo sau current.
- Dừng lại khi current là nullptr (không tìm thấy giá trị) hoặc current->data bằng giá trị cần xóa.
Nếu không tìm thấy giá trị (current == nullptr), không làm gì cả.
Nếu tìm thấy giá trị (current->data == valueToDelete):
- Cập nhật con trỏ next của nút previous để trỏ đến nút kế tiếp của current (previous->next = current->next). Điều này làm nút current bị "bỏ qua" và loại khỏi danh sách.
- Giải phóng bộ nhớ của nút current.

Code minh họa:

void deleteNodeByValue(Node*& head, int valueToDelete) {
    if (head == nullptr) { // 1. Danh sách trống
        cout << "Danh sach trống, khong the xoa." << endl;
        return;
    }

    // 2. Xóa nut dau (head)
    if (head->data == valueToDelete) {
        Node* temp = head; // Luu lai head hien tai
        head = head->next; // Cap nhat head tro den nut ke tiep
        delete temp;       // Giai phong bo nho cua nut dau cu
        cout << "Da xoa nut dau co gia tri " << valueToDelete << "." << endl;
        return;
    }

    // 3. Xoa nut khong phai la dau
    Node* current = head;
    Node* previous = nullptr; // previous luon di truoc current mot buoc

    while (current != nullptr && current->data != valueToDelete) {
        previous = current;        // Cap nhat previous la nut hien tai truoc khi di chuyen
        current = current->next;   // Di chuyen current den nut ke tiep
    }

    // 4. Kiem tra neu khong tim thay gia tri
    if (current == nullptr) {
        cout << "Khong tim thay gia tri " << valueToDelete << " de xoa." << endl;
        return;
    }

    // 5. Tim thay gia tri, tien hanh xoa nut current
    // Lien ket nut previous voi nut ke tiep cua current
    previous->next = current->next;

    // Giai phong bo nho cua nut current
    delete current;

    cout << "Da xoa nut co gia tri " << valueToDelete << "." << endl;
}

Giải thích code:

Hàm nhận Node*& head (tham chiếu) vì head có thể thay đổi nếu nút đầu tiên bị xóa.
Kiểm tra trường hợp danh sách trống và trường hợp nút cần xóa là head được xử lý riêng rẽ ở đầu hàm để đơn giản hóa logic xóa ở giữa/cuối.
Trong vòng while: Chúng ta dùng hai con trỏ current và previous. previous luôn trỏ đến nút ngay trước nút mà current đang trỏ tới. Điều này rất quan trọng để khi tìm thấy nút cần xóa (current), ta có thể nối nút previous với nút kế tiếp của current.
if (current == nullptr): Nếu vòng lặp kết thúc mà current là nullptr, nghĩa là ta đã duyệt hết danh sách nhưng không tìm thấy giá trị cần xóa.
previous->next = current->next;: Đây là bước then chốt để loại bỏ current khỏi danh sách. Con trỏ next của nút trước (previous) giờ đây trỏ đến nút mà current đang trỏ tới (current->next), bỏ qua current.
delete current;: Quan trọng! Sau khi nút đã bị loại khỏi danh sách, ta phải giải phóng bộ nhớ mà nó chiếm dụng bằng toán tử delete để tránh rò rỉ bộ nhớ (memory leak).

Bài tập 5: Đếm số nút trong danh sách

Đếm số lượng nút là một bài tập đơn giản, chỉ cần duyệt qua danh sách và tăng biến đếm.

Logic:

Khởi tạo biến đếm bằng 0.
Duyệt qua danh sách từ head đến cuối.
Với mỗi nút gặp, tăng biến đếm lên 1.
Trả về giá trị cuối cùng của biến đếm.

Code minh họa:

int countNodes(Node* head) {
    int count = 0;      // 1. Khởi tạo biến đếm
    Node* current = head; // Bắt đầu duyệt từ đầu

    while (current != nullptr) { // 2. Duyệt cho đến cuối danh sách
        count++;                 // 3. Tăng biến đếm cho mỗi nút
        current = current->next; // Di chuyển đến nút kế tiếp
    }

    return count; // 4. Trả về số nút đếm được
}

Giải thích code:

Hàm nhận Node* head (truyền giá trị) vì không cần thay đổi cấu trúc danh sách.
Sử dụng một vòng lặp while tương tự như duyệt để đi qua từng nút.
Biến count được tăng lên mỗi lần vòng lặp thực hiện, tức là mỗi lần xử lý một nút.
Khi current trở thành nullptr, vòng lặp kết thúc và giá trị count cuối cùng chính là số nút trong danh sách.

Ví dụ tổng hợp và Quản lý bộ nhớ

Để thấy rõ cách các hàm này hoạt động cùng nhau, chúng ta sẽ viết một hàm main nhỏ để thực hiện vài thao tác.

Một điều cực kỳ quan trọng khi làm việc với danh sách liên kết trong C++ là quản lý bộ nhớ. Khi chúng ta tạo các nút bằng new, chúng được cấp phát trên heap. Chúng ta phải giải phóng bộ nhớ này bằng delete khi không cần đến nữa để tránh rò rỉ bộ nhớ. Đối với danh sách liên kết, điều này thường có nghĩa là khi danh sách không còn được sử dụng, ta cần duyệt và delete từng nút.

int main() {
    Node* head = nullptr; // Bắt đầu với danh sách rỗng

    // 1. Chen vao cuoi
    cout << "*** Chen vao cuoi ***" << endl;
    insertAtEnd(head, 10); // head: 10 -> nullptr
    printList(head);
    insertAtEnd(head, 20); // head: 10 -> 20 -> nullptr
    printList(head);
    insertAtEnd(head, 30); // head: 10 -> 20 -> 30 -> nullptr
    printList(head);

    // 2. Chen vao dau
    cout << "\n*** Chen vao dau ***" << endl;
    insertAtBeginning(head, 5); // head: 5 -> 10 -> 20 -> 30 -> nullptr
    printList(head);
    insertAtBeginning(head, 1); // head: 1 -> 5 -> 10 -> 20 -> 30 -> nullptr
    printList(head);

    // 3. Dem nut
    cout << "\n*** Dem nut ***" << endl;
    cout << "So nut trong danh sach: " << countNodes(head) << endl; // Expected: 5

    // 4. Xoa nut theo gia tri
    cout << "\n*** Xoa nut theo gia tri ***" << endl;
    deleteNodeByValue(head, 20); // Xoa nut o giua
    printList(head); // Expected: 1 -> 5 -> 10 -> 30 -> nullptr

    deleteNodeByValue(head, 1);  // Xoa nut dau
    printList(head); // Expected: 5 -> 10 -> 30 -> nullptr

    deleteNodeByValue(head, 30); // Xoa nut cuoi
    printList(head); // Expected: 5 -> 10 -> nullptr

    deleteNodeByValue(head, 5);  // Xoa nut dau moi
    printList(head); // Expected: 10 -> nullptr

    deleteNodeByValue(head, 10); // Xoa nut cuoi cung
    printList(head); // Expected: nullptr

    deleteNodeByValue(head, 100); // Xoa nut khong ton tai
    printList(head); // Expected: Khong tim thay gia tri 100 de xoa. Danh sach: nullptr

    // 5. Giai phong bo nho (Quan trong!)
    // Neu danh sach con nut sau cac thao tac (vi du: khong xoa het)
    // Can co mot ham de xoa het cac nut con lai.
    cout << "\n*** Giai phong bo nho con lai (neu co) ***" << endl;
    Node* current = head;
    while (current != nullptr) {
        Node* next = current->next; // Luu lai nut ke tiep truoc khi xoa nut hien tai
        cout << "Dang giai phong nut co gia tri: " << current->data << endl;
        delete current;
        current = next; // Di chuyen den nut ke tiep da luu
    }
    head = nullptr; // Dat head ve nullptr de danh dau danh sach trong hoan toan
    cout << "Da giai phong het bo nho." << endl;

    printList(head); // Expected: Danh sach: nullptr

    return 0;
}

Lưu ý về quản lý bộ nhớ: Trong ví dụ trên, các thao tác chèn và xóa đã được viết để quản lý bộ nhớ trong từng thao tác. Tuy nhiên, một cách tiếp cận chắc chắn hơn cho danh sách liên kết là có một hàm riêng (hoặc destructor nếu dùng class) để duyệt toàn bộ danh sách và xóa tất cả các nút còn lại khi không cần danh sách nữa. Phần cuối của hàm main minh họa cách thực hiện việc giải phóng bộ nhớ còn lại này bằng cách duyệt từ head đến cuối và gọi delete cho từng nút. Luôn nhớ giải phóng bộ nhớ đã cấp phát bằng new!

Comments

There are no comments at the moment.