Khóa học C++ từ cơ bản đến nâng cao

Bài 33.4: So sánh danh sách liên kết và mảng trong C++

Chào mừng trở lại với chuỗi bài viết 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 là một quyết định quan trọng ảnh hưởng lớn đến hiệu suất và sự dễ bảo trì của chương trình. Hôm nay, chúng ta sẽ đi sâu vào so sánh hai trong số những cấu trúc dữ liệu cơ bản và phổ biến nhất: Mảng (Array) và Danh sách liên kết (Linked List). Cả hai đều được dùng để lưu trữ tập hợp các phần tử, nhưng cách chúng hoạt động và tối ưu cho các tác vụ khác nhau lại hoàn toàn khác biệt. Hãy cùng khám phá!

Mảng (Array): "Người hàng xóm" quen thuộc

Mảng là một cấu trúc dữ liệu lưu trữ các phần tử có cùng kiểu dữ liệu trong các ô nhớ liên tục (contiguous memory). Mỗi phần tử được gán một chỉ mục (index), bắt đầu từ 0.

Đặc điểm nổi bật của Mảng:

• Bộ nhớ liên tục: Các phần tử nằm cạnh nhau trong RAM.
• Kích thước cố định: Khi khai báo mảng tĩnh (như int arr[10];), kích thước được định trước và không thay đổi được. (Lưu ý: vector trong C++ là một mảng động, có thể thay đổi kích thước, nhưng nguyên lý bên dưới vẫn là mảng liên tục).
• Truy cập ngẫu nhiên (Random Access): Bạn có thể truy cập bất kỳ phần tử nào ngay lập tức chỉ bằng chỉ mục của nó (ví dụ: arr[5]). Đây là một ưu điểm vượt trội của mảng.

Ví dụ minh họa truy cập phần tử mảng:

#include <iostream>
#include <vector> // Sử dụng vector cho mảng động

int main() {
    // Mảng tĩnh
    int static_arr[5] = {10, 20, 30, 40, 50};
    cout << "Phan tu thu 2 (chi muc 1) trong mang tinh: " << static_arr[1] << endl; // Truy cap nhanh

    // Mảng động (vector)
    vector<int> dynamic_arr = {100, 200, 300, 400, 500};
    cout << "Phan tu thu 4 (chi muc 3) trong vector: " << dynamic_arr[3] << endl; // Truy cap nhanh

    return 0;
}

Giải thích: Trong cả hai trường hợp, việc truy cập phần tử static_arr[1] hoặc dynamic_arr[3] là hành động có độ phức tạp O(1). Hệ thống chỉ cần tính toán địa chỉ bộ nhớ dựa trên địa chỉ gốc của mảng và chỉ mục, công việc này diễn ra cực kỳ nhanh.

Danh sách liên kết (Linked List): "Chuỗi dây" linh hoạt

Ngược lại với mảng, danh sách liên kết lưu trữ các phần tử (gọi là node) ở các vị trí bộ nhớ không nhất thiết phải liên tục. Mỗi node chứa hai thành phần chính: dữ liệu của phần tử đó và một con trỏ (pointer) trỏ đến node kế tiếp trong danh sách.

Đặc điểm nổi bật của Danh sách liên kết:

• Bộ nhớ không liên tục: Các node có thể nằm rải rác trong bộ nhớ.
• Kích thước động: Dễ dàng thêm hoặc xóa node, kích thước của danh sách có thể thay đổi linh hoạt trong quá trình chạy.
• Truy cập tuần tự (Sequential Access): Để truy cập một phần tử, bạn phải bắt đầu từ đầu danh sách (node đầu tiên - head) và đi theo các con trỏ từ node này sang node khác cho đến khi tìm thấy phần tử mong muốn. Bạn không thể nhảy thẳng đến một phần tử bằng chỉ mục.

Ví dụ minh họa cấu trúc node đơn giản và duyệt danh sách:

