Mảng (Array) là cấu trúc dữ liệu lưu trữ các phần tử nằm liên tiếp nhau trên bộ nhớ RAM. Mảng có nhược điểm lớn: kích thước cố định khó mở rộng, và thao tác chèn/xóa phần tử ở giữa mảng cực kỳ tốn hiệu năng (do phải dịch chuyển hàng loạt phần tử phía sau). Để khắc phục vấn đề này, người ta sử dụng các cấu trúc dữ liệu liên kết động. Trong bài học này, chúng ta sẽ kết hợp struct và con trỏ cấp phát động để tự tay triển khai 3 cấu trúc dữ liệu kinh điển: Danh sách liên kết đơn (Singly Linked List), Ngăn xếp (Stack), và Hàng đợi (Queue).

1. Hiệu năng mức phần cứng: CPU Cache Locality & Spatial Locality

Trước khi đi sâu vào code, chúng ta cần hiểu bản chất phần cứng: tại sao cùng một độ phức tạp thuật toán, việc truy xuất mảng tuần tự lại nhanh hơn duyệt danh sách liên kết gấp hàng chục lần? Câu trả lời nằm ở CPU Cache Locality.

Bản chất của Cache Line và Nạp trước ô nhớ:

CPU không bao giờ đọc trực tiếp từng byte dữ liệu từ RAM vì tốc độ truy xuất RAM quá chậm (chênh lệch hàng trăm lần so với tốc độ tính toán của CPU). Thay vào đó, mỗi lần đọc dữ liệu, CPU sẽ nạp một khối dữ liệu liên tục gọi là Cache Line (thường có kích thước 64 bytes) từ RAM vào bộ nhớ đệm tốc độ cao L1/L2/L3 Cache.

Nguyên lý Lân cận Không gian (Spatial Locality):

Khi bạn truy cập phần tử arr[0] của một mảng:

  • Hệ thống sẽ nạp cả arr[0], arr[1], arr[2], arr[3]... (tối đa 64 bytes liên tiếp) vào CPU Cache trong một lượt đọc.
  • Khi vòng lặp chạy tới arr[1], CPU không cần đọc từ RAM nữa mà lấy trực tiếp từ L1 Cache. Đây gọi là Cache Hit (thời gian truy cập cực nhanh, dưới 1ns).

Ngược lại, với Danh sách liên kết (Linked List):

  • Các Node được cấp phát động thông qua malloc() tại các thời điểm khác nhau, nằm rải rác ngẫu nhiên trên Heap.
  • Khi truy cập node1->next, địa chỉ của Node tiếp theo thường nằm ở một phân vùng RAM hoàn toàn khác. CPU buộc phải hủy bộ nhớ đệm cũ và thực hiện một lệnh đọc RAM mới. Đây gọi là Cache Miss. Việc liên tục gặp Cache Miss khiến tốc độ duyệt danh sách liên kết cực kỳ chậm trên các CPU hiện đại (hay còn gọi là hiện tượng nghẽn cổ chai bộ nhớ - Memory Wall). 
Mảng (Contiguous Memory):
[ Node 0 ][ Node 1 ][ Node 2 ][ Node 3 ] <--- Tải toàn bộ vào CPU Cache trong 1 chu kỳ

Danh sách liên kết (Scattered Memory):
[ Node 0 ] ----(con trỏ trỏ tới địa chỉ ngẫu nhiên)---> [ Node 1 ] (Cache Miss!)
  Địa chỉ: 0x1000                                       Địa chỉ: 0x5000

2. Phân tích chi phí: Độ phức tạp thuật toán (Big O Notation)

Khi thiết kế một phần mềm hoặc giải quyết một bài toán, chúng ta có thể đưa ra nhiều thuật toán khác nhau. Để đánh giá thuật toán nào chạy nhanh hơn hay sử dụng ít tài nguyên máy tính hơn, khoa học máy tính sử dụng ký pháp toán học Big O Notation.

Big O đo lường tốc độ tăng trưởng (growth rate) về số lượng các phép toán cơ bản (Time Complexity) hoặc lượng bộ nhớ RAM tiêu thụ thêm (Space Complexity) khi kích thước dữ liệu đầu vào ($N$) tiến tới vô cùng ($N \to \infty$).

Biểu đồ tốc độ tăng trưởng của các lớp Big O thông dụng:

