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

Các cấu trúc dữ liệu (data structure) phổ biến bao gồm mảng (array), danh sách liên kết (linked list), ngăn xếp (stack), hàng đợi (queue), bảng băm (hash table), cây (tree), đống (heap) và đồ thị (graph). Chúng có thể được phân loại dựa trên hai phương diện: "cấu trúc logic (logical structure)" và "cấu trúc vật lý (physical structure)".

Cấu trúc logic: Tuyến tính và phi tuyến tính¶

Cấu trúc logic thể hiện mối quan hệ logic giữa các phần tử dữ liệu. Trong mảng và danh sách liên kết, dữ liệu được sắp xếp theo một thứ tự nhất định, thể hiện mối quan hệ tuyến tính giữa các phần tử; trong khi ở cây, dữ liệu được sắp xếp theo phân cấp từ trên xuống dưới, thể hiện mối quan hệ cha - con; đồ thị được cấu thành từ các nút (node) và cạnh (edge), phản ánh các mối quan hệ mạng phức tạp.

Như được minh họa trong hình bên dưới, các cấu trúc logic có thể được chia làm hai danh mục lớn: "tuyến tính" và "phi tuyến tính". Các cấu trúc tuyến tính trực quan hơn, biểu thị rằng dữ liệu được sắp xếp tuyến tính trong các mối quan hệ logic; các cấu trúc phi tuyến tính thì ngược lại, được sắp xếp phi tuyến tính.

Cấu trúc dữ liệu tuyến tính: Mảng, danh sách liên kết, ngăn xếp, hàng đợi, bảng băm, nơi các phần tử có mối quan hệ tuần tự một-đối-một (one-to-one).
Cấu trúc dữ liệu phi tuyến tính: Cây, đống, đồ thị, bảng băm.

Cấu trúc dữ liệu phi tuyến tính có thể được chia nhỏ hơn thành các cấu trúc dạng cây (tree structure) và cấu trúc dạng mạng (network structure).

Cấu trúc dạng cây: Cây, đống, bảng băm, nơi các phần tử có mối quan hệ một-nhiều (one-to-many).
Cấu trúc dạng mạng: Đồ thị, nơi các phần tử có mối quan hệ nhiều-nhiều (many-to-many).

Cấu trúc vật lý: Liên tục và phân tán¶

Khi một chương trình thuật toán chạy, dữ liệu được xử lý chủ yếu được lưu trữ trong bộ nhớ. Hình bên dưới minh họa một thanh bộ nhớ máy tính, trong đó mỗi ô vuông màu đen chứa một không gian bộ nhớ. Chúng ta có thể hình dung bộ nhớ như một bảng tính Excel khổng lồ, nơi mỗi ô có thể lưu trữ một lượng dữ liệu nhất định.

Hệ thống truy cập dữ liệu tại vị trí đích thông qua các địa chỉ bộ nhớ. Như được hiển thị trong hình dưới đây, máy tính gán một mã số cho mỗi ô trong bảng tính theo các quy tắc cụ thể, đảm bảo rằng mỗi không gian bộ nhớ đều có một địa chỉ bộ nhớ (memory address) duy nhất. Nhờ có các địa chỉ này, chương trình có thể truy cập dữ liệu trong bộ nhớ.

Tip

Cần lưu ý rằng việc so sánh bộ nhớ với một bảng tính Excel chỉ là một phép so sánh đơn giản hóa. Hoạt động thực tế của bộ nhớ phức tạp hơn nhiều, liên quan đến các khái niệm như không gian địa chỉ, quản lý bộ nhớ, cơ chế bộ đệm (cache), bộ nhớ ảo và bộ nhớ vật lý.

Bộ nhớ là tài nguyên dùng chung cho tất cả các chương trình. Khi một khối bộ nhớ bị một chương trình chiếm dụng, các chương trình khác thường không thể sử dụng nó cùng một lúc. Do đó, trong thiết kế cấu trúc dữ liệu và thuật toán, tài nguyên bộ nhớ là một yếu tố quan trọng cần cân nhắc. Ví dụ, bộ nhớ đỉnh (peak memory) bị thuật toán chiếm dụng không được vượt quá bộ nhớ trống còn lại của hệ thống; nếu thiếu các khối bộ nhớ lớn liên tục, thì cấu trúc dữ liệu được chọn phải có khả năng lưu trữ được trong các không gian bộ nhớ phân tán.

Như được minh họa trong hình dưới đây, cấu trúc vật lý phản ánh cách dữ liệu được lưu trữ trong bộ nhớ máy tính. Nó có thể được chia thành lưu trữ trong không gian liên tục (mảng) và lưu trữ trong không gian phân tán (danh sách liên kết). Ở cấp độ thấp, cấu trúc vật lý quyết định cách dữ liệu được truy cập, cập nhật, chèn và xóa. Hai cấu trúc vật lý này thể hiện các đặc tính bổ trợ lẫn nhau về mặt hiệu suất thời gian và hiệu quả không gian.

Một điều đáng chú ý là tất cả các cấu trúc dữ liệu đều được triển khai dựa trên mảng, danh sách liên kết hoặc sự kết hợp của cả hai. Ví dụ, ngăn xếp và hàng đợi có thể được triển khai bằng cả mảng hoặc danh sách liên kết; trong khi việc triển khai bảng băm có thể bao gồm cả mảng và danh sách liên kết.

Có thể được triển khai dựa trên mảng: Ngăn xếp, hàng đợi, bảng băm, cây, đống, đồ thị, ma trận, tensor (mảng có số chiều \(\geq 3\)), v.v.
Có thể được triển khai dựa trên danh sách liên kết: Ngăn xếp, hàng đợi, bảng băm, cây, đống, đồ thị, v.v.

Sau khi khởi tạo, danh sách liên kết vẫn có thể điều chỉnh độ dài của chúng trong quá trình thực thi chương trình, vì vậy chúng còn được gọi là "cấu trúc dữ liệu động (dynamic data structure)". Sau khi khởi tạo, độ dài của mảng không thể thay đổi, nên chúng còn được gọi là "cấu trúc dữ liệu tĩnh (static data structure)". Một điều đáng chú ý là mảng có thể thay đổi độ dài bằng cách phân bổ lại bộ nhớ, nhờ đó giữ lại một mức độ linh hoạt hạn chế.

Tip

Nếu bạn cảm thấy khó hiểu về cấu trúc vật lý, bạn nên đọc chương tiếp theo trước, rồi sau đó xem lại phần này.