Kỹ sư QLTT Ghi chú ôn thi
← Về danh sách
Điện toán & Nhúng
#자료구조#선형구조#비선형구조#트리#그래프#131회#125회
Cập nhật lần cuối · 2026-09-26

Cấu trúc dữ liệu: cấu trúc tuyến tính và cấu trúc phi tuyến

1. Tổng quan

A. Định nghĩa

Cấu trúc dữ liệu (Data Structure) là cách tổ chức logic để lưu trữ·quản lý·thao tác dữ liệu hiệu quả, được phân thành cấu trúc tuyến tính (Linear Structure) trong đó các phần tử nối tiếp nhau thành một hàng, và cấu trúc phi tuyến (Non-Linear Structure) trong đó các phần tử liên kết theo dạng phân cấp·mạng lưới, tùy theo hình thái liên kết giữa các phần tử.

Bản chất phân biệt hai cấu trúc là 'các phần tử được liên kết với nhau như thế nào'. Cấu trúc tuyến tính là liên kết 1:1, các phần tử xếp thành hàng và mỗi phần tử chỉ có đúng một láng giềng phía trước và phía sau. Trừ phần tử đầu và cuối, mọi phần tử đều có đúng một phần tử đứng trước và một phần tử đứng sau. Ngược lại, trong cấu trúc phi tuyến, một phần tử liên kết với nhiều phần tử (1:N hoặc N:M) tạo thành dạng phân cấp hoặc lưới. Đó là dạng một cha có nhiều con, hoặc một đỉnh nối với nhiều đỉnh bằng cạnh.

Sự khác biệt về hình thái liên kết này mang tính quyết định vì nó quy định có thể biểu diễn quan hệ nào và tìm kiếm·chèn·xóa hiệu quả đến đâu. Dữ liệu mà thứ tự quan trọng (hàng đợi, lịch sử gọi hàm, ngăn xếp hoàn tác) được biểu diễn tự nhiên bằng cấu trúc tuyến tính. Ngược lại, các quan hệ phức tạp trong đó một thứ đan xen với nhiều thứ như quan hệ trên dưới của sơ đồ tổ chức, quan hệ chuyển tuyến của tàu điện ngầm, quan hệ bạn bè trên mạng xã hội thì phải dùng cấu trúc phi tuyến mới biểu diễn được mà không bị bóp méo. Tức là việc chọn cấu trúc dữ liệu không đơn thuần là vấn đề tiện lưu trữ, mà là vấn đề mô hình hóa, chuyển cấu trúc quan hệ của miền bài toán thành mã.

Một điểm cần lưu ý là 'tuyến tính/phi tuyến' suy cho cùng là phân loại theo cấu trúc logic (trừu tượng). Về mặt vật lý, dù mảng — cấu trúc tuyến tính — được bố trí liên tục trong bộ nhớ, hay cây — cấu trúc phi tuyến — được bố trí rải rác bằng con trỏ, thì đó là vấn đề hiện thực (cấu trúc vật lý). Chẳng hạn, đống (Heap) về logic là cây nhị phân hoàn chỉnh (phi tuyến) nhưng về vật lý được hiện thực bằng mảng (tuyến tính). Như vậy, hiểu tách biệt cấu trúc logic và cấu trúc vật lý là điểm xuất phát của thiết kế cấu trúc dữ liệu.

B. Bối cảnh ra đời và sự cần thiết

Nếu chọn cấu trúc không phù hợp với đặc tính quan hệ dữ liệu của bài toán, hiệu năng sẽ giảm mạnh. Chẳng hạn, nếu gượng ép biểu diễn quan hệ phân cấp như sơ đồ tổ chức bằng mảng (tuyến tính), để tìm tổ chức cấp dưới của một nút cụ thể phải duyệt toàn bộ nên việc tìm kiếm tăng lên tới O(n). Ngược lại, nếu hiện thực lịch sử tác vụ chỉ cần xếp và lấy ra theo thứ tự bằng cây thì chỉ làm tăng độ phức tạp không cần thiết.