Tốc độ tăng trưởng (Thời gian chạy / Số phép tính)
 ^
 |                                                    / O(2^N) (Thời gian mũ - Tệ nhất)
 |                                                   /
 |                                                  /   / O(N^2) (Bậc hai - Tệ khi N lớn)
 |                                                 /   /
 |                                                /   /     / O(N log N) (Tốt - Quick/Merge Sort)
 |                                               /   /     /
 |                                              /   /     /   / O(N) (Tuyến tính - Duyệt mảng)
 |                                             /   /     /   /
 |                                            /   /     /   /     / O(log N) (Lôgarit - Tìm kiếm nhị phân)
 |                                           /   /     /   /     /
 |                                          /   /     /   /     /_______ O(1) (Hằng số - Thao tác tức thời)
 +-----------------------------------------------------------------------> Kích thước dữ liệu (N)

2.1. Bản chất toán học và Quy tắc đơn giản hóa

Về mặt toán học, ta nói $f(N) = O(g(N))$ nếu tồn tại các hằng số dương $c$ và $N_0$ sao cho:

\(f(N) \le c \times g(N) \quad \text{với mọi} \quad N \ge N_0\)

Trong phân tích thực tế, ta luôn áp dụng hai quy tắc đơn giản hóa cốt lõi:

  • Bỏ qua các hệ số nhân (Drop Constants): Thuật toán tốn $3N$ bước hay $100N$ bước đều có độ phức tạp là $O(N)$ vì hệ số nhân không làm thay đổi hình dáng đường cong tăng trưởng của đồ thị khi $N$ cực kỳ lớn.
  • Chỉ giữ lại số hạng bậc cao nhất (Keep Dominant Term): Với hàm chi phí $f(N) = 3N^2 + 50N + 1000$, khi $N = 1.000.000$, số hạng $3N^2$ ($3 \times 10^{12}$) chiếm tỉ lệ áp đảo hoàn toàn so với $50N$ ($5 \times 10^7$) và hằng số $1000$. Do đó, ta lược bỏ các số hạng bậc thấp và viết gọn là $O(N^2)$.

2.2. Hai quy tắc phân tích mã nguồn thực tế

  1. Quy tắc cộng (Sum Rule): Nếu thuật toán gồm các khối lệnh chạy tuần tự tiếp nối nhau:

    \(O(f(N)) + O(g(N)) = O(\max(f(N), g(N)))\)

    Ví dụ: Khối 1 duyệt mảng 1 lần ($O(N)$), khối 2 có 2 vòng lặp lồng nhau ($O(N^2)$). Tổng độ phức tạp là $O(N + N^2) = O(N^2)$.
  2. Quy tắc nhân (Product Rule): Nếu thuật toán chứa các vòng lặp lồng nhau hoặc gọi hàm lặp lại:

    \(O(f(N)) \times O(g(N)) = O(f(N) \times g(N))\)

    Ví dụ: Vòng lặp ngoài chạy $N$ lần, vòng lặp trong chạy $N$ lần. Tổng độ phức tạp là $O(N \times N) = O(N^2)$.

2.3. Chi tiết các lớp độ phức tạp thời gian (Time Complexity)

1. $O(1)$ — Constant Time (Thời gian hằng số)

Thời gian thực thi không đổi, hoàn toàn độc lập với kích thước $N$. Lưu ý: Một hàm chứa vòng lặp có số lần chạy cố định (ví dụ chạy đúng 1000 lần) vẫn được tính là $O(1)$.

constant_time.c 
// Direct access to a cell by array index is O(1)
int getElement(int arr[], int index) {
    return arr[index];
}

// A loop of a fixed 100 iterations, independent of N, is still O(1)
void printHeader() {
    for (int i = 0; i < 100; i++) {
        printf("-");
    }
}

Cả hai hàm đều là O(1) dù hàm thứ hai chạy 100 vòng lặp. Điểm mấu chốt: Big O đo tốc độ tăng theo N, không đo số phép tính tuyệt đối. 100 vòng cố định vẫn là 100 vòng dù N là 10 hay 10 triệu — nên nó không tăng theo N, và vì thế vẫn là hằng số.

2. $O(\log N)$ — Logarithmic Time (Thời gian Lôgarit)

Cực kỳ tối ưu. Sau mỗi phép toán, không gian cần tìm kiếm hoặc xử lý giảm đi một nửa. Lôgarit cơ số 2 ($\log_2 N$) đại diện cho số lần bạn có thể chia $N$ cho 2 trước khi kết quả nhỏ hơn hoặc bằng 1.

logarithmic_time.c 
// Binary search over a sorted array
int binarySearch(int arr[], int size, int target) {
    int left = 0, right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // Avoids integer overflow
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1; // Discard the left half
        else right = mid - 1;                // Discard the right half
    }
    return -1;
}

