Những kiểu cấu trúc dữ liệu quan trọng mà các lập trình viên không nên bỏ qua.

Cấu trúc dữ liệu (data structure) về cơ bản được định nghĩa là cách lưu trữ và tổ chức dữ liệu có thứ tự, có hệ thống để dữ liệu có thể được sử dụng một cách hiệu quả. Các cấu trúc dữ liệu có thể được ví như là một “thùng chứa” để chứa các dữ liệu theo một bố cục (layout) cụ thể. Theo từng layout này mà các lập trình viên phải hiểu thật rõ về từng loại cấu trúc dữ liệu để có thể chọn được cấu trúc dữ liệu phù hợp nhất để giải quyết vấn đề. 

Thông thường, các cấu trúc dữ liệu được sử dụng trong hầu hết mọi chương trình hay phần mềm đã được phát triển. Một cấu trúc dữ liệu được lựa chọn cẩn thận sẽ cho phép thực hiện thuật toán được hiệu quả hơn. Nó cho phép thực hiện nhiều phép toán, sử dụng ít tài nguyên, thời gian xử lý được cải thiện và bộ nhớ cũng sẽ có thể được tiết kiệm hơn. Đây cũng sẽ là chủ đề mà các Dev thường được hỏi trong các buổi phỏng vấn chuyên môn khi đi xin việc nữa. Vì vậy nên việc chuẩn bị kỹ và có kiến thức tốt về các cấu trúc dữ liệu sẽ giúp ích rất nhiều cho các bạn Dev trong việc nâng cao khả năng lập trình cũng như ghi điểm trong mắt nhà tuyển dụng đó. Dó đó nên trong bài viết này, mình sẽ giải thích về các loại cấu trúc dữ liệu quan trọng mà các lập trình viên nên biết. Hãy cùng tìm hiểu qua bài viết này nhé. 

1. Arrays.

Array hay còn gọi là cấu trúc mảng là kiểu cấu trúc dữ liệu cơ bản và phổ biến nhất. Những kiểu cấu trúc dữ liệu như Stack hay Queue đều được phát triển từ Array. Đây là một loại cấu trúc dữ liệu có thể lưu giữ một số phần tử cố định nếu các phần tử này có cùng một kiểu dữ liệu. Nó có thể là một mảng các số nguyên, một mảng các số thực, một mảng string hay kể cả một mảng của các mảng (mảng 2 chiều). Mảng được đánh chỉ mục, cho phép ta có thể truy cập ngẫu nhiên vào mảng.Có hai khái niệm quan trọng liên quan đến Array:

• Phần tử: Mỗi mục được lưu giữ trong một mảng được gọi là phần tử.
• Chỉ mục (Index): Mỗi vị trí của một phần tử trong một mảng đều có một chỉ mục số được sử dụng để nhận diện phần tử khác nhau.

Các thao tác cơ bản trên mảng bao gồm:

• Thao tác tìm kiếm (search): Thao tác này cho phép chúng ta tìm kiếm một phần tử trong mảng bằng các chỉ mục hay giá trị riêng của nó.
• Thao tác truy cập ngẫu nhiên: Ta có thể truy cập vào một phần tử bất kỳ trong mảng thông qua chỉ mục của từng phần tử đó. 
• Thao tác cập nhật: Cập nhật giá trị của một phần tử đã tồn tại trong mảng thông qua chỉ mục của nó.
• Thao tác chèn: Chèn một phần tử bất kỳ thông qua chỉ mục. Tuy nhiên vì mảng có kích thước cố định nên ta không thể chèn phần tử một cách trực tiếp. Nếu muốn thêm một phần tử vào mảng, đầu tiên ta phải tạo một mảng mới với kích thước được tăng lên so với mảng cũ, sau đó copy các phần từ và thêm phần tử mới vào mảng mới.
• Thao tác xóa: Xóa một phần tử bất kỳ thông qua chỉ mục. Cũng như thao tác chèn, ta cũng không thể trực tiếp xóa phần tử vì kích thước mảng cố định. Đối với thao tác này, ta cần một mảng mới với kích thước nhỏ hơn.

Ứng dụng của mảng:

• Sử dụng để xây dựng nên các cấu trúc dữ liệu khác như là array list, heap, hash table, vector hay matrix.
• Sử dụng cho các thuật toán sắp xếp khác nhau như là insertion sort, quick sort, bubble sort, merge sort.

Các câu hỏi phỏng vấn thường gặp đối với cấu trúc dữ liệu mảng:

• Tìm phần tử nhỏ thứ hai trong một mảng.
• Tìm số nguyên không lặp lại đầu tiên trong một mảng.
• Hợp nhất hai mảng đã được phân loại.
• Sắp xếp lại các giá trị âm và giá trị dương trong một mảng.

2. Stacks.

Chắc hẳn các bạn lập trình viên đều khá quen thuộc với tùy chọn “Undo” rồi, bởi đây là tùy chọn xuất hiện hầu hết ở các ứng dụng hay phần mềm. Vậy bạn có bao giờ tự hỏi “Undo” hoạt động thế nào không? Ý tưởng đằng sau đó là bạn lưu trữ những trạng thái trước đó của công việc trong bộ nhớ theo thứ tự sao cho trạng thái cuối cùng sẽ xuất hiện trước và được sắp xếp ở trên đầu. Để thực hiện được việc này thì sử dụng cấu trúc dữ liệu mảng là không đủ. Vì vậy mà Stack (ngăn xếp) đã được sử dụng và trở nên rất hữu ích. Đây là một dạng cấu trúc kiểu LIFO (Last In First Out – phân tử được đưa vào cuối cùng sẽ xuất hiện và được truy cập đầu tiên). Để dễ hình dung hơn, bạn có thể tưởng tượng đến hình ảnh thực tế trong cuộc sống. Ví dụ, chúng ta chỉ có thể đặt hoặc thêm một lá bài hay một quyển sách vào trên cùng của ngăn xếp. Do đó, cấu trúc dữ liệu trừu tượng ngăn xếp chỉ cho phép các thao tác dữ liệu tại vị trí trên cùng. Tại bất cứ thời điểm nào, chúng ta chỉ có thể truy cập phần tử trên cùng của ngăn xếp.

Hoạt động cơ bản của Stack:

• Push: Thêm một phần tử vào trên đỉnh của stack.
• Pop: Xóa một phần tử khỏi vị trí trên đỉnh của stack.
• isEmpty: Kiểm tra xem một stack có rỗng không.
• isFull: Kiểm tra xem một stack đã đầy chưa.
• Top: Cung cấp cho chúng ta giá trị của phần tử trên cùng của ngăn xếp mà không cần phải thực hiện hoạt động xóa ở trên (hoạt động pop).

Ứng dụng của Stack:

• Dùng để tính toán các giá trị biểu thức.
• Dùng để gọi hàm trong lập trình đệ quy.

 Các câu hỏi phỏng vấn thường gặp về cấu trúc dữ liệu Stack:

• Đánh giá biểu thức hậu tố sử dụng một stack.
• Phân loại giá trị ở một stack.
• Kiểm tra dấu ngoặc đơn trong một biểu thức.

3. Queues.

Cũng giống như Stack, Queue là một loại cấu trúc dữ liệu tuyến tính, lưu trữ các phần tử theo một thứ tự nhất định. Điều khác biệt lớn duy nhất giữa Stack và Queue đó là thay vì sử dụng LIFO thì Queue sử dụng phương pháp FIFO (First in First Out). Một ví dụ thực tế của Queue đó là một hàng người đang xếp hàng ở quầy vé để đợi mua vé. Nếu như người mới đến sẽ xếp hàng ở phía cuối, nối tiếp người đã đến trước đó chứ người đó sẽ không xếp hàng ở phía trên đầu. Tất nhiên là người xếp hàng trước sẽ là người mua được vé trước và rời khỏi hàng. 

Những hoạt động cơ bản của Queue:

• Enqueue: Chèn một phần tử ở phía dưới của một hàng.
• Dequeue: Xóa một phần tử ở phía dưới của một hàng.
• isEmpty: Kiểm tra xem một hàng có trống hay không.
• Top: Trả lại phần tử đầu tiên của một hàng.

Ứng dụng của Queue:

• Sử dụng để cài đặt các hệ thống hàng đợi.
• Sử dụng để quản lý thread trong multithreading.