#include <iostream>

// Dinh nghia cau truc mot Node cua danh sach lien ket don
struct Node {
    int data;       // Du lieu cua node
    Node* next;     // Con tro tro den node tiep theo

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

    // Destructor (de phong tranh memory leak khi xoa node)
    ~Node() {
        // Trong vi du don gian, destructor nay co the khong can thiet,
        // nhung quan trong cho viec quan ly bo nho day du hon
        // cout << "Deleting Node with data: " << data << endl;
    }
};

int main() {
    // Tao mot danh sach lien ket don: 10 -> 20 -> 30
    Node* head = new Node(10);     // Node dau tien
    head->next = new Node(20);     // Node thu hai
    head->next->next = new Node(30); // Node thu ba

    // Duyet va in cac phan tu
    Node* current = head;
    cout << "Cac phan tu trong danh sach lien ket: ";
    while (current != nullptr) {
        cout << current->data << " "; // Truy cap du lieu
        current = current->next;           // Di chuyen sang node tiep theo
    }
    cout << endl;

    // Giai phong bo nho (quan trong!)
    // Cach giai phong bo nho mot cach don gian trong vi du nay:
    Node* temp;
    while (head != nullptr) {
        temp = head;
        head = head->next;
        delete temp; // Giai phong tung node mot
    }

    return 0;
}

Giải thích: Đoạn code trên định nghĩa một cấu trúc Node đơn giản và tạo ra một danh sách 3 node. Để in các phần tử, chúng ta bắt đầu từ head và dùng vòng lặp while, di chuyển con trỏ current từ head sang head->next, rồi head->next->next, v.v., cho đến khi gặp nullptr. Việc truy cập đến phần tử thứ k sẽ đòi hỏi k-1 bước đi qua các con trỏ, đây là hoạt động có độ phức tạp O(n). Phần cuối là ví dụ về cách giải phóng bộ nhớ thủ công, một bước quan trọng khi làm việc với con trỏ trong C++.

Mảng vs Danh sách liên kết: Cuộc đối đầu kinh điển

Bây giờ, hãy đặt chúng lên bàn cân dựa trên các tiêu chí quan trọng:

1. Cấu trúc bộ nhớ và Phân bổ bộ nhớ

• Mảng: Các phần tử lưu trữ ở các vị trí liên tục. Điều này giúp tận dụng tốt bộ nhớ cache của CPU, dẫn đến hiệu suất cao khi truy cập tuần tự hoặc truy cập các phần tử gần nhau. Tuy nhiên, việc cấp phát bộ nhớ liên tục với kích thước lớn có thể gặp khó khăn nếu không có đủ khối bộ nhớ trống đủ lớn.
• Danh sách liên kết: Các node lưu trữ rời rạc trong bộ nhớ, kết nối bằng con trỏ. Điều này giúp việc cấp phát bộ nhớ dễ dàng hơn (chỉ cần tìm một khối nhỏ đủ cho một node), nhưng lại có thể làm giảm hiệu suất bộ nhớ cache. Mỗi node cũng tốn thêm bộ nhớ cho con trỏ (hoặc nhiều con trỏ trong danh sách liên kết đôi).

2. Kích thước

• Mảng (tĩnh): Kích thước được cố định khi khai báo. Không thể thay đổi sau đó. vector giải quyết vấn đề này bằng cách tự động cấp phát lại và sao chép dữ liệu khi cần mở rộng, nhưng thao tác này có thể tốn kém.
• Danh sách liên kết: Kích thước linh hoạt, có thể tăng hoặc giảm dễ dàng bằng cách thêm hoặc xóa node.

3. Truy cập phần tử

• Mảng: Truy cập ngẫu nhiên theo chỉ mục. Độ phức tạp là O(1).
• Danh sách liên kết: Truy cập tuần tự. Để truy cập phần tử thứ k, cần duyệt k-1 node. Độ phức tạp là O(n) (n là số lượng phần tử hoặc chỉ mục cần truy cập).