Việc chọn cấu trúc dữ liệu phù hợp chi phối trực tiếp độ phức tạp thời gian·không gian của thuật toán. Cùng là phép 'tìm kiếm' nhưng trên danh sách tuyến tính chưa sắp xếp là O(n), còn trên cây tìm kiếm nhị phân cân bằng là O(log n). Khi dữ liệu có 1 triệu bản ghi, O(n) cần tối đa 1 triệu lần so sánh, còn O(log n) xong trong khoảng 20 lần. Khoảng cách này thể hiện thành chênh lệch tốc độ phản hồi và thông lượng, nên từ góc nhìn Kỹ sư chuyên nghiệp (Professional Engineer), cấu trúc dữ liệu là công nghệ nền tảng không thể tách rời khỏi thiết kế thuật toán·hiệu năng.

2. Hệ thống phân loại tổng thể của cấu trúc dữ liệu

Trước tiên, nếu vẽ bản đồ tổng thể cấu trúc dữ liệu được chia thành những nhánh nào, vị trí của tuyến tính·phi tuyến sẽ trở nên rõ ràng.

flowchart TB
  DS["Cấu trúc dữ liệu (Data Structure)"] --> LN["Cấu trúc tuyến tính (Linear)"]
  DS --> NL["Cấu trúc phi tuyến (Non-Linear)"]
  LN --> ST["Ngăn xếp (Stack, LIFO)"]
  LN --> QU["Hàng đợi (Queue, FIFO)"]
  LN --> LI["Danh sách (List)"]
  LN --> DQ["Hàng đợi hai đầu (Deque)"]
  NL --> TR["Cây (Tree, 1:N)"]
  NL --> GR["Đồ thị (Graph, N:M)"]
  TR --> BST["Cây tìm kiếm nhị phân / B-Tree / Heap"]
  GR --> DG["Đồ thị có hướng·vô hướng / có trọng số"]
  style DS fill:#e8f0fe,stroke:#2f6fed,stroke-width:2px
  style LN fill:#eef6ff,stroke:#2f6fed
  style NL fill:#fef3f2,stroke:#e11d48

Như phân loại trên cho thấy, cấu trúc tuyến tính được chia nhỏ theo 'quy tắc nhập xuất', còn cấu trúc phi tuyến theo 'tô-pô liên kết (phân cấp hay mạng lưới)'. Từ chương tiếp theo, nguyên lý và ứng dụng thực tế của từng nhánh sẽ được giải thích thành văn.

3. Cấu trúc tuyến tính (Linear Structure)

Tính chất của cấu trúc tuyến tính thay đổi hoàn toàn tùy theo quy tắc đưa vào và lấy ra dữ liệu. Quy tắc chính là bản sắc của cấu trúc dữ liệu đó, và nhờ quy tắc này mà các phép toán rất nhanh O(1) được bảo đảm trong những tình huống cụ thể.

A. Ngăn xếp (Stack) — vào sau ra trước (LIFO)

Ngăn xếp là cấu trúc vào sau ra trước (Last-In-First-Out), lấy ra trước phần tử được đưa vào sau cùng. Giống như chồng đĩa rồi lấy dần từ trên xuống, cả chèn (push) và xóa (pop) chỉ xảy ra ở một chỗ là 'đỉnh (top)'. Nhờ ràng buộc này, cả hai phép toán đều được xử lý trong O(1).

Ngăn xếp mạnh mẽ vì nó hoàn toàn phù hợp với bài toán 'quay lại trạng thái gần nhất'. Ngăn xếp gọi hàm của chương trình là ví dụ tiêu biểu. Nếu hàm A gọi B và B gọi C, việc trả về phải diễn ra đúng theo thứ tự ngược (C→B→A), và đó chính là LIFO. Hoàn tác (Undo) của trình soạn thảo, nút 'quay lại' của trình duyệt web, kiểm tra cặp ngoặc của biểu thức, tính biểu thức hậu tố cũng đều được hiện thực bằng ngăn xếp. Ví dụ, với biểu thức có ngoặc lồng ba tầng, push ngoặc mở và pop ở ngoặc đóng thì có thể phán định các cặp có khớp hay không trong O(n) dựa vào việc ngăn xếp có rỗng hay không.

