Danh sách liên kết là một trong những cấu trúc phổ biến và thường được sử dụng để quản lý dữ liệu trong chương trình. Bài viết này giới thiệu một số cấu trúc dữ liệu phổ biến: linked list (danh sách liên kết), stack và queue.
Data Structure & Algorithm Hiếu Nguyễn 2014-06-02 22:05:29

Giới thiệu

Danh sách liên kết là một trong những cấu trúc phổ biến và thường được sử dụng để quản lý dữ liệu trong chương trình. Bài viết này sẽ giúp các bạn phần nào hiểu về nó cũng như mang đến các khái niệm và ứng dụng của danh sách liên kết trong lập trình và thật tế để chúng ta dễ nhớ.

Tiền đề bài viết

Sau quá trình làm việc, tôi nhận thấy các bạn thường bị hiểu một cách cứng nhắc về các định nghĩa của cấu trúc dữ liệu từ trong sách vở. Do đó, bài viết này ra đời nhằm đem lại một cách nhìn trực quan hơn để chúng ta có thể hiểu và áp dụng kiến thức này trong các bài toán thực tế.

Đối tượng hướng đến

Bài viết dành cho các lập trình viên có kiến thức lập trình căn bản, từng làm việc với cấu trúc dữ liệu mảng, đang muốn có những ví dụ thực tế về những lý thuyết khô khan về cấu trúc dữ liệu.

Danh sách liên kết

Trong quá trình lập trình, đôi lúc chúng ta cần có một cấu trúc dữ liệu linh hoạt (không bị cố định kích thước như mảng), và danh sách liên kết là thứ có thể đáp ứng được yêu cầu đó của bạn.

Gần giống với mảng, danh sách liên kết là một chuỗi các phần tử chứa dữ liệu trong nó, nhưng khác với mảng, mỗi phần tử trong danh sách (còn được gọi là node) chứa trong nó dữ liệu cần lưu và cả dữ liệu để liên kết đến node sau nó.

ss_1

Hình ảnh minh họa danh sách liên kết

Với tính cơ động của mình, danh sách liên kết được sử dụng nhiều để tổ chức các dữ liệu mà người lập trình không biết trước kích thước. Ngoài ra danh sách liên kết còn được sử dụng để tổ chức dữ liệu một cách thứ tự, chẳng hạn như StackQueue là những cấu trúc dữ liệu có thứ tự có thể hiện thực được từ danh sách liên kết.

Stack

Khi bạn lấy dĩa trong bếp, bạn thường lấy cái trên cùng, và sau khi rửa dĩa xong, bạn lại xếp từ trên xuống. Đó là một hình ảnh trong thực tế của Stack. Khi bạn lấy phần tử dĩa ra chồng dĩa, nó được gọi là pop, ngược lại khi bạn để dĩa vào lại, nó được gọi là push. Một điều cần phải lưu ý khi bạn hiện thực hóa cấu trúc dữ liệu này, đó là Stack chỉ có thể truy cập được phần tử trên cùng của nó (giống như bạn chỉ có thể lấy cái dĩa trên cùng của chồng dĩa vậy). Ngoài ra, Stack có một đặc điểm rất hay đó là thứ tự của các phần tử được đưa vào Stack sẽ là Vào trước – Ra sau. Vì những đặc điểm này của Stack cho nên chúng có một số ứng dụng sau:

  • Dùng để đảo ngược 1 chuỗi các ký tự.
  • Dùng để hiện thực hóa tính năng undo của phần mềm.
  • Dùng để quản lý những dữ liệu mà chúng ta chỉ cần quan tâm đến phần tử được push vào sau cùng của Stack. (ví dụ như quản lý State Game, trạng thái của nhân vật trong trò chơi…).

ss_2

Hình ảnh minh họa về Stack

Queue

Khi bạn xếp hàng để mua hàng, người đến trước sẽ được thanh toán trước, người đến sau sẽ phải thanh toán sau. Đó là hình ảnh trong thực tế của Queue. Khi một người đi ra khỏi hàng đợi, được gọi là dequeue; khi một người bước vào xếp hàng, được gọi là enqueue. Khi bạn quản lý dữ liệu bằng cấu trúc này, nó sẽ tạo ra sự thứ tự trong dữ liệu đưa vào, vì đặc điểm này mà Queue có một số ứng dụng sau:

  • Cấu trúc hàng đợi thông điệp.
  • Cấu trúc hàng đợi cho người chơi trong các trò chơi có tính năng tự tìm đối thủ.
  • Cấu trúc các bộ đệm truyền tải dữ liệu.

ss_3

Hình ảnh minh họa về Queue