6 cấu trúc dữ liệu mà mọi lập trình viên nên biết

Con đường trở thành một lập trình viên thành thạo và thành công là rất khó, nhưng một trong những điều đó chắc chắn có thể đạt được. Cấu trúc dữ liệu là thành phần cốt lõi mà mọi sinh viên lập trình phải nắm vững, và rất có thể bạn đã học hoặc làm việc với một số cấu trúc dữ liệu cơ bản như mảng hoặc danh sách.

Người phỏng vấn có xu hướng thích đặt những câu hỏi liên quan đến cấu trúc dữ liệu, vì vậy nếu bạn đang chuẩn bị cho một cuộc phỏng vấn xin việc, bạn sẽ cần phải trang bị kiến ​​thức về cấu trúc dữ liệu của mình. Đọc tiếp khi chúng tôi liệt kê các cấu trúc dữ liệu quan trọng nhất cho các lập trình viên và các cuộc phỏng vấn xin việc.

1. Danh sách liên kết

Danh sách liên kết là một trong những cấu trúc dữ liệu cơ bản nhất và thường là điểm khởi đầu cho sinh viên trong hầu hết các khóa học về cấu trúc dữ liệu. Danh sách được liên kết là cấu trúc dữ liệu tuyến tính cho phép truy cập dữ liệu tuần tự.

Các phần tử trong danh sách liên kết được lưu trữ trong các nút riêng lẻ được kết nối (liên kết) bằng cách sử dụng con trỏ. Bạn có thể coi danh sách liên kết là một chuỗi các nút được kết nối với nhau thông qua các con trỏ khác nhau.

Liên quan: Giới thiệu về cách sử dụng danh sách được liên kết trong Java

Trước khi chúng ta đi vào chi tiết cụ thể của các loại danh sách liên kết khác nhau, điều quan trọng là phải hiểu cấu trúc và cách triển khai của từng nút. Mỗi nút trong danh sách được liên kết có ít nhất một con trỏ (các nút danh sách được liên kết kép có hai con trỏ) kết nối nó với nút tiếp theo trong danh sách và chính mục dữ liệu.

Mỗi danh sách liên kết có một nút đầu và nút đuôi. Các nút danh sách liên kết đơn chỉ có một con trỏ trỏ đến nút tiếp theo trong chuỗi. Ngoài con trỏ tiếp theo, các nút danh sách được liên kết kép có một con trỏ khác trỏ đến nút trước đó trong chuỗi.

Các câu hỏi phỏng vấn liên quan đến danh sách liên kết thường xoay quanh việc chèn, tìm kiếm hoặc xóa một phần tử cụ thể. Việc chèn vào danh sách liên kết mất O (1) thời gian, nhưng việc xóa và tìm kiếm có thể mất O (n) thời gian trong trường hợp xấu nhất. Vì vậy, danh sách liên kết không phải là lý tưởng.

2. Cây nhị phân

Cây nhị phân là tập con phổ biến nhất của cấu trúc dữ liệu họ cây; các phần tử trong cây nhị phân được sắp xếp theo thứ bậc. Các loại cây khác bao gồm cây AVL, đỏ-đen, B, v.v. Các nút của cây nhị phân chứa phần tử dữ liệu và hai con trỏ đến mỗi nút con.

Mỗi nút cha trong cây nhị phân có thể có tối đa hai nút con, và mỗi nút con, đến lượt nó, có thể là cha của hai nút.

Liên quan: Hướng dẫn cho người mới bắt đầu về cây nhị phân

Cây tìm kiếm nhị phân (BST) lưu trữ dữ liệu theo thứ tự được sắp xếp, trong đó các phần tử có khóa-giá trị nhỏ hơn nút cha được lưu trữ ở bên trái và các phần tử có khóa-giá trị lớn hơn nút cha được lưu trữ ở bên phải.

Cây nhị phân thường được hỏi trong các cuộc phỏng vấn, vì vậy nếu bạn đã sẵn sàng cho một cuộc phỏng vấn, bạn nên biết cách làm phẳng cây nhị phân, tra cứu một phần tử cụ thể, v.v.

3. Bảng băm

Bảng băm hoặc bản đồ băm là một cấu trúc dữ liệu hiệu quả cao lưu trữ dữ liệu ở định dạng mảng. Mỗi phần tử dữ liệu được gán một giá trị chỉ mục duy nhất trong bảng băm, cho phép tìm kiếm và xóa hiệu quả.

Quá trình gán hoặc ánh xạ các khóa trong một bản đồ băm được gọi là quá trình băm. Hàm băm càng hiệu quả thì hiệu quả của bảng băm càng tốt.