Điểm cần chú ý là quản lý kích thước ngăn xếp. Nếu lời gọi đệ quy quá sâu, ngăn xếp gọi hàm vượt giới hạn và xảy ra tràn ngăn xếp (stack overflow). Đó là lý do trong thực tế người ta đổi đệ quy thành vòng lặp + ngăn xếp tường minh hoặc xem xét tối ưu đệ quy đuôi.

B. Hàng đợi (Queue) — vào trước ra trước (FIFO)

Hàng đợi là cấu trúc vào trước ra trước (First-In-First-Out), lấy ra trước phần tử được đưa vào trước, giống như xếp hàng ở quầy vé. Chèn (enqueue) xảy ra ở phía sau (rear), xóa (dequeue) ở phía trước (front). Hàng đợi là nền tảng của mọi tình huống phải 'xử lý công bằng theo đúng thứ tự đến'.

Hàng chờ in của máy in, hàng chờ lập lịch tiến trình của hệ điều hành, bộ đệm gói tin mạng, hàng đợi thông điệp (Kafka·RabbitMQ) đều là hàng đợi. Tìm kiếm theo chiều rộng (BFS) của đồ thị cũng đưa các nút cần thăm vào hàng đợi và duyệt từ gần đến xa. Trong thực tế, dùng hàng đợi vòng (Circular Queue) tái sử dụng mảng theo vòng tròn để không lãng phí bộ nhớ khi phía trước trống, và trong bài toán nhà sản xuất-người tiêu dùng thì dùng hàng đợi có kích thước giới hạn để điều tiết lưu lượng (backpressure).

C. Danh sách (List) và hàng đợi hai đầu (Deque)

Danh sách là cấu trúc đa dụng chứa các phần tử theo thứ tự nhưng hỗ trợ truy cập·chèn·xóa ở vị trí bất kỳ. Tính chất khác nhau tùy cách hiện thực: danh sách dựa trên mảng (tuần tự) có thể truy cập ngay phần tử thứ i trong O(1) bằng chỉ số nhưng khi chèn·xóa ở giữa phải dịch chuyển phần tử nên mất O(n). Danh sách liên kết (Linked List) có mỗi nút trỏ tới địa chỉ nút kế tiếp, chèn·xóa ở giữa chỉ cần đổi con trỏ nên là O(1), nhưng muốn tìm phần tử thứ i phải lần từ đầu nên là O(n). Vì đánh đổi này mà nguyên tắc thực tiễn 'tra cứu nhiều thì dùng mảng, chèn·xóa nhiều thì dùng danh sách liên kết' được hình thành.

Hàng đợi hai đầu (Deque, Double-Ended Queue) là cấu trúc cho phép chèn·xóa ở cả hai đầu, bao hàm cả ngăn xếp và hàng đợi. Nó được dùng khi cần xử lý tự do cả hai đầu như tính giá trị lớn nhất trong cửa sổ trượt, quản lý cache mục dùng gần đây (LRU).

Bảng dưới đây tổng hợp cấu trúc tuyến tính theo quy tắc·độ phức tạp phép toán·tiêu chí ứng dụng. Bảng suy cho cùng là tài liệu bổ trợ nén lại phần giải thích văn xuôi phía trên.

Loại Quy tắc Độ phức tạp phép toán tiêu biểu Ứng dụng tiêu biểu
Ngăn xếp Vào sau ra trước (LIFO) push/pop O(1) Gọi hàm, hoàn tác, kiểm tra ngoặc, DFS
Hàng đợi Vào trước ra trước (FIFO) enqueue/dequeue O(1) Hàng chờ tác vụ, lập lịch, bộ đệm, BFS
Danh sách (mảng) Tuần tự theo chỉ số Truy cập O(1), chèn giữa O(n) Tập hợp chủ yếu tra cứu
Danh sách (liên kết) Liên kết con trỏ Truy cập O(n), chèn O(1) Tập hợp chèn·xóa thường xuyên
Hàng đợi hai đầu (Deque) Chèn·xóa ở hai đầu Hai đầu O(1) Cửa sổ trượt, LRU