4. Thêm hoặc xóa phần tử

Đây là điểm khác biệt quan trọng nhất về hiệu suất.

• Mảng:
  • Thêm/xóa ở cuối (với vector): Trung bình O(1), nhưng worst case là O(n) khi cần cấp phát lại bộ nhớ.
  • Thêm/xóa ở đầu hoặc giữa: Cần phải dịch chuyển tất cả các phần tử sau vị trí đó để tạo chỗ trống hoặc lấp đầy chỗ trống. Độ phức tạp là O(n).
• Danh sách liên kết:
  • Thêm/xóa ở đầu: Rất nhanh, chỉ cần cập nhật con trỏ head và con trỏ của node mới/cũ. Độ phức tạp O(1).
  • Thêm/xóa ở cuối: Với danh sách liên kết đơn thông thường, cần duyệt đến cuối (O(n)). Với danh sách liên kết đơn giữ con trỏ tail hoặc danh sách liên kết đôi, có thể là O(1).
  • Thêm/xóa ở giữa: Nếu bạn đã có con trỏ trỏ đến node trước vị trí cần thêm/xóa, thao tác chỉ là thay đổi vài con trỏ. Độ phức tạp O(1). Tuy nhiên, việc tìm đến vị trí đó vẫn mất O(n) nếu phải bắt đầu từ đầu.

Ví dụ minh họa Thêm/Xóa ở giữa:

Thêm vào giữa Mảng (vector):

#include <iostream>
#include <vector>
#include <algorithm> // Can de su dung for_each

int main() {
    vector<int> vec = {10, 20, 40, 50};
    // Muon chen 30 vao giua 20 va 40 (tai chi muc 2)

    // Tim iterator den vi tri can chen
    auto it = vec.begin() + 2;

    // Chen phan tu
    vec.insert(it, 30); // Thao tac nay yeu cau dich chuyen cac phan tu sau do

    cout << "Vector sau khi chen: ";
    for_each(vec.begin(), vec.end(), [](int x){
        cout << x << " ";
    });
    cout << endl;

    return 0;
}

Giải thích: Hàm vec.insert(it, 30) phải di chuyển các phần tử 40 và 50 sang phải để tạo chỗ cho 30. Nếu vector lớn, thao tác này tốn thời gian tương ứng với số lượng phần tử cần di chuyển (độ phức tạp O(n)).

Thêm vào giữa Danh sách liên kết đơn (giả định có con trỏ đến node trước đó):

#include <iostream>

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
    ~Node() { /* cout << "Deleting Node with data: " << data << endl; */ }
};

int main() {
    // Tao danh sach: 10 -> 20 -> 40 -> 50
    Node* head = new Node(10);
    Node* node_20 = new Node(20);
    Node* node_40 = new Node(40);
    Node* node_50 = new Node(50);

    head->next = node_20;
    node_20->next = node_40;
    node_40->next = node_50;

    // Muon chen 30 vao sau node_20 (sau so 20)
    Node* new_node = new Node(30);

    // Thao tac chen: Chi can thay doi con tro
    new_node->next = node_20->next; // Con tro cua node moi tro den node 40
    node_20->next = new_node;       // Con trỏ của node 20 trỏ đến node mới (30)

    cout << "Danh sach lien ket sau khi chen: ";
    Node* current = head;
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;

    // Giai phong bo nho...
    Node* temp;
    current = head; // Bat dau giai phong tu head
    while (current != nullptr) {
        temp = current;
        current = current->next;
        delete temp;
    }

    return 0;
}

Giải thích: Nếu chúng ta đã có con trỏ node_20 (trỏ đến node có giá trị 20), việc chèn node mới (30) chỉ bao gồm 2 bước thay đổi con trỏ: new_node->next = node_20->next; và node_20->next = new_node;. Thao tác này có độ phức tạp O(1), không phụ thuộc vào kích thước danh sách. Tuy nhiên, việc tìm ra node_20 ban đầu có thể mất O(n) nếu phải duyệt từ đầu.

