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

Chào mừng bạn đến với bài thực hành chuyên sâu về danh sách liên kết đơn (Singly Linked List) trong C++. Sau khi đã tìm hiểu về lý thuyết, đây là lúc chúng ta xắn tay áo lên và làm quen với việc cài đặt thực tế, đặc biệt là làm việc hiệu quả với con trỏ - linh hồn của cấu trúc dữ liệu này.

Danh sách liên kết đơn là một trong những cấu trúc dữ liệu cơ bản nhưng cực kỳ mạnh mẽ. Nó cho phép chúng ta lưu trữ dữ liệu một cách linh hoạt về kích thước, không bị ràng buộc bởi bộ nhớ cấp phát tĩnh như mảng. Tuy nhiên, sự linh hoạt này đến từ việc quản lý các con trỏ để liên kết các phần tử (gọi là node) lại với nhau. Việc này đòi hỏi sự tỉ mỉ và hiểu rõ cách con trỏ hoạt động.

Bài viết này sẽ tập trung vào việc cài đặt các thao tác cơ bản trên danh sách liên kết đơn, giúp bạn làm quen với việc điều chỉnh các con trỏ next để thêm, xóa, duyệt và tìm kiếm phần tử.

Nền tảng: Cấu trúc Node

Mọi danh sách liên kết đều được xây dựng từ các khối cơ bản gọi là node. Trong danh sách liên kết đơn, mỗi node chứa hai phần:

Dữ liệu: Giá trị mà node đang lưu trữ (có thể là bất kỳ kiểu dữ liệu nào).
Con trỏ next: Một con trỏ trỏ đến node tiếp theo trong danh sách. Node cuối cùng sẽ có con trỏ next trỏ đến nullptr (hoặc NULL trong C cũ) để đánh dấu điểm kết thúc.

Chúng ta có thể định nghĩa cấu trúc Node trong C++ như sau:

#include <iostream>
#include <stdexcept>

struct Node {
    int data;
    Node* next;

    Node(int val) : data(val), next(nullptr) {}
};

Trong đoạn code trên:

struct Node định nghĩa kiểu dữ liệu mới cho node.
int data; là nơi lưu trữ giá trị (ở đây là số nguyên).
Node* next; là con trỏ kiểu Node*, nó sẽ giữ địa chỉ của node tiếp theo.
Node(int val) : data(val), next(nullptr) {} là một constructor. Khi tạo một node mới với new Node(value), nó sẽ tự động gán value vào data và khởi tạo next là nullptr.

Lớp Danh sách Liên kết (LinkedList)

Để quản lý toàn bộ danh sách, chúng ta thường sử dụng một lớp hoặc cấu trúc chứa con trỏ đến node đầu tiên của danh sách, thường gọi là head. Node head là điểm truy cập duy nhất vào danh sách. Nếu head là nullptr, danh sách rỗng.

class LinkedList {
private:
    Node* head;

public:
    LinkedList() : head(nullptr) {}
    ~LinkedList();

    void themCuoi(int g);
    void themDau(int g);
    void xoa(int g);
    void in();
    int kichThuoc();
    bool tim(int g);
};

Lớp LinkedList này:

Có một thành viên private là head, chỉ lớp này mới có thể trực tiếp truy cập head.
Constructor LinkedList() khởi tạo head là nullptr, tạo ra một danh sách rỗng ban đầu.
Destructor ~LinkedList() là cực kỳ quan trọng trong C++ để giải phóng bộ nhớ đã cấp phát động (new) cho các node, tránh rò rỉ bộ nhớ (memory leak).
Các phương thức public định nghĩa các thao tác mà người dùng có thể thực hiện trên danh sách.

Bây giờ, hãy đi sâu vào cài đặt chi tiết từng phương thức.

Cài đặt các thao tác cơ bản

1. Thêm node vào cuối danh sách (`append`)

Thao tác này thêm một node mới vào vị trí cuối cùng của danh sách.

Nếu danh sách rỗng (head == nullptr), node mới sẽ trở thành head.
Nếu danh sách không rỗng, chúng ta cần duyệt qua danh sách để tìm đến node cuối cùng (node có next == nullptr), sau đó cho con trỏ next của node cuối cùng đó trỏ đến node mới.

void LinkedList::themCuoi(int g) {
    Node* m = new Node(g);
    if (!head) {
        head = m;
        return;
    }
    Node* h = head;
    while (h->next) {
        h = h->next;
    }
    h->next = m;
}

Giải thích:

Node* m = new Node(g); cấp phát bộ nhớ động cho một node mới và khởi tạo nó với giá trị g.
Điều kiện if (!head) xử lý trường hợp danh sách ban đầu trống rỗng.
Vòng lặp while (h->next) là cách chúng ta duyệt qua danh sách. Chúng ta dừng lại khi h đang trỏ đến node mà con trỏ next của nó là nullptr (tức là h chính là node cuối cùng).
h->next = m; là bước quan trọng nhất: chúng ta cập nhật con trỏ next của node cuối cùng cũ để nó trỏ đến node mới vừa tạo, nối node mới vào cuối danh sách.