4. Cấu trúc phi tuyến (Non-Linear Structure)

Đại diện của cấu trúc phi tuyến là cây và đồ thị. Cả hai cấu trúc đều 'một liên kết với nhiều', nhưng khác nhau ở chỗ cây là phân cấp không có chu trình (1:N) còn đồ thị là mạng lưới cho phép chu trình (N:M). Dưới đây là sơ đồ khái niệm chi tiết thể hiện khác biệt tô-pô giữa cây và đồ thị.

flowchart TB
  subgraph TREE["Cây (Tree) — phân cấp 1:N, không có chu trình"]
    R((Gốc)) --> C1((Con 1))
    R --> C2((Con 2))
    C1 --> G1((Cháu))
    C1 --> G2((Cháu))
  end
  subgraph GRAPH["Đồ thị (Graph) — mạng N:M, cho phép chu trình"]
    V1((A)) --- V2((B))
    V2 --- V3((C))
    V3 --- V1
    V2 --- V4((D))
  end

A. Cây (Tree)

Cây là cấu trúc phân cấp bắt đầu từ một gốc (root), trong đó cha có nhiều con, không có chu trình và đường đi giữa hai nút bất kỳ là duy nhất. Cây quan trọng vì sức mạnh 'vừa biểu diễn nguyên vẹn quan hệ phân cấp vừa kéo thời gian tìm kiếm xuống mức logarit'.

Cây tìm kiếm nhị phân (BST) được dùng rộng rãi nhất duy trì dữ liệu ở trạng thái sắp xếp theo quy tắc 'con trái < cha < con phải', thực hiện tìm kiếm·chèn·xóa trung bình O(log n). Tuy nhiên, nếu đầu vào đến theo thứ tự đã sắp xếp thì cây lệch về một phía và suy biến thành O(n); để ngăn điều này, các cây cân bằng như cây AVL·cây đỏ-đen tự động điều chỉnh chiều cao bằng phép quay. Cơ sở dữ liệu và hệ thống tệp dựa trên đĩa dùng B-Tree/B+Tree, trong đó một nút có hàng trăm con, làm chỉ mục để giảm thiểu số lần truy cập đĩa xuống bằng chiều cao cây (thường 3~4 tầng). Bí quyết tìm được bản ghi mong muốn chỉ với vài lần đọc khối ngay cả trên bảng hàng triệu dòng chính là cấu trúc này. Ngoài ra, đống (Heap) dùng để hiện thực hàng đợi ưu tiên lấy giá trị lớn nhất·nhỏ nhất trong O(1) và sắp xếp lại trong O(log n) theo quy tắc cha luôn lớn hơn (hoặc nhỏ hơn) con.

B. Đồ thị (Graph)

Đồ thị được định nghĩa bằng tập các đỉnh (Vertex) và tập các cạnh (Edge) nối chúng; nếu quan hệ có hướng thì là đồ thị có hướng, nếu cạnh gắn chi phí thì là đồ thị có trọng số. Đồ thị là công cụ tổng quát nhất để biểu diễn 'sự liên kết qua lại phức tạp giữa các thực thể bất kỳ'.

Tìm đường ngắn nhất của hệ thống dẫn đường là kết quả của việc coi giao lộ là đỉnh, đường là cạnh có trọng số rồi áp dụng thuật toán Dijkstra. Gợi ý kết bạn của mạng xã hội là bài toán tìm 'bạn của bạn' trong đồ thị người dùng, và xếp hạng trang (PageRank) của tìm kiếm web là tính mức độ quan trọng trên đồ thị liên kết. Đồ thị được hiện thực bằng ma trận kề (không gian O(V²) theo số đỉnh V) hoặc danh sách kề (không gian O(V+E) tỷ lệ với số cạnh); trong các mạng thực tế có cạnh thưa (sparse), danh sách kề hiệu quả hơn nhiều. Tìm kiếm cơ bản là theo chiều sâu (DFS, dùng ngăn xếp) và theo chiều rộng (BFS, dùng hàng đợi), đây là ví dụ hay cho thấy cấu trúc tuyến tính ở trên được dùng làm engine tìm kiếm cho cấu trúc phi tuyến.

