🗂️ Phân loại cấu trúc dữ liệu

Tuyến tính vs phi tuyến tính

Bạn có thể chia gần như mọi cấu trúc dữ liệu thành hai nhóm lớn dựa trên cách các phần tử liên hệ với nhau.

Cấu trúc tuyến tính (linear) sắp xếp phần tử theo một hàng, mỗi phần tử chỉ có tối đa một phần tử “trước” và một phần tử “sau”:

Array - các phần tử nằm liền kề nhau.
Linked List - các phần tử nối nhau qua con trỏ.
Stack, Queue - cũng là dạng tuyến tính, chỉ khác ở quy tắc thêm/xóa (LIFO, FIFO).

Cấu trúc phi tuyến tính (non-linear) thì một phần tử có thể liên hệ với nhiều phần tử khác cùng lúc:

Tree - một node cha có thể có nhiều node con.
Graph - các đỉnh có thể nối với bất kỳ đỉnh nào khác.
Hash Table, Heap - tổ chức phần tử theo key hoặc theo thứ tự ưu tiên, không theo một “hàng” cố định.

Góc nhìn vật lý: liên tục vs phân tán

Ngoài cách tổ chức logic ở trên, còn một cách phân loại khác dựa trên việc dữ liệu được lưu ở đâu trong bộ nhớ máy tính.

Lưu liên tục (contiguous): các phần tử nằm sát nhau trong một vùng nhớ duy nhất, giống như array. Máy tính chỉ cần biết địa chỉ phần tử đầu tiên và kích thước mỗi phần tử là tính được địa chỉ của bất kỳ phần tử nào - đây là lý do arr[i] truy cập được trong O(1).

Lưu phân tán (linked): mỗi phần tử là một “node” riêng lẻ nằm ở một vùng nhớ bất kỳ, và các node giữ địa chỉ (con trỏ) trỏ đến nhau, giống như linked list. Muốn tìm phần tử thứ i, bạn buộc phải đi từ đầu, lần theo từng con trỏ - đây là lý do truy cập ngẫu nhiên trên linked list là O(n).

Đổi lại, cấu trúc phân tán linh hoạt hơn khi thêm/xóa: bạn chỉ cần đổi vài con trỏ, không cần dịch chuyển hàng loạt phần tử như array.

	Contiguous (Array)	Linked (Linked List)
Truy cập theo index	O(1)	O(n)
Thêm/xóa ở giữa	O(n) (phải dịch phần tử)	O(1) (chỉ đổi con trỏ, nếu đã có vị trí)
Tận dụng cache CPU	Tốt	Kém

Rất nhiều cấu trúc dữ liệu “cấp cao” hơn thực chất được xây từ hai khối cơ bản này - ví dụ hash table dùng array làm nền, còn tree và graph thường dùng node kiểu linked list.

Kiểu dữ liệu cơ bản

Trước khi ghép các phần tử lại thành cấu trúc dữ liệu, bản thân mỗi phần tử phải là một kiểu dữ liệu cơ bản (primitive type) nào đó - số nguyên, số thực, ký tự, boolean… Kích thước cố định của các kiểu này là lý do array tính được địa chỉ phần tử nhanh như vậy.

Java
Kotlin

byte b;      // 1 byte  (8 bit)
short s;     // 2 byte
int i;       // 4 byte
long l;      // 8 byte
float f;     // 4 byte
double d;    // 8 byte
char c;      // 2 byte (UTF-16)
boolean bo;  // 1 byte (thường)

val b: Byte    // 1 byte
val s: Short   // 2 byte
val i: Int     // 4 byte
val l: Long    // 8 byte
val f: Float   // 4 byte
val d: Double  // 8 byte
val c: Char    // 2 byte (UTF-16)
val bo: Boolean // 1 byte (thường)

Python, Dart hay Swift che giấu phần lớn chi tiết này (một int trong Python có thể mở rộng kích thước tùy giá trị), nhưng bên dưới, trình thông dịch/biên dịch vẫn phải quy các giá trị đó về dạng nhị phân có kích thước xác định để CPU xử lý được.

Số và ký tự dưới dạng nhị phân

Máy tính chỉ hiểu 0 và 1, nên mọi kiểu dữ liệu cuối cùng đều quy về chuỗi bit:

Số nguyên được lưu ở dạng nhị phân trực tiếp; số âm thường dùng kỹ thuật “bù hai” (two’s complement) để phép cộng/trừ nhị phân hoạt động đúng mà không cần mạch xử lý riêng cho dấu.
Số thực được lưu theo chuẩn dấu phẩy động (floating point, ví dụ IEEE 754), tách thành phần dấu, phần mũ và phần định trị - đây cũng là lý do phép so sánh số thực đôi khi có sai số nhỏ ngoài dự đoán.
Ký tự được ánh xạ sang số qua một bảng mã: ASCII cho các ký tự tiếng Anh cơ bản (0-127), còn Unicode (thường mã hóa bằng UTF-8 hoặc UTF-16) bao phủ gần như mọi ký tự trên thế giới, kể cả tiếng Việt có dấu và emoji.

Bạn không cần nhớ chi tiết các chuẩn này để dùng cấu trúc dữ liệu hằng ngày, nhưng hiểu sơ qua giúp lý giải được những hiện tượng như “vì sao 0.1 + 0.2 != 0.3” hay “vì sao chuỗi tiếng Việt đôi khi bị lỗi font khi đọc sai encoding”.