Mảng & danh sách liên kết

Bài trước, ta học cách đo chi phí bằng Độ phức tạp (Big-O). Giờ ta gặp cấu trúc dữ liệu đầu tiên - và sẽ thấy ngay vì sao cùng một việc lại có chi phí khác nhau tuỳ cách dữ liệu được xếp trong bộ nhớ.

Cần lưu một dãy phần tử (một hàng mèo con), có hai cách xếp. Cách 1 - dãy ghế liền nhau, đánh số: mèo con ngồi vào ghế 0, 1, 2… Biết số ghế là tới thẳng, nhưng chen một bạn vào giữa thì cả hàng phải xích ra. Cách 2 - mỗi mèo nắm tay bạn kế tiếp: không cần ghế cố định, ai cũng chỉ nhớ “bạn sau mình là ai”. Đó chính là mảng và danh sách liên kết.

• ▸Mảng (array): các phần tử nằm trong ô nhớ LIỀN KỀ, đánh chỉ số 0, 1, 2…
• ▸Danh sách liên kết (linked list): mỗi phần tử là một node, GIỮ con trỏ tới node kế.
• ▸Cùng lưu một dãy, nhưng chi phí mỗi thao tác lại khác nhau - đó là bài học chính.

Trong mảng, các phần tử nằm khít nhau trong bộ nhớ. Vì biết ô nhớ gốc và mỗi phần tử to bằng nhau, máy tính tính ngay địa chỉ phần tử thứ i: địa chỉ = gốc + i × kích thước. Không cần dò - nhảy thẳng tới nơi. Đó là lý do truy cập theo chỉ số là O(1). (Muốn nhìn ô nhớ và địa chỉ vận hành ở mức phần cứng, ghé bài Bộ nhớ & RAM ở khoá Máy tính hoạt động thế nào.)

Cái giá nằm ở chỗ khác: muốn chèn vào đầu, mọi phần tử cũ phải dịch sang phải một ô để chừa chỗ - tốn O(n).

const a = [10, 20, 30, 40, 50];

console.log(a[3]);  // truy cap theo chi so: nhay thang, O(1)

a.unshift(5);       // chen vao dau: doi ca day sang phai, O(n)
console.log(a);

40
[ 5, 10, 20, 30, 40, 50 ]

• ▸Truy cập a[i] theo chỉ số: O(1) - tính địa chỉ rồi nhảy thẳng.
• ▸Chèn / xoá ở đầu (hay giữa): O(n) - phải dời các phần tử khác.
• ▸Mảng hợp khi bạn đọc theo vị trí nhiều, ít chèn/xoá ở đầu.

Một node gồm hai phần: value (giá trị) và next (con trỏ tới node kế, hoặc null nếu là node cuối). Ta chỉ nắm head - con trỏ tới node đầu; muốn đi đâu thì lần theo next.

Nhờ vậy chèn vào đầu cực rẻ: tạo một node mới trỏ vào head cũ là xong, O(1), không ai phải dịch chỗ. Nhưng truy cập phần tử thứ i lại phải đi từ head qua từng node - O(n), vì không có chỉ số để nhảy thẳng:

type Node = { value: number; next: Node | null };

// Chen vao dau: O(1) - chi tao 1 node tro vao head cu
function prepend(head: Node | null, value: number): Node {
  return { value, next: head };
}

// Truy cap phan tu thu i: phai di qua i+1 node - O(n)
function getAt(head: Node | null, i: number): { value: number | null; hops: number } {
  let hops = 0;
  for (let node = head; node; node = node.next) {
    hops++;
    if (hops === i + 1) return { value: node.value, hops };
  }
  return { value: null, hops };
}

let ds: Node | null = null;
for (const v of [30, 20, 10]) ds = prepend(ds, v); // chen dau -> [10, 20, 30]

console.log(getAt(ds, 0)); // phan tu dau
console.log(getAt(ds, 2)); // phan tu cuoi: phai di het

{ value: 10, hops: 1 }
{ value: 30, hops: 3 }

Phần tử đầu lấy được sau 1 bước; phần tử cuối phải đi hết 3 node (hops: 3). Danh sách càng dài, lấy phần tử cuối càng lâu - đúng tinh thần O(n).

• ▸Node = value + con trỏ next; head trỏ tới node đầu, node cuối trỏ null.
• ▸Chèn / xoá ở đầu: O(1) - chỉ đổi vài con trỏ.
• ▸Truy cập phần tử thứ i: O(n) - phải đi lần lượt từ head.

Chọn một thao tác và kéo kích thước n để xem mỗi cấu trúc tốn bao nhiêu bước. Ô tô màu cho thấy thao tác phải “đụng” tới đâu - chính là nơi sinh ra chi phí:

• ▸Truy cập theo chỉ số: Mảng O(1) · Danh sách O(n).
• ▸Chèn / xoá ở đầu: Mảng O(n) · Danh sách O(1) - ngược hẳn lại.
• ▸Tìm một giá trị (chưa sắp): cả hai O(n), hoà.
• ▸Không có cấu trúc “tốt nhất” - chỉ có cái HỢP với thao tác bạn làm nhiều.

Cùng một Big-O chưa chắc cùng tốc độ thật. Hai điều khiến mảng thường thắng trong thực tế dù trên giấy ngang nhau:

• ▸Tốn bộ nhớ phụ: mỗi node danh sách phải mang thêm một con trỏ next (8 byte trên máy 64-bit); mảng thì không.
• ▸Thân thiện cache: mảng nằm liền kề nên CPU nạp một “mẻ” là có sẵn nhiều phần tử; node danh sách rải rác khắp bộ nhớ, đọc tới đâu nhảy tới đó.
• ▸Vì vậy duyệt tuần tự một mảng thường nhanh hơn duyệt danh sách, dù cùng O(n).

Mèo con vừa có hai “viên gạch” nền: mảng (truy cập theo chỉ số nhanh) và danh sách liên kết (thêm/bớt ở đầu nhanh). Mọi cấu trúc phức tạp hơn đều xây từ hai viên gạch này, cộng với cái la bàn Big-O của bài trước để cân đo.