Bài 33.1: Khái niệm danh sách liên kết đơn trong C++

Chào mừng các bạn quay trở lại với series blog về C++ của FullhouseDev!

Trong thế giới lập trình, việc lựa chọn cấu trúc dữ liệu phù hợp có vai trò quyết định đến hiệu suất và sự linh hoạt của chương trình. Chúng ta đã quen thuộc với mảng (arrays) - một cấu trúc dữ liệu tuyệt vời cho việc lưu trữ các phần tử cùng kiểu một cách liền kề trong bộ nhớ, cho phép truy cập ngẫu nhiên (random access) cực nhanh.

Tuy nhiên, mảng cũng có những hạn chế của nó. Kích thước của mảng thường phải được xác định trước (trừ các trường hợp vector), và việc thêm hoặc xóa một phần tử ở giữa mảng đòi hỏi phải di chuyển rất nhiều phần tử khác, dẫn đến chi phí cao về thời gian (độ phức tạp O(n)).

Vậy, khi chúng ta cần một cấu trúc dữ liệu có khả năng thay đổi kích thước linh hoạt và hỗ trợ việc thêm/xóa phần tử hiệu quả hơn ở một số vị trí nhất định, chúng ta sẽ nghĩ đến Danh sách liên kết (Linked List). Và trong bài viết này, chúng ta sẽ bắt đầu khám phá loại danh sách liên kết đơn giản nhất nhưng cũng là nền tảng nhất: Danh sách liên kết đơn (Singly Linked List).

Danh sách liên kết đơn là gì?

Hãy tưởng tượng bạn có một chuỗi các toa tàu. Mỗi toa tàu không chỉ chứa "hành khách" (dữ liệu) mà còn có một liên kết đến toa tàu tiếp theo. Toa tàu đầu tiên là "đầu tàu", và toa tàu cuối cùng thì không liên kết đến toa nào nữa (coi như là điểm dừng cuối). Đó chính là ý tưởng cốt lõi của danh sách liên kết đơn!

Cụ thể hơn, danh sách liên kết đơn là một tập hợp các nút (nodes). Mỗi nút bao gồm hai phần chính:

Dữ liệu (Data): Đây là nơi lưu trữ thông tin thực tế mà bạn muốn lưu trữ (có thể là số nguyên, chuỗi, đối tượng, v.v.).
Con trỏ (Pointer): Một con trỏ trỏ đến nút tiếp theo trong danh sách.

Danh sách liên kết đơn chỉ duy trì một con trỏ duy nhất trỏ đến nút đầu tiên của danh sách, thường được gọi là con trỏ head (hoặc root). Nút cuối cùng trong danh sách có con trỏ next của nó trỏ đến null (hoặc nullptr trong C++ hiện đại) để đánh dấu kết thúc danh sách.

Cấu trúc của một Nút (Node) trong C++

Để hiện thực hóa khái niệm này trong C++, chúng ta có thể sử dụng struct hoặc class để định nghĩa cấu trúc của một nút.

#include <iostream> // Cần cho ví dụ sau

// Định nghĩa cấu trúc của một nút (Node)
struct Node {
    int data;      // Phần dữ liệu (ví dụ là số nguyên)
    Node* next;    // Con trỏ trỏ đến nút tiếp theo

    // Constructor đơn giản (tùy chọn nhưng tiện lợi)
    Node(int val) : data(val), next(nullptr) {}
};

Giải thích:

Chúng ta định nghĩa một struct tên là Node.
Bên trong struct, có một biến data kiểu int (bạn có thể thay thế int bằng bất kỳ kiểu dữ liệu nào bạn muốn lưu trữ).
Điều quan trọng là biến next. Nó là một con trỏ (*) kiểu Node*. Điều này có nghĩa là next có thể trỏ đến một đối tượng khác cùng kiểu Node. Chính con trỏ này tạo nên "liên kết" giữa các nút.
Chúng ta thêm một constructor đơn giản Node(int val). Khi tạo một nút mới, chúng ta có thể truyền giá trị ban đầu cho data, và con trỏ next sẽ được khởi tạo mặc định là nullptr (nghĩa là ban đầu nút này chưa trỏ đến nút nào cả).

Cách các Nút Liên kết với nhau

Một danh sách liên kết đơn được tạo thành bằng cách kết nối các nút lại với nhau thông qua con trỏ next. Con trỏ head giữ địa chỉ của nút đầu tiên.