2. Thêm node vào đầu danh sách (`prepend`)

Thao tác này đơn giản hơn append vì chúng ta chỉ cần thay đổi con trỏ head.

Tạo node mới.
Cho con trỏ next của node mới trỏ đến node hiện tại mà head đang trỏ tới.
Cập nhật head để trỏ đến node mới.

void LinkedList::themDau(int g) {
    Node* m = new Node(g);
    m->next = head;
    head = m;
}

Giải thích:

m->next = head; kết nối node mới với phần còn lại của danh sách (bắt đầu từ head cũ).
head = m; đặt node mới làm node đầu tiên của danh sách. Thao tác này hoạt động đúng ngay cả khi danh sách rỗng ban đầu (head là nullptr).

3. Xóa node theo giá trị (`deleteByValue`)

Thao tác này tìm node đầu tiên có giá trị khớp với giá trị cần xóa và loại bỏ nó khỏi danh sách. Đây là một thao tác phức tạp hơn một chút vì cần quản lý con trỏ của node trước node cần xóa.

Cần theo dõi cả node hiện tại (h) và node đứng trước nó (t).
Duyệt qua danh sách.
Nếu tìm thấy node cần xóa:
- Nếu đó là node head, cập nhật head để trỏ tới node kế tiếp và giải phóng bộ nhớ của node cũ.
- Nếu không phải node head, cho con trỏ next của node t trỏ tới node sau node h (tức là h->next), sau đó giải phóng bộ nhớ của node h.
Nếu duyệt hết danh sách mà không tìm thấy, không làm gì cả hoặc thông báo lỗi.

void LinkedList::xoa(int g) {
    Node* h = head;
    Node* t = nullptr;

    if (h && h->data == g) {
        head = h->next;
        delete h;
        return;
    }

    while (h && h->data != g) {
        t = h;
        h = h->next;
    }

    if (!h) return;

    t->next = h->next;
    delete h;
}

Giải thích:

Chúng ta dùng hai con trỏ: h để duyệt và t để giữ địa chỉ của node ngay trước h.
Trường hợp xóa head được xử lý riêng vì không có node t nào trước head.
Trong vòng lặp, t luôn được gán bằng h trước khi h nhảy sang node kế tiếp. Điều này đảm bảo t luôn trỏ đến node đứng ngay trước h.
Khi h trỏ đến node cần xóa, chúng ta thực hiện t->next = h->next;. Thao tác này bỏ qua node h và nối t trực tiếp với node sau h.
delete h; là bắt buộc để trả lại bộ nhớ đã cấp phát cho hệ thống. Nếu quên bước này, sẽ xảy ra rò rỉ bộ nhớ.

4. In danh sách (`printList`)

Thao tác này duyệt qua danh sách từ đầu đến cuối và in ra dữ liệu của từng node.

void LinkedList::in() {
    Node* h = head;
    if (!h) {
        cout << "Danh sach rong." << endl;
        return;
    }

    cout << "Danh sach: ";
    while (h) {
        cout << h->data;
        h = h->next;
        if (h) {
            cout << " -> ";
        }
    }
    cout << endl;
}

Giải thích:

Node* h = head; khởi tạo một con trỏ tạm thời để duyệt. Chúng ta không thay đổi con trỏ head gốc khi in.
Vòng lặp while (h) tiếp tục cho đến khi h vượt ra ngoài node cuối cùng.
cout << h->data; in dữ liệu của node hiện tại.
h = h->next; là bước di chuyển sang node kế tiếp.

5. Lấy kích thước danh sách (`getSize`)

Một cách đơn giản để lấy kích thước là duyệt toàn bộ danh sách và đếm số node. (Cách hiệu quả hơn là duy trì một biến kichThuoc trong lớp và cập nhật nó khi thêm/xóa, nhưng cách duyệt giúp luyện tập).

int LinkedList::kichThuoc() {
    int n = 0;
    Node* h = head;
    while (h) {
        n++;
        h = h->next;
    }
    return n;
}

Giải thích:

Khởi tạo biến đếm n = 0.
Dùng con trỏ h để duyệt từ head.
Mỗi lần di chuyển sang node kế tiếp, tăng biến đếm.
Trả về giá trị n khi duyệt xong.

6. Tìm kiếm giá trị (`search`)

Thao tác này kiểm tra xem một giá trị có tồn tại trong danh sách hay không.

bool LinkedList::tim(int g) {
    Node* h = head;
    while (h) {
        if (h->data == g) return true;
        h = h->next;
    }
    return false;
}

Giải thích:

Duyệt danh sách bằng con trỏ h.
Trong mỗi bước lặp, kiểm tra xem h->data có bằng giá trị cần tìm hay không.
Nếu khớp, trả về true và kết thúc hàm.
Nếu vòng lặp kết thúc (tức là h trở thành nullptr) mà chưa tìm thấy, trả về false.

7. Destructor (`~LinkedList`) - Giải phóng bộ nhớ

Đây là phần quan trọng nhất để tránh rò rỉ bộ nhớ khi đối tượng LinkedList bị hủy. Chúng ta cần duyệt qua tất cả các node và giải phóng bộ nhớ của từng node một.