5. Chi phí bộ nhớ

• Mảng: Chỉ lưu trữ dữ liệu. Hiệu quả về bộ nhớ nếu kích thước cố định và không cần nhiều thao tác thêm/xóa ở giữa. vector có thể có một chút bộ nhớ dự phòng.
• Danh sách liên kết: Mỗi node lưu trữ dữ liệu và một hoặc nhiều con trỏ. Điều này tạo ra chi phí bộ nhớ lớn hơn cho mỗi phần tử so với mảng.

6. Hiệu suất Cache

• Mảng: Do nằm liên tục, mảng tận dụng rất tốt bộ nhớ cache của CPU. Khi bạn truy cập một phần tử, CPU có thể tải sẵn các phần tử lân cận vào cache, giúp các lần truy cập tiếp theo rất nhanh.
• Danh sách liên kết: Do các node nằm rải rác, việc truy cập một node có thể dẫn đến tình trạng "cache miss" (dữ liệu không có trong cache), buộc CPU phải đọc từ RAM, làm chậm quá trình xử lý.

Bảng Tóm tắt So sánh:

Khi nào sử dụng Mảng và khi nào sử dụng Danh sách liên kết?

Việc lựa chọn phụ thuộc vào các thao tác mà bạn sẽ thực hiện nhiều nhất trên cấu trúc dữ liệu của mình:

• Nên dùng Mảng (hoặc vector):

  • Khi bạn biết trước hoặc có thể ước tính được kích thước dữ liệu.
  • Khi bạn cần truy cập ngẫu nhiên các phần tử thường xuyên.
  • Khi bạn thực hiện nhiều thao tác thêm/xóa ở cuối danh sách (vector rất hiệu quả cho việc này).
  • Khi hiệu suất bộ nhớ cache là quan trọng.

• Nên dùng Danh sách liên kết (hoặc list):

  • Khi bạn cần một cấu trúc dữ liệu có kích thước thay đổi liên tục và khó dự đoán.
  • Khi bạn thực hiện nhiều thao tác thêm hoặc xóa phần tử ở đầu hoặc giữa danh sách (và bạn có thể dễ dàng có được con trỏ đến vị trí cần thao tác).
  • Khi việc chèn/xóa ở giữa là phổ biến hơn nhiều so với việc truy cập ngẫu nhiên.

Về vector và list trong C++ STL:

Thư viện chuẩn C++ (STL) cung cấp các container vector và list, là những triển khai phổ biến của mảng động và danh sách liên kết đôi.

• vector: Hoạt động dựa trên nguyên lý mảng động. Cung cấp truy cập ngẫu nhiên O(1). Thêm/xóa ở cuối trung bình O(1), nhưng thêm/xóa ở đầu/giữa là O(n). Thường là lựa chọn mặc định tốt nếu bạn không có lý do cụ thể để dùng danh sách liên kết.
• list: Là danh sách liên kết đôi (mỗi node có con trỏ tới node trước và sau). Hỗ trợ thêm/xóa O(1) ở bất kỳ vị trí nào nếu bạn có iterator trỏ đến vị trí đó. Tuy nhiên, truy cập theo chỉ mục là O(n). Tốn bộ nhớ hơn vector do hai con trỏ trên mỗi node.

Hiểu rõ nguyên tắc hoạt động của mảng và danh sách liên kết giúp bạn sử dụng hiệu quả vector và list trong STL.

Bài tập ví dụ: C++ Bài 21.B1: Sách của FullHouse Dev

Sách của FullHouse Dev

FullHouse Dev đang chuẩn bị cho kỳ thi sắp tới. Cuốn sách giáo khoa có tổng cộng N trang. FullHouse Dev muốn đọc tối đa X trang mỗi ngày trong Y ngày.

