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:

  1. Dữ liệu: Giá trị mà node đang lưu trữ (có thể là bất kỳ kiểu dữ liệu nào).
  2. 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> // Thêm để sử dụng cout, endl
#include <stdexcept> // Thêm để sử dụng runtime_error

// Định nghĩa cấu trúc Node
struct Node {
    int data; // Dữ liệu của node, có thể thay đổi kiểu dữ liệu tùy ý
    Node* next; // Con trỏ trỏ tới node kế tiếp

    // Constructor để dễ dàng tạo node mới
    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.

// Định nghĩa lớp LinkedList
class LinkedList {
private:
    Node* head; // Con trỏ trỏ đến node đầu tiên của danh sách

public:
    // Constructor
    LinkedList() : head(nullptr) {}

    // Destructor (để giải phóng bộ nhớ)
    ~LinkedList();

    // Các phương thức thao tác trên danh sách:
    void append(int value); // Thêm node vào cuối danh sách
    void prepend(int value); // Thêm node vào đầu danh sách
    void deleteByValue(int value); // Xóa node đầu tiên có giá trị cho trước
    void printList(); // In ra các phần tử của danh sách
    int getSize(); // Lấy kích thước của danh sách (ví dụ đơn giản bằng cách duyệt)
    bool search(int value); // Tìm kiếm một giá trị trong danh sách
    // ... các thao tác khác ...
};

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::append(int value) {
    // 1. Tạo node mới
    Node* newNode = new Node(value);

    // 2. Nếu danh sách rỗng, node mới là head
    if (head == nullptr) {
        head = newNode;
        return; // Kết thúc hàm
    }

    // 3. Nếu không rỗng, tìm node cuối cùng
    Node* current = head; // Bắt đầu từ head
    while (current->next != nullptr) { // Duyệt đến khi con trỏ next là nullptr
        current = current->next; // Di chuyển tới node kế tiếp
    }

    // 4. Node cuối cùng hiện tại (current) sẽ trỏ tới node mới
    current->next = newNode;
    // Node mới đã có next = nullptr từ constructor, nên không cần gán lại
}

Giải thích:

  • Node* newNode = new Node(value); cấp phát bộ nhớ động cho một node mới và khởi tạo nó với giá trị value.
  • Điều kiện if (head == nullptr) xử lý trường hợp danh sách ban đầu trống rỗng.
  • Vòng lặp while (current->next != nullptr) là cách chúng ta duyệt qua danh sách. Chúng ta dừng lại khi current đang trỏ đến node mà con trỏ next của nó là nullptr (tức là current chính là node cuối cùng).
  • current->next = newNode; 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::prepend(int value) {
    // 1. Tạo node mới
    Node* newNode = new Node(value);

    // 2. Con trỏ next của node mới trỏ tới head hiện tại
    newNode->next = head;

    // 3. Cập nhật head để trỏ tới node mới
    head = newNode;
}

Giải thích:

  • newNode->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 = newNode; đặ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 (current) và node đứng trước nó (previous).
  • 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 previous trỏ tới node sau node current (tức là current->next), sau đó giải phóng bộ nhớ của node current.
  • 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::deleteByValue(int value) {
    Node* current = head;
    Node* previous = nullptr; // Con trỏ theo dõi node trước current

    // Trường hợp 1: Xóa node head
    if (current != nullptr && current->data == value) {
        head = current->next; // Cập nhật head
        delete current;      // Giải phóng bộ nhớ của node cũ
        return;
    }

    // Trường hợp 2: Tìm và xóa node không phải head
    while (current != nullptr && current->data != value) {
        previous = current;      // previous theo sát current
        current = current->next; // current di chuyển tới node kế tiếp
    }

    // Nếu không tìm thấy node có giá trị cần xóa (duyệt hết danh sách)
    if (current == nullptr) {
        //cout << "Khong tim thay gia tri " << value << " de xoa." << endl;
        return; // Không làm gì cả
    }

    // Nếu tìm thấy node (current != nullptr và current->data == value)
    // Nối node previous với node sau current
    previous->next = current->next;

    // Giải phóng bộ nhớ của node current (node bị xóa)
    delete current;
}

Giải thích:

