[Bài đọc] Cấu trúc dữ liệu (Data Structure)

Trong khoa học máy tính, cấu trúc dữ liệu là một cách lưu dữ liệu trong máy tính sao cho nó có thể được sử dụng một cách hiệu quả.

Cấu trúc dữ liệu là hình thức tổ chức một nhóm dữ liệu bao gồm các chức năng:

• Lưu trữ dữ liệu
• Cung cấp các phương thức để thao tác với dữ liệu.

Trong thiết kế nhiều loại chương trình, việc chọn cấu trúc dữ liệu là vấn đề quan trọng. Kinh nghiệm trong việc xây dựng các hệ thống lớn cho thấy khó khăn của việc triển khai chương trình, chất lượng và hiệu năng của kết quả cuối cùng phụ thuộc rất nhiều vào việc chọn cấu trúc dữ liệu tốt nhất.

Mỗi loại cấu trúc dữ liệu phù hợp với một vài loại ứng dụng khác nhau, một số cấu trúc dữ liệu dành cho những công việc đặc biệt. Ví dụ, các B-tree đặc biệt phù hợp trong việc thiết kế cơ sở dữ liệu. Sau khi cấu trúc dữ liệu được chọn, người ta thường dễ nhận thấy thuật toán cần sử dụng. Đôi khi trình tự công việc diễn ra theo thứ tự ngược lại: cấu trúc dữ liệu được chọn do những bài toán quan trọng nhất định có thuật toán chạy tốt nhất với một số cấu trúc dữ liệu cụ thể. Trong cả hai trường hợp, việc lựa chọn cấu trúc dữ liệu là rất quan trọng.

Cấu trúc dữ liệu là một khái niệm rất quan trọng trong lập trình, bởi vì nó ảnh hưởng rất lớn đến hiệu năng của hệ thống. Việc lựa chọn được cấu trúc dữ liệu phù hợp trong từng bài toán sẽ giúp cho hiệu năng của hệ thống được đảm bảo tốt nhất. Ngược lại, nếu không sử dụng đúng cấu trúc dữ liệu cần thiết thì có thể gây ảnh hưởng rất lớn đến hoạt động của hệ thống, hậu quả có thể là rất lớn.

Trong một cấu trúc dữ liệu thì có 2 thành phần quan trọng chính là container và element.

• Container: Là lớp chứa dữ liệu và cung cấp các phương thức để thao tác với dữ liệu
• Elements: Chính là các phần tử dữ liệu

Ví dụ:

• Lớp ArrayList là cấu trúc danh sách, lưu trữ nhiều giá trị liên tiếp nhau
• Các phương thức được cung cấp để thực hiện các thao tác với ArrayList là: Thêm phần tử, xoá phần tử, duyệt phần tử, tìm kiếm…

Các cấu trúc dữ liệu thông dụng

• Set (Tập hợp): Nhóm các phần tử không trùng nhau
• List (Danh sách): Nhóm ác phần tử có thể trùng nhau
• Stack: Nhóm các phần tử theo trật tự first-in/last-out (vào trước/ra sau)
• Queue: Nhóm các phần tử theo trật tự first-in/first-out (vào trước/ra trước)
• Map (Bản đồ): Lưu trữ các cặp key/value
• Tree (Cây): Lưu trữ các phần tử theo mối quan hệ cha-con
• Graph (Đồ thị): Lưu trữ các phần tử theo mối quan hệ mạng lưới