Một Danh sách liên kết (Linked List) là một dãy các cấu trúc dữ liệu được kết nối với nhau thông qua các liên kết (link). Hiểu một cách đơn giản thì Danh sách liên kết là một cấu trúc dữ liệu bao gồm một nhóm các nút (node) tạo thành một chuỗi. Mỗi nút gồm dữ liệu ở nút đó và tham chiếu đến nút kế tiếp trong chuỗi.
- Dưới đây là một số điểm cần nhớ về Danh sách liên kết:
- Link đầu tiên được gọi là First
- Link cuối được gọi là Last
- Mỗi một link sẽ chưa dữ liệu và tham chiếu đến phần tử trước/tiếp theo của nó
- Link cuối cùng mang một link là null để đánh dấu điểm cuối của danh sách.
- Các loại Linked List
- Danh sách liên kết đơn (Simple Linked List): chỉ duyệt các phần tử theo chiều về trước.
- Danh sách liên kết đôi (Doubly Linked List): các phần tử có thể được duyệt theo chiều về trước hoặc về sau.
- Danh sách liên kết vòng (Circular Linked List): phần tử cuối cùng chứa link của phần tử đầu tiên như là next và phần tử đầu tiên có link tới phần tử cuối cùng như là prev.
Nhược điểm:
- Một danh sách liên kết đơn giản không cho phép truy cập ngẫu nhiên dữ liệu.
- Chính vì lí do trên mà một số phép tính như tìm phần tử cuối cùng, xóa phần tử ngẫu nhiên hay chèn thêm, tìm kiếm có thể phải duyệt tất cả các phần tử.
Một hàng đợi là mở ở cả hai đầu. Một đầu luôn luôn được sử dụng để chèn dữ liệu vào (hay còn gọi là sắp vào hàng) và đầu kia được sử dụng để xóa dữ liệu (rời hàng). Cấu trúc dữ liệu hàng đợi tuân theo phương pháp First-In-First-Out, tức là dữ liệu được nhập vào đầu tiên sẽ được truy cập đầu tiên.
- dequeue(): xóa phần tử đầu và trả về phần tử cuối
- enqueue(): thêm phần tử vào cuối hàng đợi
- peek(): trả về dữ liệu của phần tử cuối
- isEmpty(): return true nếu hàng đợi rỗng
Trong đời sống thực, ngăn xếp chỉ cho phép các hoạt động tại vị trí trên cùng của ngăn xếp. Ví dụ, chúng ta chỉ có thể đặt hoặc thêm một lá bài hay một cái đĩa 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.
Đặc điểm này làm cho ngăn xếp trở thành cấu trúc dữ liệu dạng LIFO. LIFO là viết tắt của Last-In-First-Out. Ở đây, phần tử được đặt vào (được chèn, được thêm vào) cuối cùng sẽ được truy cập đầu tiên. Trong thuật ngữ ngăn xếp, hoạt động chèn được gọi là hoạt động PUSH và hoạt động xóa được gọi là hoạt động POP.
- push() thêm phần tử lên đầu stack
- pop() xóa phần tử ở trên đầu ngăn xếp và trả về nó
- top() trả về phần tử trên đầu ngăn xếp
- isEmpty() kiểm tra stack có rỗng hay không
Cấu trúc dữ liệu cây biểu diễn các nút (node) được kết nối bởi các cạnh.
- Đường: là một dãy các nút cùng với các cạnh của một cây.
- Nút gốc (Root): nút trên cùng của cây được gọi là nút gốc. Một cây sẽ chỉ có một nút gốc và một đường xuất phát từ nút gốc tới bất kỳ nút nào khác. Nút gốc là nút duy nhất không có bất kỳ nút cha nào.
- Nút cha: bất kỳ nút nào ngoại trừ nút gốc mà có một cạnh hướng lên một nút khác thì được gọi là nút cha.
- Nút con: nút ở dưới một nút đã cho được kết nối bởi cạnh dưới của nó được gọi là nút con của nút đó.
- Nút lá: nút mà không có bất kỳ nút con nào thì được gọi là nút lá.
- Cây con: cây con biểu diễn các con của một nút.
- Truy cập: kiểm tra giá trị của một nút khi điều khiển là đang trên một nút đó.
- Duyệt: duyệt qua các nút theo một thứ tự nào đó.
- Bậc: bậc của một nút biểu diễn số con của một nút. Nếu nút gốc có bậc là 0, thì nút con tiếp theo sẽ có bậc là 1, và nút cháu của nó sẽ có bậc là 2, …
- Khóa (Key): biểu diễn một giá trị của một nút dựa trên những gì mà một thao tác tìm kiếm thực hiện trên nút.
Cây nhị phân là một cấu trúc dữ liệu đặc biệt được sử dụng cho mục đích lưu trữ dữ liệu. Một cây nhị phân có một điều kiện đặc biệt là mỗi nút có thể có tối đa hai nút con.
Một node trong cây nhị phân sẽ lưu trữ:
- Dữ liệu của nó
- Tham chiếu đến nút con bên trái
- Tham chiếu đến nút con bên phải
Cây nhị phân tìm kiếm là cây nhị phân trong đó tại mỗi node, khóa của node đang xét lớn hơn khóa của tất cả các node thuộc node con trái và nhỏ hơn khóa của tất cả các node thuộc node con phải.
Heap thực chất là một cây cân bằng thỏa mãn các điều kiện sau:
- Một nút có không quá 2 nút con.
- Với Heap Max thì nút gốc là nút lớn nhất, mọi nút con đều không lớn hơn nút cha của nó. Với Heap Min thì ngược lại.
