Cấu trúc dữ liệu Tuyến tính (Linear Data Structures)
Các phần tử dữ liệu sắp xếp tuần tự, mỗi phần tử kết nối với phần tử trước và sau. Kết nối này giúp duyệt qua cấu trúc tuyến tính trong một cấp độ và một lần chạy. Dễ cài đặt vì bộ nhớ máy tính cũng tuần tự. Ví dụ: Danh sách (List), Hàng đợi (Queue), Ngăn xếp (Stack), Mảng (Array).
Cấu trúc dữ liệu Phi tuyến tính (Non-linear Data Structures)
Không có trình tự kết cố định nối tất cả phần tử, mỗi phần tử có thể có nhiều đường dẫn nối với các phần tử khác. Hỗ trợ lưu trữ đa cấp, thường không duyệt hết trong một lần. Khó cài đặt hơn nhưng hiệu quả hơn trong việc sử dụng bộ nhớ. Ví dụ: Cây (Tree), BST, Đồ thị (Graphs).
Các khác biệt quan trọng:
| STT | Tiêu chí | Tuyến tính | Phi tuyến tính |
|---|---|---|---|
| 1 | Sắp xếp phần tử | Kết nối tuần tự, duyệt được trong một lần chạy. | Kết nối phân cấp, hiện diện ở nhiều cấp độ. |
| 2 | Cấp độ | Tất cả phần tử ở một cấp độ. | Phần tử ở nhiều cấp độ. |
| 3 | Độ phức tạp cài đặt | Dễ cài đặt hơn. | Khó hiểu và cài đặt hơn so với tuyến tính. |
| 4 | Duyệt (Traversal) | Duyệt hoàn toàn trong một lần chạy. | Khó duyệt, cần nhiều lần chạy để duyệt hết. |
| 5 | Sử dụng bộ nhớ | Không thân thiện bộ nhớ, không hiệu quả. | Sử dụng bộ nhớ rất hiệu quả. |
| 6 | Độ phức tạp thời gian | Thường tăng khi kích thước tăng. | Thường không đổi khi kích thước tăng. |
| 7 | Ví dụ | Array, List, Queue, Stack. | Graph, Map, Tree. |