Bài 3.1. Giới thiệu về danh sách liên kết
Nội dung bài học
- Khái niệm danh sách liên kết
- Mục đích sử dụng
- Phân loại danh sách liên kết
Khái niệm danh sách liên kết
- Danh sách liên kết là kiểu cấu trúc dữ liệu tuyến tính trong đó các phần tử của nó không bắt buộc lưu trữ ở các vùng nhớ liền kề nhau.
- Các phần tử của danh sách liên kết được kết nối với nhau qua con trỏ.
- Nói cách khác, một danh sách liên kết bao gồm các node trong đó mỗi node chứa dữ liệu của nó và tham chiếu đến node liên quan.
Mục đích sử dụng
- Sử dụng linked list cho các danh sách lưu trữ dữ liệu có kích thước lớn, số lượng phần tử của danh sách này không được biết trước và có thể thay đổi.
- Sử dụng linked list khi không cần truy cập ngẫu nhiên vào bất kì phần tử nào.
- Sử dụng linked list cho phép chèn, xóa phần tử ở bất cứ vị trí nào trong tập hợp các phần tử của nó.
- Khác với mảng(chỉ phù hợp với các tập dữ liệu nhỏ, số phần tử tối đa cố định và đã được biết trước).
Phân loại danh sách liên kết
- Danh sách liên kết đơn.
- Danh sách liên kết đôi.
- Danh sách liên kết đơn vòng.
- Danh sách liên kết đôi vòng.
Danh sách liên kết đơn
- Nếu ta đang nói về danh sách liên kết thì mặc định đó là danh sách liên kết đơn.
- Cấu trúc dữ liệu này gồm nhiều phần tử nối với nhau theo một chiều từ đầu đến cuối.
- Mỗi phần tử của danh sách liên kết gọi là một node.
- Mỗi node gồm 2 phần chính: dữ liệu của node và địa chỉ của node kế tiếp.
- Phần dữ liệu của node có thể là các dữ liệu đơn như giá trị số, kí tự… Hoặc cũng có thể là các giá trị phức tạp như thông tin của đối tượng sinh viên.
- Phần địa chỉ của một node được lưu trữ trong một con trỏ(thường đặt tên là next, pNext) cùng kiểu với kiểu của node hiện tại.
- Biểu diễn của mỗi node:
- T là kiểu dữ liệu của node.
- Tham chiếu next dùng để trỏ đến node kế tiếp.
- Mã:
template<class T> class Node {
public:
T data; // phần dữ liệu của một node
Node<T>* next; // con trỏ next chứa địa chỉ node kế tiếp
Node(T data) {
this->next = null; // mặc định khi tạo node mới next trỏ tới null
this->data = data; // gán giá trị
}
};Danh sách liên kết đôi
- Danh sách liên kết đôi giống như danh sách liên kết đơn. Với sự khác biệt ở chỗ mỗi node của danh sách liên kết đôi có thêm một con trỏ để trỏ đến node trước nó.
- Biểu diễn node của danh sách liên kết đôi trong Java:
- Phần data là dữ liệu của node.
- Tham chiếu next, prev lần lượt là con trỏ trỏ đến node liền sau và liền trước.
- Mã:
template<class T> class Node {
public:
T data; // phần dữ liệu của một node
Node<T>* next; // con trỏ next chứa địa chỉ node kế tiếp
Node<T>* prev; // con trỏ prev chứa địa chỉ node phía trước
Node(T data) {
this->next = null; // mặc định khi tạo node mới next trỏ tới null
this->data = data; // gán giá trị
}
};Danh sách liên kết đơn vòng
- Là biến thể của danh sách liên kết đơn trong đó:
- Con trỏ next của node cuối cùng của danh sách sẽ trỏ đến địa chỉ của node đầu tiên trong danh sách.
- Hình minh họa.
Danh sách liên kết đôi vòng
- Là biến thể của danh sách liên kết đôi trong đó:
- Con trỏ next của node cuối cùng của danh sách sẽ trỏ đến địa chỉ của node đầu tiên trong danh sách;
- Con trỏ prev của node đầu tiên sẽ trỏ đến địa chỉ của node cuối cùng trong danh sách.
- Hình minh họa:
