Bỏ qua điều hướng, tới nội dung chính
Học C
Bài 21.124 phút đọc

Node và bố cục bộ nhớ

Sau bài này bạn sẽ làm được

  • Khai báo kiểu Node tự tham chiếu bằng tên thẻ
  • Vẽ được sơ đồ ô nhớ của một danh sách ba nút
  • So sánh mảng và danh sách trên tám tiêu chí
  • Biết vì sao mảng động thường nhanh hơn dù lý thuyết xấu hơn

Mảng buộc mọi phần tử nằm cạnh nhau. Ràng buộc đó cho bạn truy cập O(1) nhưng lấy đi khả năng chèn và xóa rẻ. Danh sách liên kết đổi ngược lại: mỗi phần tử tự do nằm ở đâu tùy thích, và một con trỏ nối chúng lại thành hàng.

#Ý tưởng: bỏ ràng buộc liên tiếp

Bài 9.1 nói mảng là một khối byte liền mạch. Chính vì liền mạch nên a[i] tính được bằng một phép nhân và một phép cộng. Nhưng cũng chính vì liền mạch nên chèn một phần tử vào giữa phải dịch tất cả những phần tử phía sau.

Danh sách liên kết bỏ hẳn ràng buộc đó. Mỗi phần tử được cấp phát riêng, ở bất cứ đâu trong vùng cấp phát động, và mang theo địa chỉ của phần tử kế tiếp. Muốn chèn vào giữa thì chỉ cần sửa hai con trỏ, không ai phải dịch chuyển.

MảngDanh sách liên kết
Vị trí phần tửDo trình biên dịch quyết định, liên tiếpDo bộ cấp phát quyết định, rời rạc
Cách tìm phần tử kế tiếpCộng thêm sizeof phần tửĐọc trường next
Cái phải trả để chènDịch toàn bộ phần đuôiSửa hai con trỏ
Cái phải trả để truy cậpKhông, một phép tính địa chỉĐi lần lượt qua từng nút

#Khai báo nút tự tham chiếu

node.h
typedef struct Node {
    int          data;
    struct Node *next;      /* PHẢI dùng tên thẻ, không dùng được tên typedef */
} Node;

Kích thước thật của một nút

kich-thuoc.c
#include <stddef.h>
#include <stdio.h>

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

int main(void)
{
    printf("sizeof(int)    = %zu\n", sizeof(int));
    printf("sizeof(Node *) = %zu\n", sizeof(Node *));
    printf("sizeof(Node)   = %zu\n", sizeof(Node));
    printf("offset data    = %zu\n", offsetof(Node, data));
    printf("offset next    = %zu\n", offsetof(Node, next));

    return 0;
}
terminal
./kich-thuoc
sizeof(int)    = 4
sizeof(Node *) = 8
sizeof(Node)   = 16
offset data    = 0
offset next    = 8

Bốn byte dữ liệu, tám byte con trỏ, và bốn byte đệm nằm giữa để next rơi vào bội số của 8. Đúng theo quy tắc căn chỉnh ở Bài 15.1. Nghĩa là để lưu một số int, bạn tốn 16 byte cộng thêm phần đầu khối mà bộ cấp phát giữ riêng.

#Một nút nằm ở đâu trong bộ nhớ

Ba nút được cấp phát riêng lẻ. Địa chỉ của chúng không theo thứ tự nào, chỉ có con trỏ next tạo ra thứ tự.
dia-chi.c
#include <stdio.h>
#include <stdlib.h>

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

int main(void)
{
    Node *a = malloc(sizeof *a);
    Node *b = malloc(sizeof *b);
    Node *c = malloc(sizeof *c);

    if (a == NULL || b == NULL || c == NULL) { free(a); free(b); free(c); return 1; }

    a->data = 10;  a->next = b;
    b->data = 20;  b->next = c;
    c->data = 30;  c->next = NULL;

    for (Node *p = a; p != NULL; p = p->next)
        printf("%p  data = %2d  next = %p\n",
               (void *)p, p->data, (void *)p->next);

    free(a); free(b); free(c);

    return 0;
}
terminal
./dia-chi
0x5591a2b6b2a0  data = 10  next = 0x5591a2b6b2c0
0x5591a2b6b2c0  data = 20  next = 0x5591a2b6b2e0
0x5591a2b6b2e0  data = 30  next = (nil)
# Ba khối cấp liên tiếp nhau nên địa chỉ cách đều 32 byte, nhưng đó chỉ là may mắn
./dia-chi-xen-ke
0x55e9f0a4a2a0  data = 10  next = 0x55e9f0a4a300
0x55e9f0a4a300  data = 20  next = 0x55e9f0a4a2e0
0x55e9f0a4a2e0  data = 30  next = (nil)

Lượt chạy thứ hai xen kẽ vài lần cấp phát khác vào giữa. Địa chỉ liền nhảy lung tung, và nút thứ ba còn nằm trước nút thứ hai trong bộ nhớ. Danh sách vẫn đúng, vì thứ tự logic hoàn toàn nằm ở con trỏ, không nằm ở địa chỉ.

