#2. Tổng quan về cấu trúc dữ liệu - data structure

Cấu trúc dữ liệu được chia thành 2 loại chính:

• Linear data structure - Cấu trúc dữ liệu tuyến tính
• Non-linear data structure - Cấu trúc dữ liệu phi tuyến tính Nghe qua bằng tiếng Việt rất là kêu :U , nhưng chúng ta cứ hiểu qua loa rằng thằng linear thì nó lưu trữ data của chúng ta nối đuôi nhau, còn thằng nonlinear thì nó sẽ rẽ nhánh.

Linear data structure - cấu trúc tuyến tính

Với loại cấu trúc này, các phần tử sẽ được lưu trữ liên tiếp, nối đuôi nhau. Chính vì vậy mà cũng khá dễ hiểu và dễ sử dụng. Các loại cấu trúc dữ liệu điển hình thuộc loại này đó là:

1. Array - Mảng

Đây có lẽ là loại cấu trúc mà anh em được tiếp cận đầu tiên từ khi bắt đầu học lập trình và cũng là loại sơ khai nhất. Các phân tử dữ liệu được lưu trữ tại các ô nhớ liên tiếp nhau, và các phân tử cũng phải cùng loại dữ liệu.

2. Stack - Ngăn xếp

Trong cấu trúc này các phân tử sẽ được lữu trữ và tuân theo nguyên tắc LIFO - Last In First Out, tức là vào trước ra sau, vào sau ra trước. Trông nó giống như cái ống đựng cầu lông vậy:

3. Queue - Hàng đợi

Ngược lại với Stack, Queue sẽ cho phép data của chúng ta được lưu trữ và tuân theo quy tắc FIFO - First In First Out, tức là vào trước thì ra trước, chúng có vẻ công bằng hơn người anh em Stack của nó ) . Nó được đặt tên như vậy bởi nó hoạt động giống theo dòng người mua vé thôi:

4. Linked List - Danh sách liên kết

Người anh em của array, nhưng nó sẽ được lưu trữ bằng phương thức đặc biệt và phức tạp hơn - nó bao gồm các node, mỗi node sẽ có 2 phần là data và con trỏ(pointer) - nó sẽ trỏ tới cái node khác. Các bạn nên cố gắng hiểu bản chất của loại cấu trúc này bởi nó là dạng dễ nhất của cấu trúc động rồi.

Non-linear data structure - cấu trúc phi tuyến tính

Khác với cách lưu trữ của linear, nó sẽ tổ chức các dữ liệu theo dạng cấp bậc và không theo trình tự nhất định nào cả, mỗi phần tử sẽ liên kết với 1 hoặc nhiều phần tử khác. 2 cấu trúc điển hình là Tree và Graph.

1. Tree - Cây

Với tree, node cha và node con sẽ được nối với nhau bằng 1 cạnh (edge). Node cao nhất là gọi là root và cũng là node duy nhất không có node cha.

2. Graph - Đồ thị

Mỗi node của graph sẽ được gọi là đỉnh (vertex) và chúng sẽ được nối với nhau qua cạnh (edge)

Lưu ý rằng tree cũng là 1 dạng của graph nhưng có một đặc trưng để phân biệt giữa 2 cấu trúc này đó là: Tree sẽ không có bất kì node nào mà tồn tại con đường để đi rồi quay lại chính nó, nhưng với graph thì có và chúng được gọi là chu kì - cycle.

Bài viết này mô tả cấu trúc dữ liệu một cách phổ quát và ngắn gọn nhất, để hiểu hơn chúng ta sẽ phải đào sâu hơn với mỗi loại cấu trúc và các loại biến thể của chúng. Cảm ơn các bạn đã đọc!