This C programming guide is currently only available in Vietnamese. Please toggle the language switch (🇻🇳) in the top navigation to read the full article.

In this seventh part of the series, we combine structures and dynamic pointers to implement classic software data structures: Singly Linked Lists, Stacks (LIFO), and Queues (FIFO) from scratch in C.

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 
// Truy cập trực tiếp ô nhớ qua index trong mảng là O(1)
int getElement(int arr[], int index) {
    return arr[index];
}

// Vòng lặp chạy cố định 100 lần không đổi theo N vẫn là O(1)
void printHeader() {
    for (int i = 0; i < 100; i++) {
        printf("-");
    }
}

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 
// Thuật toán tìm kiếm nhị phân (Binary Search) trên mảng đã sắp xếp
int binarySearch(int arr[], int size, int target) {
    int left = 0, right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // Tránh tràn số nguyên
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1; // Loại bỏ nửa trái
        else right = mid - 1; // Loại bỏ nửa phải
    }
    return -1;
}

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 
// Duyệt toàn bộ mảng tìm kiếm tuần tự
int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) return i; // Tệ nhất chạy qua N phần tử
    }
    return -1;
}

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$.

> [!IMPORTANT] > 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 
// In toàn bộ cặp phần tử trong mảng
void printAllPairs(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        for (int j = i + 1; j < size; j++) { // Chạy giảm dần theo i
            printf("(%d, %d)\n", arr[i], arr[j]); // Vẫn là O(N^2)
        }
    }
}

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$. 
    // Đệ quy Fibonacci thô sơ (Không lưu bộ đệm) tốn O(2^N)
int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2); // Mỗi node cha sinh ra 2 nhánh con
}
  • $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 
// CÁCH 1: ĐỆ QUY (Tính tổng từ 1 đến N)
// Đệ quy sâu N lần, Call Stack phải chứa N Stack Frames cùng lúc
// => Time: O(N) | Space: O(N) (Dễ gây Stack Overflow khi N lớn)
int sumRecursive(int n) {
    if (n <= 1) return n;
    return n + sumRecursive(n - 1);
}

// CÁCH 2: VÒNG LẶP (Tính tổng từ 1 đến N)
// Chỉ sử dụng 1 biến sum cố định trên duy nhất 1 Stack Frame của hàm sumIterative
// => Time: O(N) | Space: O(1) (Cực kỳ an toàn, tối ưu bộ nhớ RAM)
int sumIterative(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}

> [!TIP] > 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>

// Dinh nghia mot Node
typedef struct Node {
    int data;
    struct Node *next; // Con tro tro toi node ke tiep
} Node;

// Ham tao node moi
Node* createNode(int value) {
    Node *newNode = (Node*) malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

// Ham chen node moi vao dau danh sach
void insertAtHead(Node **head, int value) {
    Node *newNode = createNode(value);
    newNode->next = *head;
    *head = newNode;
}

// Ham in toan bo danh sach
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; // Danh sach ban dau trong

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

    printf("Danh sach lien ket: ");
    printList(head); // Output: 10 -> 20 -> 30 -> NULL

    // Giai phong toan bo cac node truoc khi thoat
    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;

// Ham day phan tu vao 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);
}

// Ham rut phan tu khoi Stack
int pop(StackNode **top) {
    if (*top == NULL) {
        printf("Stack rong!\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 (Phan tu vao sau cung ra dau tien)
    printf("Popped: %d\n", pop(&top)); // 200

    // Giai phong stack con lai
    while(top != NULL) {
        pop(&top);
    }

    return 0;
}

4. 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;

// Khoi tao queue rong
Queue* createQueue() {
    Queue *q = (Queue*) malloc(sizeof(Queue));
    q->front = q->rear = NULL;
    return q;
}

// Them phan tu vao cuoi 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);
}

// Xoa phan tu khoi dau queue
int dequeue(Queue *q) {
    if (q->front == NULL) {
        printf("Queue rong!\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 (Vao truoc ra truoc)
    printf("Dequeued: %d\n", dequeue(q)); // 20

    // Giai phong queue con lai
    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 7
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ì?

Related Articles

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

Lesson 11: Multi-file Programming, Preprocessor & Build Tools in C Bài 11: Lập trình đa tệp, Preprocessor & Công cụ Build trong C Lesson 9: Dynamic Memory Allocation and Memory Management in C Bài 9: Cấp phát bộ nhớ động & Quản lý bộ nhớ trong C Back to C Series Overview Quay lại Lộ trình C Series