Trước khi tìm hiểu về danh sách liên kết, chúng ta cần nắm rõ nhược điểm của mảng và ưu điểm của con trỏ trong lập trình C.
Nhược điểm của mảng
- Sử dụng cấp phát bộ nhớ tĩnh (static memory allocation).
- Gây lãng phí bộ nhớ do kích thước cố định.
- Thiếu hụt bộ nhớ khi cần mở rộng vượt quá kích thước khai báo.
Ưu điểm của con trỏ
- Hỗ trợ cấp phát bộ nhớ động (dynamic memory allocation).
- Sử dụng bộ nhớ hiệu quả, chỉ cấp phát khi cần và giải phóng khi không dùng.
Danh sách liên kết (Linked List)
Danh sách liên kết sử dụng cấp phát bộ nhớ động, cho phép tự động mở rộng và thu nhỏ. Chúng được định nghĩa là tập hợp các nút (node), mỗi nút gồm hai phần: dữ liệu (data) và liên kết (link). Biểu diễn như sau:
Các loại danh sách liên kết
Danh sách liên kết có 4 loại chính:
- Danh sách liên kết đơn (Single / Singly linked list)
- Danh sách liên kết kép (Double / Doubly linked list)
- Danh sách liên kết đơn vòng (Circular single linked list)
- Danh sách liên kết kép vòng (Circular double linked list)
Danh sách liên kết đơn (Singly Linked List)
Biểu diễn:
Mỗi nút gồm 2 phần:
- Data (Dữ liệu)
- Link (Liên kết)
Trường link luôn trỏ đến nút tiếp theo trong danh sách. Trường link của nút cuối cùng là NULL.
Danh sách liên kết kép (Doubly Linked List)
Biểu diễn:
Mỗi nút gồm 3 phần:
- Data part (Phần dữ liệu)
- Left link (Liên kết trái)
- Right link (Liên kết phải)
Left link trỏ đến nút bên trái, right link trỏ đến nút bên phải. Left link của nút đầu và right link của nút cuối phải là NULL.
Danh sách liên kết đơn vòng (Circular Single Linked List)
Biểu diễn:
Mỗi nút gồm 2 phần: Data part và Link part. Link luôn trỏ đến nút tiếp theo. Link của nút cuối trỏ về nút đầu tiên.
Danh sách liên kết kép vòng (Circular Double Linked List)
Biểu diễn:
Mỗi nút gồm 3 phần: Data part, Left link, Right link. Left link trỏ đến nút trái, right link trỏ đến nút phải. Left link của nút đầu trỏ đến nút cuối, right link của nút cuối trỏ đến nút đầu.