#So sánh với mảng

Tiêu chíMảngDanh sách liên kết
Bố trí bộ nhớLiên tiếpRời rạc
Truy cập phần tử thứ iO(1)O(n)
Chèn hoặc xóa ở đầuO(n)O(1)
Chèn hoặc xóa ở cuốiO(1) nếu còn chỗO(1) nếu giữ tail
Chèn khi đã có con trỏ tới chỗ đóO(n) vì phải dịchO(1)
Bộ nhớ phụ mỗi phần tử08 byte con trỏ cộng đệm
Thân thiện bộ nhớ đệmRất tốtKém
Đổi kích thướcPhải realloc cả khốiKhông cần gì

#Vì sao mảng thường thắng trong thực tế

Dòng bộ nhớ đệm
Bộ xử lý không đọc từng byte từ RAM. Nó đọc cả một dòng, thường 64 byte, vào bộ nhớ đệm. Đọc byte kế tiếp trong cùng dòng gần như miễn phí, còn đọc một byte ở dòng khác thì tốn hàng trăm chu kỳ nếu dòng đó chưa có sẵn.

Duyệt một mảng int là đọc 16 số cho mỗi dòng 64 byte. Duyệt một danh sách là mỗi nút một lần nhảy tới địa chỉ chẳng liên quan gì tới nút trước, nên gần như mỗi nút một lần trượt bộ nhớ đệm. Chênh lệch thực tế thường là một bậc độ lớn, dù cả hai đều là O(n).

do-tong.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

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

#define N 5000000

int main(void)
{
    /* Mảng */
    int *a = malloc(N * sizeof *a);

    if (a == NULL) return 1;

    for (size_t i = 0; i < N; ++i) a[i] = (int)i;

    clock_t t0 = clock();
    long long tong_a = 0;

    for (size_t i = 0; i < N; ++i) tong_a += a[i];

    double giay_a = (double)(clock() - t0) / CLOCKS_PER_SEC;

    /* Danh sách, cấp phát theo đúng thứ tự nên đã là trường hợp thuận lợi */
    Node *dau = NULL, *cuoi = NULL;

    for (size_t i = 0; i < N; ++i) {
        Node *n = malloc(sizeof *n);

        if (n == NULL) return 1;

        n->data = (int)i;
        n->next = NULL;

        if (cuoi) cuoi->next = n; else dau = n;

        cuoi = n;
    }

    t0 = clock();
    long long tong_l = 0;

    for (Node *p = dau; p; p = p->next) tong_l += p->data;

    double giay_l = (double)(clock() - t0) / CLOCKS_PER_SEC;

    printf("mang      : %.3f s  (tong %lld)\n", giay_a, tong_a);
    printf("danh sach : %.3f s  (tong %lld)\n", giay_l, tong_l);
    printf("cham hon  : %.1f lan\n", giay_l / giay_a);

    free(a);

    for (Node *p = dau; p; ) { Node *t = p->next; free(p); p = t; }

    return 0;
}
terminal
gcc -std=c17 -O2 do-tong.c -o do-tong && ./do-tong
mang      : 0.004 s  (tong 12499997500000)
danh sach : 0.031 s  (tong 12499997500000)
cham hon  : 7.8 lan

Tự làm thử

  1. Khai báo Node rồi in sizeof và offsetof của từng trường. Đổi int thành char và giải thích vì sao sizeof(Node) không đổi.
  2. Dựng bằng tay một danh sách bốn nút, in địa chỉ từng nút, rồi xen kẽ vài lần malloc khác vào giữa và xem địa chỉ thay đổi thế nào.
  3. Chạy phép đo do-tong.c trên máy bạn với -O0 và -O2. Giải thích vì sao tỷ lệ chênh lệch khác nhau.
  4. Sửa phép đo để các nút được cấp phát theo thứ tự ngẫu nhiên, rồi đo lại. Ghi lại tỷ lệ mới.
  5. Với một bài toán bạn từng viết, hãy trả lời: nếu đổi từ mảng sang danh sách thì thao tác nào nhanh lên, thao tác nào chậm đi.

Trình chấm điểm tự động sẽ được bổ sung ở giai đoạn sau. Hiện tại bạn tự chạy thử trên máy.

Tóm tắt

  • Nút danh sách bắt buộc dùng tên thẻ struct Node *next, vì tên typedef chưa tồn tại bên trong thân struct.
  • Một nút chứa 4 byte dữ liệu thật ra chiếm 32 byte, tính cả đệm căn chỉnh và phần đầu khối của bộ cấp phát.
  • Thứ tự trong danh sách nằm hoàn toàn ở con trỏ next, không liên quan gì tới thứ tự địa chỉ.
  • Danh sách thắng ở chèn và xóa khi đã có con trỏ. Mảng thắng ở truy cập theo chỉ số và ở tốc độ duyệt.
  • Trong thực tế mảng động thường nhanh hơn nhiều lần nhờ bộ nhớ đệm. Chỉ chọn danh sách khi có lý do đo được.