Các câu hỏi phỏng vấn thường gặp về Queue:

• Cài đặt một stack sử dụng Queue.
• Đảo ngược phần tử đầu tiên của một hàng.
• Tạo số nhị phân từ 1 đến n sử dụng Queue.

4. Linked List.

Linked List là một cấu trúc dữ liệu tuyến tính. Đây cũng là một cấu trúc tuần tự khác bao gồm chuỗi các phần tử được liên kết với nhau theo thứ tự. Do đó, ta chỉ có thể truy cập tuần tự vào Linked List chứ không thể truy cập ngẫu nhiên. Các phần tử trong Linked List được gọi là node, mỗi node sẽ chứa key và một mũi tên để trỏ tới node tiếp theo của nó. Thuộc tính “Head” biểu thị cho phần tử đầu tiên trong Linked List, còn thuộc tính “Tail” biểu thị cho phần tử cuối cùng trong Linked List. 

Một số thao tác cơ bản trên Linked List:

• InsertAtEnd: Chèn một phần tử vào cuối của linked list.
• InsertAtHead: Chèn một phần tử vào đầu của linked list.
• Delete: Xóa một phần tử khỏi linked list.
• DeleteAtHead: Xóa phần tử đầu tiên ra khỏi linked list.
• Search: Tìm kiếm phần tử đầu tiên trong linked list.
• isEmpty: Kiểm tra xem một linked list có trống hay không.

Ứng dụng của Linked List:

• Được dùng cho symbol table management trong thiết kế compiler.
• Được sử dụng trong việc chuyển giữa các chương trình bằng phím tắt Alt + Tab (cài đặt bằng Circular Linked List).

Các câu hỏi phỏng vấn thường gặp đối với cấu trúc dữ liệu Linked List:

• Đảo ngược lại linked list.
• Phát hiện vòng lặp trong một linked list.
• Xóa bỏ sự trùng lặp trong một linked list.

5. Tree.

Tree là một loại cấu trúc dữ liệu phân cấp, trong đó dữ liệu được sắp xếp theo thứ bậc và được liên kết với nhau khi lưu trữ. 

Cấu trúc dữ liệu Tree có rất nhiều kiểu như: N-ary Tree, Balanced Tree, Binary Tree, Binary Search Tree, AVL Tree, Red Black Tree và 2-3 Tree. Trong đó thì phổ biến nhất vẫn là Cây nhị phân (Binary Tree) và Cây tìm kiếm nhị phân (Binary Search Tree). Cây nhị phân là một cấu trúc dữ liệu bao gồm một loạt các nút trong đó mỗi nút có thể có tối đa hai nút con, mỗi nút một giá trị. Root là nút trên cùng trong cấu trúc Binary Tree, không có nút cha.

Cây tìm kiếm nhị phân là một loại cây nhị phân khác trong đó tất cả các giá trị nút là khác nhau, mỗi nút cha có hai nút con, trong đó:

• Nút con bên trái có giá trị nhỏ hơn nút cha.
• Nút con bên phải có giá trị lớn hơn nút cha.

Mỗi nút trong cây tìm kiếm nhị phân bao gồm các thuộc tính sau:

• Key: giá trị được lưu trữ trong node (nút).
• Left: con trỏ tới con bên trái.
• Right: con trỏ tới con bên phải.
• p: con trỏ tới node cha.

Ứng dụng của cấu trúc dữ liệu Tree: 

• Cây nhị phân: Lưu trữ dữ liệu và tính toán biểu thức.
• Cây tìm kiếm nhị phân: Được sử dụng nhiều trong các ứng dụng để tìm kiếm.

Các câu hỏi phỏng vấn thường gặp đối với cấu trúc dữ liệu Tree:

• Tìm chiều cao của một cây nhị phân.
• Tìm giá trị lớn nhất của cây tìm kiếm nhị phân.
• Tìm nút chính xác ở một khoảng cách “k” so với gốc.
• Tìm mối quan hệ của một nút nhất định trên cây nhị phân.

Trên đây là bài viết ngắn gọn của mình giới thiệu về 5 kiểu cấu trúc dữ liệu mà các lập trình viên nên biết. Mong rằng bài viết của mình sẽ đem lại một chút thông tin hay kiến thức bổ ích cho các bạn.