Mỗi vòng lặp vứt đi một nửa số phần tử còn lại — đó là dấu hiệu nhận ra O(log N). Với mảng 1 triệu phần tử, tìm kiếm nhị phân cần tối đa khoảng 20 bước. Dòng left + (right - left) / 2 viết như vậy thay vì (left + right) / 2 để tránh tràn số nguyên khi cả hai chỉ số đều lớn — một lỗi từng tồn tại nhiều năm trong thư viện chuẩn Java.

3. $O(N)$ — Linear Time (Thời gian tuyến tính)

Thời gian chạy tăng tuyến tính tỷ lệ thuận với $N$. Điển hình là các thuật toán duyệt mảng 1 vòng lặp hoặc duyệt qua danh sách liên kết.

linear_time.c 
// Walk the whole array, searching sequentially
int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) return i; // Worst case visits all N elements
    }
    return -1;
}

Khác biệt với bản nhị phân ở trên: hàm này không đòi mảng phải sắp xếp, và cái giá là phải duyệt tuần tự. Với mảng 1 triệu phần tử, trường hợp tệ nhất là 1 triệu phép so sánh thay vì 20. Đó chính là khoảng cách giữa O(N) và O(log N).

4. $O(N \log N)$ — Linearithmic Time (Thời gian Tuyến tính Lôgarit)

Đây là giới hạn tối thiểu về mặt toán học đối với các thuật toán sắp xếp dựa trên so sánh (như Merge Sort, Quick Sort, Heap Sort). Thuật toán chia dữ liệu làm đôi $\log N$ lần, và ở mỗi cấp độ phân tách, ta thực hiện ghép/duyệt tuyến tính tốn chi phí $O(N)$.

5. $O(N^2)$ — Quadratic Time (Thời gian bậc hai)

Thời gian chạy tăng theo bình phương của kích thước dữ liệu. Rất dễ gặp khi viết các thuật toán sắp xếp sơ cấp (Bubble Sort, Selection Sort) hoặc xử lý ma trận $N \times N$.

⚠️ Cạm bẫy: vòng lặp giảm dần
Một số bạn lầm tưởng nếu vòng lặp trong chạy giảm dần từ $0$ tới $i$ thì không phải $O(N^2)$. Bản chất tổng số bước chạy là cấp số cộng: $1 + 2 + 3 + \dots + N = \frac{N(N+1)}{2} = \frac{N^2}{2} + \frac{N}{2} \approx O(N^2)$.
quadratic_time.c 
// Print every pair of elements in the array
void printAllPairs(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        for (int j = i + 1; j < size; j++) { // Shrinks as i grows
            printf("(%d, %d)\n", arr[i], arr[j]); // Still O(N^2)
        }
    }
}

Chú ý vòng trong bắt đầu từ i + 1 chứ không phải 0, nên tổng số lần chạy là khoảng N²/2 chứ không phải N². Nhưng Big O bỏ hằng số, nên nó vẫn là O(N²) — và điều đó có nghĩa thật: tăng N gấp đôi thì thời gian chạy tăng gấp bốn.

6. Các lớp thời gian nguy hiểm: $O(2^N)$ và $O(N!)$

  • $O(2^N)$ — Exponential Time (Thời gian mũ): Tốc độ tăng trưởng cực kỳ khủng khiếp, gấp đôi số lượng phép tính mỗi khi $N$ tăng lên 1 đơn vị. Điển hình là đệ quy tìm số Fibonacci không tối ưu hoặc thuật toán sinh chuỗi nhị phân độ dài $N$. 
    // Naive recursive Fibonacci (no memoisation) costs O(2^N)
int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2); // Each parent spawns 2 branches
}
  • $O(N!)$ — Factorial Time (Thời gian giai thừa): Lớp phức tạp tệ nhất trong máy tính. Chỉ cần $N = 20$, máy siêu tính toán cũng phải chạy hàng chục năm. Điển hình là bài toán duyệt vét cạn sinh các hoán vị (ví dụ: bài toán Người bán hàng - Traveling Salesperson Problem bằng vét cạn).