  • Chúng ta dùng hai con trỏ: current để duyệt và previous để giữ địa chỉ của node ngay trước current.
  • Trường hợp xóa head được xử lý riêng vì không có node previous nào trước head.
  • Trong vòng lặp, previous luôn được gán bằng current trước khi current nhảy sang node kế tiếp. Điều này đảm bảo previous luôn trỏ đến node đứng ngay trước current.
  • Khi current trỏ đến node cần xóa, chúng ta thực hiện previous->next = current->next;. Thao tác này bỏ qua node current và nối previous trực tiếp với node sau current.
  • delete current; 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::printList() {
    Node* current = head; // Bắt đầu từ head
    if (current == nullptr) {
        cout << "Danh sach rong." << endl;
        return;
    }

    cout << "Danh sach: ";
    while (current != nullptr) { // Duyệt đến khi gặp nullptr (kết thúc danh sách)
        cout << current->data;
        current = current->next; // Di chuyển tới node kế tiếp
        if (current != nullptr) {
            cout << " -> "; // In mũi tên nếu còn node tiếp theo
        }
    }
    cout << endl; // Xuống dòng sau khi in xong
}

Giải thích:

  • Node* current = 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 (current != nullptr) tiếp tục cho đến khi current vượt ra ngoài node cuối cùng.
  • cout << current->data; in dữ liệu của node hiện tại.
  • current = current->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 size 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::getSize() {
    int count = 0;
    Node* current = head;
    while (current != nullptr) {
        count++;
        current = current->next;
    }
    return count;
}

Giải thích:

  • Khởi tạo biến đếm count = 0.
  • Dùng con trỏ current để 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ị count 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::search(int value) {
    Node* current = head;
    while (current != nullptr) {
        if (current->data == value) {
            return true; // Tìm thấy giá trị, trả về true ngay lập tức
        }
        current = current->next;
    }
    return false; // Duyệt hết danh sách mà không tìm thấy, trả về false
}

Giải thích:

  • Duyệt danh sách bằng con trỏ current.
  • Trong mỗi bước lặp, kiểm tra xem current->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à current 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* current = head;
    Node* nextNode; // Biến tạm để lưu con trỏ tới node kế tiếp trước khi xóa node hiện tại

    while (current != nullptr) {
        nextNode = current->next; // Lưu lại con trỏ next trước khi xóa current
        delete current;           // Giải phóng bộ nhớ của node hiện tại
        current = nextNode;       // Di chuyển tới node kế tiếp đã lưu trước đó
    }
    head = nullptr; // Đảm bảo head trỏ về nullptr sau khi danh sách bị xóa hoàn toàn
    cout << "Danh sach da duoc giai phong bo nho." << endl;
}

Giải thích:

  • Chúng ta dùng current để duyệt.
  • Trước khi gọi delete current;, chúng ta phải lưu lại con trỏ current->next vào biến tạm nextNode. Lý do là sau khi delete current;, current trở thành con trỏ treo (dangling pointer) và không còn an toàn để truy cập current->next nữa.
  • Sau khi giải phóng node hiện tại, chúng ta cập nhật current = nextNode; để tiếp tục duyệt sang node kế tiếp.
  • Vòng lặp dừng lại khi current (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>

// ... (Định nghĩa struct Node và class LinkedList như ở trên) ...

// ** Cài đặt đầy đủ các phương thức vào đây **

// ... (append, prepend, deleteByValue, printList, getSize, search, ~LinkedList) ...


int main() {
    LinkedList my_list; // Tạo một danh sách liên kết rỗng

    // Thêm phần tử vào cuối
    my_list.append(10);
    my_list.append(20);
    my_list.append(30);
    my_list.printList(); // Output: Danh sach: 10 -> 20 -> 30

    // Thêm phần tử vào đầu
    my_list.prepend(5);
    my_list.printList(); // Output: Danh sach: 5 -> 10 -> 20 -> 30

    // Lấy kích thước
    cout << "Kich thuoc danh sach: " << my_list.getSize() << endl; // Output: Kich thuoc danh sach: 4

    // Tìm kiếm
    cout << "Tim kiem 20: " << (my_list.search(20) ? "Tim thay" : "Khong tim thay") << endl; // Output: Tim kiem 20: Tim thay
    cout << "Tim kiem 100: " << (my_list.search(100) ? "Tim thay" : "Khong tim thay") << endl; // Output: Tim kiem 100: Khong tim thay

    // Xóa phần tử
    my_list.deleteByValue(20);
    my_list.printList(); // Output: Danh sach: 5 -> 10 -> 30

    my_list.deleteByValue(5); // Xóa head
    my_list.printList(); // Output: Danh sach: 10 -> 30

    my_list.deleteByValue(40); // Xóa giá trị không tồn tại
    my_list.printList(); // Output: Danh sach: 10 -> 30

    my_list.deleteByValue(30); // Xóa node cuối cùng
    my_list.printList(); // Output: Danh sach rong.

    // Khi my_list ra khỏi phạm vi của main, destructor sẽ tự động được gọi, giải phóng bộ nhớ.
    return 0;
}

(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à my_list.
  • Gọi các phương thức append, prepend, printList, getSize, search, deleteByValue để 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 my_list 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.