Hãy xem ví dụ minh họa cách chúng ta có thể tạo và liên kết vài nút đơn giản:

#include <iostream>

// Định nghĩa cấu trúc của một nút (Node)
struct Node {
    int data;
    Node* next;

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

int main() {
    // Tạo nút đầu tiên
    Node* head = new Node(10); // Nút đầu tiên có data = 10, next = nullptr

    // Tạo nút thứ hai
    Node* second = new Node(20); // Nút thứ hai có data = 20, next = nullptr

    // Tạo nút thứ ba
    Node* third = new Node(30); // Nút thứ ba có data = 30, next = nullptr

    // Liên kết các nút lại với nhau:
    // Nút đầu tiên (head) trỏ đến nút thứ hai
    head->next = second;

    // Nút thứ hai trỏ đến nút thứ ba
    second->next = third;

    // Nút thứ ba vẫn trỏ đến nullptr (đây là nút cuối cùng)

    // Bây giờ danh sách của chúng ta trông như thế này (tưởng tượng):
    // head -> Node(10) -> Node(20) -> Node(30) -> nullptr

    cout << "Du lieu nut dau tien: " << head->data << endl;
    cout << "Du lieu nut thu hai: " << head->next->data << endl;       // Truy cap qua head->next
    cout << "Du lieu nut thu ba: " << head->next->next->data << endl; // Truy cap qua head->next->next

    // **RẤT QUAN TRỌNG:** Giải phóng bộ nhớ đã cấp phát!
    // (Trong ví dụ đơn giản này, ta làm thủ công, nhưng trong thực tế cần quản lý chặt chẽ hơn)
    delete head;
    delete second;
    delete third;
    // Lưu ý: Cách giải phóng này chỉ đúng khi ta không còn sử dụng các con trỏ nữa.
    // Để giải phóng toàn bộ danh sách, ta cần duyệt qua nó (sẽ thấy ở ví dụ duyệt).

    return 0;
}

Giải thích:

Chúng ta tạo ba nút riêng biệt trên bộ nhớ heap bằng toán tử new. Mỗi new Node(...) trả về một con trỏ đến nút mới được tạo.
head = new Node(10); tạo nút đầu tiên và gán địa chỉ của nó cho con trỏ head. Ban đầu, head->next là nullptr.
head->next = second; không phải là sao chép dữ liệu, mà là gán địa chỉ. Nó làm cho con trỏ next của nút mà head đang trỏ tới (nút có data 10) trỏ đến cùng địa chỉ mà con trỏ second đang giữ (địa chỉ của nút có data 20).
Tương tự, second->next = third; liên kết nút 20 với nút 30.
Để truy cập dữ liệu của nút thứ hai, chúng ta không thể truy cập trực tiếp bằng tên biến second (vì head là điểm vào duy nhất). Chúng ta phải đi từ head, theo con trỏ next của nó: head->next sẽ cho ta con trỏ đến nút thứ hai. Sau đó, dùng ->data để lấy dữ liệu: head->next->data.
Để truy cập nút thứ ba, ta tiếp tục đi theo con trỏ next: head->next->next->data.
Việc quản lý bộ nhớ (delete) là cực kỳ quan trọng trong C++ khi sử dụng new. Nếu không giải phóng, bộ nhớ sẽ bị rò rỉ (memory leak). Trong ví dụ này, ta delete từng nút đã new. Tuy nhiên, cách tốt nhất để giải phóng toàn bộ danh sách là duyệt qua danh sách và xóa từng nút một cách cẩn thận (sẽ minh họa sau).

Duyệt qua Danh sách liên kết đơn

Một trong những thao tác cơ bản nhất với danh sách liên kết là duyệt qua nó để truy cập từng phần tử. Vì không có truy cập ngẫu nhiên như mảng, chúng ta phải bắt đầu từ head và theo con trỏ next từ nút này sang nút kế tiếp cho đến khi gặp nullptr.

#include <iostream>

// Định nghĩa cấu trúc của một nút (Node)
struct Node {
    int data;
    Node* next;

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

int main() {
    // Xây dựng một danh sách đơn giản: 10 -> 20 -> 30 -> nullptr
    // Sử dụng initializer list cho constructor để tạo nhanh các nút lồng nhau
    Node* head = new Node(10);
    head->next = new Node(20);
    head->next->next = new Node(30);
    // Lưu ý: Cách tạo này ngắn gọn hơn nhưng việc quản lý con trỏ trung gian cần cẩn thận
    // Cách tạo trong ví dụ trước (dùng biến second, third) rõ ràng hơn cho người mới bắt đầu.

    // Duyệt qua danh sách và in dữ liệu
    Node* current = head; // Bắt đầu từ nút đầu tiên
    cout << "Danh sach: ";
    while (current != nullptr) { // Lặp cho đến khi con trỏ hiện tại là nullptr (cuối danh sách)
        cout << current->data << " "; // In dữ liệu của nút hiện tại
        current = current->next; // Di chuyển con trỏ sang nút tiếp theo
    }
    cout << endl;

    // **RẤT QUAN TRỌNG:** Giải phóng bộ nhớ đã cấp phát!
    current = head; // Bắt đầu lại từ head để xóa
    while (current != nullptr) {
        Node* temp = current;      // Lưu con trỏ hiện tại vào biến tạm
        current = current->next;   // Di chuyển con trỏ hiện tại sang nút kế tiếp TRƯỚC KHI xóa
        delete temp;               // Xóa nút mà temp đang trỏ tới (nút ban đầu của vòng lặp này)
    }
    head = nullptr; // Sau khi xóa hết, head nên trỏ về nullptr

    return 0;
}

Giải thích:

Chúng ta tạo một con trỏ tạm thời current và khởi tạo nó bằng head. current sẽ là "người đi bộ" qua danh sách.
Vòng lặp while (current != nullptr) tiếp tục chạy miễn là current vẫn trỏ đến một nút hợp lệ (chưa đến cuối danh sách).
Bên trong vòng lặp:
- cout << current->data << " "; in ra dữ liệu của nút mà current đang trỏ tới.
- current = current->next; là bước chủ chốt. Nó cập nhật con trỏ current để trỏ đến nút tiếp theo. Nếu current đang trỏ đến nút cuối cùng, current->next sẽ là nullptr, và ở bước tiếp theo, vòng lặp sẽ kết thúc.
Phần giải phóng bộ nhớ: Vòng lặp thứ hai minh họa cách xóa toàn bộ danh sách một cách an toàn. Tại sao cần biến temp? Nếu ta xóa current trước khi di chuyển current = current->next;, ta sẽ mất khả năng truy cập đến phần còn lại của danh sách. Bằng cách lưu current vào temp, di chuyển current sang nút tiếp theo, rồi mới delete temp, chúng ta đảm bảo không bị "mất dấu" chuỗi các nút. Cuối cùng, gán head = nullptr là một cách tốt để chỉ ra rằng danh sách hiện tại đã trống.

Ưu điểm và Nhược điểm của Danh sách liên kết đơn (Khái niệm)

Dựa trên cấu trúc và cách hoạt động cơ bản, chúng ta có thể thấy vài ưu điểm và nhược điểm so với mảng:

Ưu điểm:
- Kích thước linh hoạt (Dynamic Size): Danh sách có thể dễ dàng tăng hoặc giảm kích thước trong thời gian chạy chỉ bằng cách tạo hoặc xóa nút và cập nhật con trỏ.
- Thêm/Xóa hiệu quả ở đầu danh sách: Việc thêm một nút mới vào đầu danh sách hoặc xóa nút đầu tiên chỉ cần thay đổi con trỏ head và cập nhật liên kết của nút mới (nếu thêm). Độ phức tạp O(1). Việc thêm/xóa ở các vị trí khác cần duyệt (O(n)).
Nhược điểm:
- Không truy cập ngẫu nhiên (No Random Access): Để truy cập phần tử thứ i, bạn phải bắt đầu từ head và duyệt qua i-1 nút. Độ phức tạp O(n).
- Cần thêm bộ nhớ cho con trỏ: Mỗi nút cần một con trỏ để lưu địa chỉ nút tiếp theo, tốn thêm bộ nhớ so với mảng (chỉ lưu dữ liệu).
- Duyệt chỉ theo một chiều: Chỉ có thể đi từ đầu danh sách đến cuối danh sách. Không thể đi ngược lại dễ dàng (trừ khi dùng danh sách liên kết đôi).

Bài tập ví dụ: C++ Bài 21.A1: Điểm Mana

Điểm Mana

Mô tả

FullHouse Dev đang chơi một trò chơi di động. Trong trò chơi này, FullHouse Dev có thể thực hiện các đòn tấn công đặc biệt. Tuy nhiên, mỗi đòn tấn công đặc biệt tiêu tốn X điểm mana.

Nếu FullHouse Dev hiện có Y điểm mana, hãy xác định số lượng đòn tấn công đặc biệt tối đa mà anh ấy có thể thực hiện.

Input

Dòng đầu tiên chứa một số nguyên T - số lượng test case.
Mỗi test case gồm một dòng chứa hai số nguyên X và Y cách nhau bởi dấu cách - chi phí của một đòn tấn công đặc biệt và số điểm mana FullHouse Dev có ban đầu.

Output

Với mỗi test case, in ra số lượng đòn tấn công đặc biệt tối đa mà FullHouse Dev có thể thực hiện.

Ràng buộc

\(1 ≤ T ≤ 10^5\)
\(1 ≤ X ≤ 100\)
\(1 ≤ Y ≤ 1000\)

Ví dụ

Input:

Output:

3
6
8

Giải thích

Test case 1: FullHouse Dev có thể thực hiện 3 đòn tấn công đặc biệt, mỗi đòn tiêu tốn 10 điểm mana, tổng cộng 30 điểm mana.
Test case 2: FullHouse Dev có thể thực hiện 6 đòn tấn công đặc biệt, mỗi đòn tiêu tốn 6 điểm mana, tổng cộng 36 điểm mana. Còn lại 5 điểm mana không đủ để thực hiện thêm đòn tấn công nào.
Test case 3: FullHouse Dev có thể thực hiện 8 đòn tấn công đặc biệt, mỗi đòn tiêu tốn 50 điểm mana, tổng cộng 400 điểm mana. Chào bạn, đây là hướng dẫn giải bài tập "Điểm Mana" bằng C++ theo yêu cầu:

Bài toán yêu cầu tìm số lần tối đa bạn có thể thực hiện một hành động (đòn tấn công) khi mỗi lần tiêu tốn một lượng tài nguyên nhất định (X mana) và bạn có tổng cộng một lượng tài nguyên khác (Y mana).

Phân tích bài toán:

Đây là một bài toán chia đơn giản. Nếu bạn có Y mana và mỗi đòn tấn công tốn X mana, thì số lần tấn công tối đa bạn có thể thực hiện chính là số lần X "vừa vặn" chứa trong Y. Bất kỳ lượng mana còn lại nào nhỏ hơn X sẽ không đủ để thực hiện thêm một đòn tấn công nữa.

Trong lập trình, phép toán này chính là phép chia nguyên (integer division).

Hướng giải chi tiết:

Đọc số lượng test case: Bạn cần đọc giá trị T đầu tiên để biết có bao nhiêu bộ dữ liệu cần xử lý.
Vòng lặp xử lý test case: Sử dụng một vòng lặp (ví dụ: while hoặc for) để lặp lại T lần. Mỗi lần lặp sẽ xử lý một test case.
Đọc dữ liệu cho mỗi test case: Bên trong vòng lặp, đọc hai số nguyên X và Y cho mỗi test case.
Tính toán kết quả: Thực hiện phép chia nguyên Y / X. Kết quả của phép chia nguyên này chính là số đòn tấn công tối đa có thể thực hiện.
In kết quả: In kết quả của phép chia nguyên ra màn hình. Đảm bảo in mỗi kết quả trên một dòng riêng biệt (sử dụng ký tự xuống dòng).
Sử dụng thư viện chuẩn: Cần bao gồm thư viện iostream để sử dụng các hàm nhập/xuất chuẩn như cin và cout.
Kiểu dữ liệu: Với ràng buộc Y <= 1000 và X <= 100, kiểu dữ liệu int là đủ để lưu trữ X, Y và kết quả.

Ví dụ logic với các test case:

X=10, Y=30: 30 chia nguyên cho 10 bằng 3. (3 * 10 = 30 mana dùng hết)
X=6, Y=41: 41 chia nguyên cho 6 bằng 6. (6 * 6 = 36 mana dùng, còn lại 5 mana không đủ cho đòn tiếp theo)
X=50, Y=400: 400 chia nguyên cho 50 bằng 8. (8 * 50 = 400 mana dùng hết)

Gợi ý về cấu trúc code (không phải code hoàn chỉnh):

#include <iostream> // Can including this header

int main() {
    // Optimize I/O (optional but good practice for competitive programming)
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    // Read T

    // Loop T times
    while (T--) {
        int X, Y;
        // Read X and Y

        // Calculate the result using integer division

        // Print the result followed by a newline using cout
    }

    return 0;
}

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.