Loại Hình thái liên kết Biến thể cốt lõi Ứng dụng
Cây (Tree) Phân cấp 1:N, không có chu trình BST, AVL, B-Tree, Heap Chỉ mục, hệ thống tệp, hàng đợi ưu tiên
Đồ thị (Graph) Mạng N:M, cho phép chu trình Đồ thị có hướng·có trọng số·hai phía Đường ngắn nhất, mạng xã hội, gợi ý, PageRank

5. So sánh tuyến tính vs phi tuyến — lý do tạo ra khác biệt

Khác biệt giữa hai cấu trúc không đến từ hình dạng bề ngoài mà từ 'tính chất của quan hệ cần biểu diễn'. Cấu trúc tuyến tính được tối ưu cho các quan hệ có thể xếp thành một hàng như thời gian·thứ tự, vì vậy việc tìm kiếm cũng chảy tuần tự từ trước ra sau. Cấu trúc phi tuyến ra đời để chứa các quan hệ phân cấp·mạng lưới không thể xếp thành một hàng, vì vậy cần các cách tìm kiếm lan theo nhiều nhánh như DFS·BFS. Tức là khác biệt về cách tìm kiếm là kết quả tất yếu phái sinh từ khác biệt về hình thái liên kết.

Hàm ý thực tiễn cũng xuất phát từ đây. Log·lịch sử·bộ đệm chỉ cần giữ thứ tự thì nên hiện thực tuyến tính để có được tính đơn giản khi hiện thực và phép toán O(1), còn các bài toán mà quan hệ nhiều-nhiều đan xen hoặc tìm kiếm phân cấp là cốt lõi (gợi ý·đường đi·tổ chức) phải thiết kế phi tuyến ngay từ đầu mới tránh được điểm nghẽn hiệu năng và chi phí thiết kế lại về sau.

Phân loại Cấu trúc tuyến tính Cấu trúc phi tuyến
Liên kết 1:1 (một hàng) 1:N, N:M (phân cấp·mạng)
Quan hệ biểu diễn Quan hệ thứ tự·thời gian Quan hệ phân cấp·mạng lưới
Tìm kiếm Tìm kiếm tuần tự DFS·BFS (tìm đường·phân cấp)
Ví dụ tiêu biểu Ngăn xếp·hàng đợi·danh sách·deque Cây·đồ thị
Tình huống phù hợp Dữ liệu có thứ tự, bộ đệm·lịch sử Dữ liệu quan hệ·phân cấp·đường đi phức tạp
Lưu ý khi hiện thực Tràn·tái sử dụng vòng Duy trì cân bằng·xử lý chu trình

6. Chuyên sâu — cấu trúc dữ liệu ứng dụng và chiến lược áp dụng thực tiễn

Hệ thống hiện đại thay vì dùng nguyên vẹn tuyến tính·phi tuyến thuần túy, thường dùng cấu trúc dữ liệu ứng dụng kết hợp hoặc chuyên biệt hóa cả hai. Hiểu điều này là độ sâu ở mức Kỹ sư chuyên nghiệp (Professional Engineer).

Thứ nhất, bảng băm (Hash Table) ánh xạ khóa thành chỉ số mảng bằng hàm băm để thực hiện tìm kiếm trung bình O(1), đồng thời kết hợp danh sách liên kết (chaining) để giải quyết xung đột. Đây là ví dụ kết hợp các cấu trúc tuyến tính (mảng + danh sách) để tạo ra tính chất mới là 'tra cứu gần như thời gian hằng số'. Nó là cốt lõi của cache quy mô lớn (Redis) và phép nối trong cơ sở dữ liệu.

Thứ hai, thiết kế chỉ mục cơ sở dữ liệu chính là lựa chọn cấu trúc dữ liệu. Nếu tìm kiếm phạm vi (BETWEEN) và sắp xếp diễn ra thường xuyên thì chọn chỉ mục B+Tree duy trì trạng thái sắp xếp, còn nếu chỉ cần tìm kiếm bằng thì chọn chỉ mục băm. Thực tế, trên bảng 1 triệu dòng, truy vấn không có chỉ mục là quét toàn bộ O(n), nhưng có chỉ mục B+Tree thì xong sau vài lần duyệt nút, thời gian phản hồi được cải thiện hàng chục lần là chuyện thường gặp.