Hãy xác định xem liệu FullHouse Dev có thể hoàn thành việc đọc toàn bộ cuốn sách hay không.

INPUT FORMAT

• Dòng đầu tiên chứa số nguyên T — số lượng bộ test.
• Mỗi bộ test gồm một dòng chứa ba số nguyên cách nhau bởi dấu cách N, X, và Y — số trang sách, số trang FullHouse Dev có thể đọc trong một ngày, và số ngày.

OUTPUT FORMAT

• Với mỗi bộ test, in ra trên một dòng mới "YES" nếu FullHouse Dev có thể hoàn thành toàn bộ cuốn sách trong thời gian cho phép, và "NO" nếu không thể.

CONSTRAINTS

• 1 ≤ T ≤ 1000
• 1 ≤ N ≤ 100
• 1 ≤ X, Y ≤ 10

Ví dụ

Input

4
5 2 3
10 3 3
7 7 1
3 2 1

Output

YES
NO
YES
NO

Giải thích:

• Test 1: FullHouse Dev có thể đọc hai trang vào ngày đầu tiên, hai trang vào ngày thứ hai, và một trang còn lại vào ngày thứ ba.
• Test 2: FullHouse Dev không thể hoàn thành tất cả mười trang trong ba ngày.
• Test 3: FullHouse Dev có thể đọc tất cả bảy trang trong một ngày.
• Test 4: FullHouse Dev không thể hoàn thành tất cả ba trang trong một ngày. Tuyệt vời, đây là hướng dẫn để giải bài tập này bằng C++ theo yêu cầu của bạn:

1. Bao gồm thư viện cần thiết: Bạn sẽ cần thư viện cho phép nhập và xuất dữ liệu. Thư viện chuẩn của C++ cho việc này là iostream.

2. Hàm main: Mọi chương trình C++ bắt đầu thực thi từ hàm main.

3. Tối ưu hóa I/O (Tùy chọn nhưng nên dùng trong competitive programming): Để tăng tốc độ đọc và ghi dữ liệu, đặc biệt khi có nhiều bộ test, bạn có thể thêm hai dòng sau vào đầu hàm main:

   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   

   Điều này ngắt kết nối giữa luồng I/O của C++ và C, đồng thời gỡ bỏ ràng buộc giữa cin và cout.

4. Đọc số lượng bộ test: Đọc giá trị T từ đầu vào chuẩn (cin).

5. Xử lý từng bộ test: Sử dụng một vòng lặp để lặp lại T lần. Mỗi lần lặp tương ứng với một bộ test. Vòng lặp while (T--) là một cách ngắn gọn để làm điều này.

6. Đọc dữ liệu cho mỗi bộ test: Bên trong vòng lặp, đọc ba số nguyên N, X, và Y từ đầu vào chuẩn (cin).

7. Logic chính:

   • FullHouse Dev có Y ngày để đọc sách.
   • Mỗi ngày, FullHouse Dev có thể đọc tối đa X trang.
   • Tổng số trang tối đa FullHouse Dev có thể đọc trong Y ngày là X * Y.
   • Để hoàn thành cuốn sách có N trang, tổng số trang tối đa có thể đọc (X * Y) phải lớn hơn hoặc bằng tổng số trang của cuốn sách (N).

8. So sánh và in kết quả:

   • Sử dụng một câu lệnh điều kiện (if / else) để kiểm tra xem (X * Y) có lớn hơn hoặc bằng N hay không.
   • Nếu điều kiện (X * Y >= N) đúng, in ra "YES" ra đầu ra chuẩn (cout).
   • Nếu điều kiện sai (X * Y < N), in ra "NO" ra đầu ra chuẩn (cout).
   • Đảm bảo in ký tự xuống dòng ('\n' hoặc endl) sau mỗi kết quả "YES" hoặc "NO".

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