2.4. Ba trạng thái đánh giá thuật toán (Best, Average, Worst Case)

  • Best Case ($\Omega$ - Omega): Số bước chạy tối thiểu khi gặp dữ liệu thuận lợi nhất (ví dụ: Tìm kiếm phần tử ở ngay vị trí arr[0] tốn $O(1)$). Rất ít giá trị thực tế.
  • Worst Case ($O$ - Big O): Ngưỡng giới hạn trên (Upper bound), bảo đảm rằng thời gian chạy không thể vượt quá giá trị này dù dữ liệu đầu vào có tệ đến đâu. Đây là mốc đánh giá quan trọng nhất trong phát triển phần mềm.
  • Average Case ($\Theta$ - Theta): Phản ánh đúng hiệu năng trung bình của ứng dụng trong thực tế chạy trên tập dữ liệu ngẫu nhiên.

2.5. Độ phức tạp không gian (Space Complexity) & Độ sâu của Call Stack

Độ phức tạp không gian đo lượng bộ nhớ RAM phụ trội (ngoại trừ dữ liệu đầu vào gốc) phát sinh trong suốt vòng đời thực thi của thuật toán.

  • Không gian Heap: Xảy ra khi bạn chủ động cấp phát bộ nhớ động bằng các lệnh như malloc() hay calloc().
  • Không gian Stack (Call Stack Depth): Đây là điểm mấu chốt dễ gây lỗi Stack Overflow. Khi một hàm gọi đệ quy, máy tính phải cấp phát một ngăn chứa bộ nhớ (Stack Frame) trên Call Stack để lưu trữ địa chỉ trả về và các biến cục bộ của hàm đó. Khối nhớ này chỉ được giải phóng khi hàm kết thúc.

Hãy so sánh chi phí bộ nhớ giữa cách tiếp cận Đệ quy và Vòng lặp thông thường:

space_complexity_comparison.c 
// OPTION 1: RECURSION (sum from 1 to N)
// Recurses N deep, so the call stack holds N stack frames at once
// => Time: O(N) | Space: O(N) (easy to blow the stack for large N)
int sumRecursive(int n) {
    if (n <= 1) return n;
    return n + sumRecursive(n - 1);
}

// OPTION 2: ITERATION (sum from 1 to N)
// Uses one fixed sum variable, in a single stack frame
// => Time: O(N) | Space: O(1) (safe, and minimal RAM)
int sumIterative(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}
💡 Quy tắc đánh đổi (trade-off)
Trong lập trình thực tế, chúng ta thường tối ưu tốc độ chạy thuật toán bằng cách dùng thêm bộ nhớ đệm (như bảng băm Hash Table hoặc mảng phụ lưu kết quả trung gian Memoization). Đây là quy tắc đánh đổi không gian lấy thời gian (space-time trade-off).

3. Danh sách liên kết đơn (Singly Linked List)

Một danh sách liên kết được cấu thành từ nhiều nút dữ liệu rời rạc gọi là Node.

Mỗi Node gồm 2 phần:

  • Data: Giá trị thực tế cần lưu trữ (số nguyên, struct, v.v.).
  • Next: Một biến con trỏ trỏ tới Node tiếp theo trong danh sách. Node cuối cùng sẽ trỏ tới NULL để báo hiệu kết thúc danh sách.

Sơ đồ trực quan:

Head -> [ Data | Next ] ---> [ Data | Next ] ---> [ Data | Next ] ---> NULL

Hãy cùng chạy chương trình tạo và in một danh sách liên kết đơn:

linked_list.c 
#include <stdio.h>
#include <stdlib.h>

// Define one node of the list
typedef struct Node {
    int data;
    struct Node *next; // Pointer to the next node
} Node;

// Allocate and initialise a new node
Node* createNode(int value) {
    Node *newNode = (Node*) malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

// Insert a new node at the head of the list
void insertAtHead(Node **head, int value) {
    Node *newNode = createNode(value);
    newNode->next = *head;
    *head = newNode;
}

// Print every node in the list
void printList(Node *head) {
    Node *temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    Node *head = NULL; // The list starts out empty

    insertAtHead(&head, 30);
    insertAtHead(&head, 20);
    insertAtHead(&head, 10);

    printf("Linked list: ");
    printList(head); // Output: 10 -> 20 -> 30 -> NULL

    // Free every node before leaving the program
    Node *temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }

    return 0;
}

📥 Tải về mã nguồn mẫu: linked_list.c

4. Ngăn xếp (Stack - LIFO)

Stack hoạt động theo cơ chế Last In, First Out (Vào sau, Ra trước). Giống như một chồng đĩa, chiếc đĩa đặt vào sau cùng sẽ là chiếc đĩa đầu tiên được lấy ra.