Thứ ba, gần đây cơ sở dữ liệu đồ thị (Neo4j, v.v.) lưu trữ·truy vấn trực tiếp chính quan hệ đồ thị đã nổi lên. Nó xử lý trực tiếp bằng duyệt đồ thị 'bạn của bạn của bạn' vốn phải biểu diễn bằng nối nhiều tầng trong CSDL quan hệ, cho thấy lợi thế hiệu năng trong các miền mà duyệt quan hệ chiếm ưu thế như gợi ý·phát hiện gian lận·đồ thị tri thức. Điều này cho thấy việc chọn kho lưu trữ phù hợp với cấu trúc quan hệ của miền vẫn là nguyên lý căn bản.

7. Các điểm cần lưu ý và hàm ý

  1. Chọn cấu trúc phù hợp với đặc tính quan hệ của dữ liệu quyết định hiệu năng. Thứ tự·lịch sử thì tuyến tính, phân cấp·quan hệ thì phi tuyến là tự nhiên và hiệu quả. Lựa chọn sai không chỉ gây kém hiệu quả đơn thuần mà còn dẫn đến thiết kế lại toàn diện ở giai đoạn mở rộng, nên phải phân tích cấu trúc quan hệ của miền trước tiên ngay từ đầu thiết kế.

  2. Chọn cấu trúc dữ liệu gắn trực tiếp với độ phức tạp thuật toán (Big-O). Cùng một bài toán nhưng tùy dùng cấu trúc nào mà là O(n), O(log n), thậm chí O(1). Cấu trúc dữ liệu và thuật toán phải được thiết kế cùng nhau, và phải xác định trước 'trong tìm kiếm·chèn·xóa, phép nào là phép chiếm ưu thế' rồi chọn cấu trúc làm phép đó nhanh.

  3. Phải luôn cân nhắc đánh đổi thời gian-không gian. Bảng băm dùng bộ nhớ dư để tra cứu nhanh, ma trận kề có lợi cho đồ thị dày nhưng lãng phí không gian với đồ thị thưa. Trong môi trường nhúng·di động có ràng buộc bộ nhớ lớn thì hiệu quả không gian được ưu tiên, còn trên máy chủ dung lượng lớn thì hiệu quả thời gian có thể được ưu tiên.

  4. Phải phán đoán tách biệt cấu trúc logic và hiện thực vật lý. Giống như đống được hiện thực bằng mảng, đồ thị bằng danh sách kề, cùng một cấu trúc logic cũng có hiện thực tối ưu khác nhau tùy mẫu truy cập·tính cục bộ cache·đặc tính đĩa. Đặc biệt trên nền đĩa·SSD, tính cục bộ cache và số lần truy cập khối quan trọng không kém độ phức tạp lý thuyết.

  5. Thường xuyên xem xét mở rộng sang cấu trúc ứng dụng·chuyên biệt. Các giải pháp kết hợp·chuyên biệt hóa cấu trúc cơ bản như cây cân bằng·bảng băm·CSDL đồ thị liên tục phát triển, nên khi quy mô bài toán và mẫu truy cập thay đổi thì lựa chọn cấu trúc dữ liệu cũng phải được đánh giá lại.

Tóm tắt một câu: Cấu trúc tuyến tính (ngăn xếp·hàng đợi·danh sách·deque) liên kết phần tử 1:1 thành một hàng để xử lý quan hệ thứ tự bằng phép toán O(1), cấu trúc phi tuyến (cây·đồ thị) liên kết theo phân cấp·mạng 1:N·N:M để hỗ trợ quan hệ phức tạp và tìm kiếm thời gian logarit, và việc chọn cấu trúc phù hợp với đặc tính quan hệ của dữ liệu quyết định hiệu quả tìm kiếm và độ phức tạp thuật toán.