Cấu trúc dữ liệu
Cấu trúc dữ liệu cơ bản bao gồm:
Mảng
Mảng là một danh sách các phần tử liên tiếp nhau cùng kiểu dữ liệu. Mảng tĩnh có số không thay đổi lúc biên dịch chương trình, còn mảng động có dữ liệu được khai báo trong Heap. Mảngcó thời gian truy cập một phần tử là O(1).
Danh sách liên kết
Danh sách liên kết là tập hợp các dữ liệu mà một phần tử trỏ đến phần tử tiếp theo. Mỗi phần tử chỉ thường có hai phần đó chính là dữ liệu và tham chiếu đến phần tử tiếp theo. Lợi ích chính khi sử dụng danh sách liên kết là thao tác xóa hoặc thêm một phần tử chỉ mất thời gian cố định `O(1)`.
Stack
Ngăn xếp (tiếng Anh: stack) là một cấu trúc dữ liệu hoạt động theo nguyên lý vào sau ra trước (Last In First Out). Có hai hàm phổ biến là chồng lên đỉnh stack - hay được gọi là thao tác push(). Còn một hàm lấy dữ liệu ra khỏi đỉnh là pop().
Stack sử dụng mảng
Ở phần trước chúng ta sử dụng linked list để cài đặt Stack, phần này thì chúng ta sử dụng mảng. Cách này hiệu quả với ngăn xếp có kích thước cố định.
Queue
Hàng đợi hay queue là một cấu trúc dữ liệu dùng để chứa các đối tượng làm việc theo cơ chế First In First Out (FIFO), nghĩa là 'vào trước ra trước'. Có hai hàm phổ biến với queue đó là enQueue() (thêm vào cuối hàng đợi) và deQueue() (xóa một phần từ đầu hàng đợi).
Hash table
Mảng băm là một cấu trúc dữ liệu ánh xạ từ khóa tới dữ liệu. Trong mảng băm các khóa luôn luôn khác nhau. Hàm băm là là hàm số chuyển từ khóa thành giá trị băm tương ứng trong mảng lưu trữ các giá trị cần tìm.
Cây nhị phân
Cây là một cấu trúc dữ liệu liên kết giữa node cha xuống node con. Cây nhị phân là cây mà mỗi nút chỉ có hai nút con. Có hai cách thường dùng để biểu diễn cây nhị phân là sử dụng liên kết hoặc sử dụng mảng.
Cây tìm kiếm nhị phân
Cây tìm kiếm nhị phân là cây với mỗi nút k thì: mỗi khóa trên cây con trái đều nhỏ hơn khóa của nút k và mỗi khóa trên cây con phải đều lớn hơn khóa của nút k.
B-tree
B-tree là cấu trúc cây tìm kiếm tự cân bằng, đây là trường hợp tổng quát của cây nhị phân tự cân bằng. Thời gian tìm kiếm, chèn và xóa một node của B-tree trong thời gian logaric - O(log(n)).
Binary Heap
Heap (đống) là một cấu trúc dữ liệu cây có khóa của mỗi nút lớn hơn khóa của mỗi nút con. Trong heap thì khóa lớn nhất luôn nằm ở nút gốc.