Mỗi bảng băm lưu trữ các phần tử dữ liệu trong một cặp chỉ số-giá trị.

Trong đó giá trị là dữ liệu được lưu trữ và chỉ mục là số nguyên duy nhất được sử dụng để ánh xạ phần tử vào bảng. Các hàm băm có thể rất phức tạp hoặc rất đơn giản, tùy thuộc vào hiệu quả cần thiết của bảng băm và cách bạn giải quyết các xung đột.

Các xung đột thường phát sinh khi một hàm băm tạo ra cùng một ánh xạ cho các phần tử khác nhau; Xung đột bản đồ băm có thể được giải quyết theo nhiều cách khác nhau, sử dụng địa chỉ mở hoặc chuỗi.

Bảng băm hoặc bản đồ băm có nhiều ứng dụng khác nhau, bao gồm cả mật mã. Chúng là cấu trúc dữ liệu được lựa chọn đầu tiên khi cần chèn hoặc tìm kiếm trong thời gian O (1) không đổi.

4. Ngăn xếp

Ngăn xếp là một trong những cấu trúc dữ liệu đơn giản và khá dễ để làm chủ. Cấu trúc dữ liệu ngăn xếp về cơ bản là bất kỳ ngăn xếp ngoài đời thực nào (hãy nghĩ đến một chồng hộp hoặc đĩa) và hoạt động theo cách thức LIFO (Cuối cùng Trong Lần xuất trước).

Thuộc tính LIFO của ngăn xếp có nghĩa là phần tử bạn đã chèn vào cuối cùng sẽ được truy cập đầu tiên. Bạn không thể truy cập các phần tử bên dưới phần tử trên cùng trong ngăn xếp mà không xuất hiện các phần tử bên trên nó.

Ngăn xếp có hai hoạt động chính — đẩy và bật. Push được sử dụng để chèn một phần tử vào ngăn xếp và pop sẽ xóa phần tử trên cùng khỏi ngăn xếp.

Chúng cũng có rất nhiều ứng dụng hữu ích, vì vậy người phỏng vấn thường hỏi các câu hỏi liên quan đến ngăn xếp. Biết cách đảo ngược một ngăn xếp và đánh giá các biểu thức là khá cần thiết.

5. Hàng đợi

Hàng đợi tương tự như ngăn xếp nhưng hoạt động theo cách FIFO (Nhập trước Xuất trước), nghĩa là bạn có thể truy cập các phần tử bạn đã chèn trước đó. Cấu trúc dữ liệu hàng đợi có thể được hình dung như bất kỳ hàng đợi nào trong đời thực, nơi mọi người được định vị dựa trên thứ tự đến của họ.

Thao tác chèn của hàng đợi được gọi là hàng đợi, và việc xóa / xóa một phần tử khỏi đầu hàng đợi được gọi là sắp xếp lại.

Liên quan: Hướng dẫn cho người mới bắt đầu để hiểu hàng đợi và hàng đợi ưu tiên

Hàng đợi ưu tiên là một ứng dụng tích hợp của hàng đợi trong nhiều ứng dụng quan trọng như lập lịch CPU. Trong hàng đợi ưu tiên, các phần tử được sắp xếp theo thứ tự ưu tiên của chúng hơn là thứ tự đến.

6. Đống

Heaps là một loại cây nhị phân trong đó các nút được sắp xếp theo thứ tự tăng dần hoặc giảm dần. Trong một đống tối thiểu, giá trị khóa của cha bằng hoặc nhỏ hơn giá trị con của nó và nút gốc chứa giá trị nhỏ nhất của toàn bộ đống.

Tương tự, nút gốc của một đống tối đa chứa giá trị khóa lớn nhất của đống; bạn phải giữ lại thuộc tính heap tối thiểu / tối đa trong suốt heap.

Liên quan: Heaps so với Stacks: Cái gì làm cho chúng khác biệt?

Các đống có rất nhiều ứng dụng do tính chất rất hiệu quả của chúng; chủ yếu, hàng đợi ưu tiên thường được thực hiện thông qua heap. Chúng cũng là một thành phần cốt lõi trong các thuật toán heapsort.

Tìm hiểu cấu trúc dữ liệu

Ban đầu, cấu trúc dữ liệu có vẻ rắc rối nhưng hãy dành đủ thời gian và bạn sẽ thấy chúng dễ dàng như chiếc bánh.

Chúng là một phần quan trọng của lập trình và hầu hết mọi dự án sẽ yêu cầu bạn sử dụng chúng. Biết cấu trúc dữ liệu nào là lý tưởng cho một kịch bản nhất định là rất quan trọng.

Đọc tiếp

Giới thiệu về tác giả