LinkedList::~LinkedList() {
    Node* h = head;
    Node* t;

    while (h) {
        t = h->next;
        delete h;
        h = t;
    }
    head = nullptr;
    cout << "Danh sach da duoc giai phong bo nho." << endl;
}

Giải thích:

Chúng ta dùng h để duyệt.
Trước khi gọi delete h;, chúng ta phải lưu lại con trỏ h->next vào biến tạm t. Lý do là sau khi delete h;, h trở thành con trỏ treo (dangling pointer) và không còn an toàn để truy cập h->next nữa.
Sau khi giải phóng node hiện tại, chúng ta cập nhật h = t; để tiếp tục duyệt sang node kế tiếp.
Vòng lặp dừng lại khi h (trước khi cập nhật) là nullptr, tức là đã xử lý hết các node.
head = nullptr; đảm bảo trạng thái của danh sách sau khi hủy là rỗng.

Ví dụ minh họa sử dụng

Bây giờ, hãy xem cách sử dụng lớp LinkedList đã cài đặt trong hàm main.

#include <iostream>
#include <stdexcept>

struct Node {
    int data;
    Node* next;

    Node(int val) : data(val), next(nullptr) {}
};

class LinkedList {
private:
    Node* head;

public:
    LinkedList() : head(nullptr) {}
    ~LinkedList();

    void themCuoi(int g);
    void themDau(int g);
    void xoa(int g);
    void in();
    int kichThuoc();
    bool tim(int g);
};

void LinkedList::themCuoi(int g) {
    Node* m = new Node(g);
    if (!head) {
        head = m;
        return;
    }
    Node* h = head;
    while (h->next) {
        h = h->next;
    }
    h->next = m;
}

void LinkedList::themDau(int g) {
    Node* m = new Node(g);
    m->next = head;
    head = m;
}

void LinkedList::xoa(int g) {
    Node* h = head;
    Node* t = nullptr;

    if (h && h->data == g) {
        head = h->next;
        delete h;
        return;
    }

    while (h && h->data != g) {
        t = h;
        h = h->next;
    }

    if (!h) return;

    t->next = h->next;
    delete h;
}

void LinkedList::in() {
    Node* h = head;
    if (!h) {
        cout << "Danh sach rong." << endl;
        return;
    }

    cout << "Danh sach: ";
    while (h) {
        cout << h->data;
        h = h->next;
        if (h) {
            cout << " -> ";
        }
    }
    cout << endl;
}

int LinkedList::kichThuoc() {
    int n = 0;
    Node* h = head;
    while (h) {
        n++;
        h = h->next;
    }
    return n;
}

bool LinkedList::tim(int g) {
    Node* h = head;
    while (h) {
        if (h->data == g) return true;
        h = h->next;
    }
    return false;
}

LinkedList::~LinkedList() {
    Node* h = head;
    Node* t;

    while (h) {
        t = h->next;
        delete h;
        h = t;
    }
    head = nullptr;
    cout << "Danh sach da duoc giai phong bo nho." << endl;
}

int main() {
    LinkedList ds;

    ds.themCuoi(10);
    ds.themCuoi(20);
    ds.themCuoi(30);
    ds.in();

    ds.themDau(5);
    ds.in();

    cout << "Kich thuoc danh sach: " << ds.kichThuoc() << endl;

    cout << "Tim kiem 20: " << (ds.tim(20) ? "Tim thay" : "Khong tim thay") << endl;
    cout << "Tim kiem 100: " << (ds.tim(100) ? "Tim thay" : "Khong tim thay") << endl;

    ds.xoa(20);
    ds.in();

    ds.xoa(5);
    ds.in();

    ds.xoa(40);
    ds.in();

    ds.xoa(30);
    ds.in();

    return 0;
}

Output:

Danh sach: 10 -> 20 -> 30
Danh sach: 5 -> 10 -> 20 -> 30
Kich thuoc danh sach: 4
Tim kiem 20: Tim thay
Tim kiem 100: Khong tim thay
Danh sach: 5 -> 10 -> 30
Danh sach: 10 -> 30
Danh sach: 10 -> 30
Danh sach rong.
Danh sach da duoc giai phong bo nho.

(Lưu ý: Để chạy được code này, bạn cần ghép toàn bộ các phần định nghĩa Node, LinkedList và cài đặt các phương thức vào cùng một file .cpp trước hàm main.)

Trong hàm main:

Chúng ta tạo một đối tượng LinkedList tên là ds.
Gọi các phương thức themCuoi, themDau, in, kichThuoc, tim, xoa để thao tác và kiểm tra kết quả.
Khi chương trình kết thúc hàm main, đối tượng ds sẽ bị hủy. Lúc này, destructor ~LinkedList() mà chúng ta đã cài đặt sẽ tự động chạy, đảm bảo toàn bộ bộ nhớ đã cấp phát cho các node được giải phóng một cách sạch sẽ. Đây là lý do việc cài đặt destructor chính xác là rất quan trọng khi làm việc với cấp phát bộ nhớ động trong C++.

Comments

There are no comments at the moment.