Hai thao tác cơ bản của Stack:

  • Push: Đẩy một phần tử vào đỉnh (top) của Stack.
  • Pop: Lấy phần tử nằm ở đỉnh Stack ra ngoài và trả về giá trị của nó.
stack.c 
#include <stdio.h>
#include <stdlib.h>

typedef struct StackNode {
    int data;
    struct StackNode *next;
} StackNode;

// Push an element onto the stack
void push(StackNode **top, int value) {
    StackNode *newNode = (StackNode*) malloc(sizeof(StackNode));
    newNode->data = value;
    newNode->next = *top;
    *top = newNode;
    printf("Pushed: %d\n", value);
}

// Pop an element off the stack
int pop(StackNode **top) {
    if (*top == NULL) {
        printf("Stack is empty!\n");
        return -1;
    }
    StackNode *temp = *top;
    int poppedValue = temp->data;
    *top = (*top)->next;
    free(temp);
    return poppedValue;
}

int main() {
    StackNode *top = NULL;

    push(&top, 100);
    push(&top, 200);
    push(&top, 300);

    printf("Popped: %d\n", pop(&top)); // 300 (last in, first out)
    printf("Popped: %d\n", pop(&top)); // 200

    // Free whatever is left on the stack
    while(top != NULL) {
        pop(&top);
    }

    return 0;
}

Điểm đáng chú ý: cả push lẫn pop đều chỉ đụng vào đầu danh sách, nên cả hai đều là O(1) bất kể ngăn xếp đang chứa bao nhiêu phần tử. Đó là lý do ngăn xếp được dùng ở những chỗ cần tốc độ ổn định — kể cả call stack mà CPU dùng để gọi hàm, như đã thấy ở Bài 5.

5. Hàng đợi (Queue - FIFO)

Queue hoạt động theo cơ chế First In, First Out (Vào trước, Ra trước). Giống như một hàng xếp hàng mua vé, người đến xếp hàng trước sẽ được phục vụ và ra ngoài trước.

Hai thao tác cơ bản của Queue:

  • Enqueue: Thêm phần tử vào cuối (rear) hàng đợi.
  • Dequeue: Lấy phần tử từ đầu (front) hàng đợi ra ngoài.
queue.c 
#include <stdio.h>
#include <stdlib.h>

typedef struct QNode {
    int data;
    struct QNode *next;
} QNode;

typedef struct {
    QNode *front;
    QNode *rear;
} Queue;

// Create an empty queue
Queue* createQueue() {
    Queue *q = (Queue*) malloc(sizeof(Queue));
    q->front = q->rear = NULL;
    return q;
}

// Add an element at the rear of the queue
void enqueue(Queue *q, int value) {
    QNode *temp = (QNode*) malloc(sizeof(QNode));
    temp->data = value;
    temp->next = NULL;

    if (q->rear == NULL) {
        q->front = q->rear = temp;
        printf("Enqueued: %d\n", value);
        return;
    }

    q->rear->next = temp;
    q->rear = temp;
    printf("Enqueued: %d\n", value);
}

// Remove the element at the front of the queue
int dequeue(Queue *q) {
    if (q->front == NULL) {
        printf("Queue is empty!\n");
        return -1;
    }

    QNode *temp = q->front;
    int val = temp->data;
    q->front = q->front->next;

    if (q->front == NULL) {
        q->rear = NULL;
    }

    free(temp);
    return val;
}

int main() {
    Queue *q = createQueue();

    enqueue(q, 10);
    enqueue(q, 20);
    enqueue(q, 30);

    printf("Dequeued: %d\n", dequeue(q)); // 10 (first in, first out)
    printf("Dequeued: %d\n", dequeue(q)); // 20

    // Free whatever is left in the queue
    while(q->front != NULL) {
        dequeue(q);
    }
    free(q);

    return 0;
}

Thử thách thiết kế thuật toán:

Hãy thử tự xây dựng cấu trúc của một danh sách liên kết đôi (Doubly Linked List), trong đó mỗi Node có thêm một con trỏ prev trỏ ngược lại Node phía trước để có thể duyệt danh sách theo cả hai chiều xuôi và ngược.

📝 Kiểm tra kiến thức bài 10
Sự khác biệt chính về cấu trúc giữa Danh sách liên kết đơn (Singly Linked List) và Danh sách liên kết đôi (Doubly Linked List) là gì?

Bài viết liên quan trong series

Bài 11: Lập trình đa tệp, Preprocessor & Công cụ Build trong C Bài 9: Cấp phát bộ nhớ động & Quản lý bộ nhớ trong C Quay lại Lộ trình C Series