Danh sách liên kết DSA
Danh sách liên kết , như từ ngụ ý, là một danh sách trong đó các nút được liên kết với nhau. Mỗi nút chứa dữ liệu và một con trỏ. Cách chúng được liên kết với nhau là mỗi nút trỏ đến vị trí của nút tiếp theo trong bộ nhớ.
Danh sách liên kết
Danh sách liên kết bao gồm các nút có một số loại dữ liệu và một con trỏ hoặc liên kết tới nút tiếp theo.
Lợi ích lớn của việc sử dụng danh sách liên kết là các nút được lưu trữ ở bất kỳ nơi nào có dung lượng trống trong bộ nhớ, các nút không cần phải được lưu trữ liền kề nhau giống như các phần tử được lưu trữ trong mảng. Một điều thú vị khác với danh sách liên kết là khi thêm hoặc xóa các nút, các nút còn lại trong danh sách không cần phải dịch chuyển.
Danh sách liên kết so với mảng
Cách dễ nhất để hiểu danh sách liên kết có lẽ là so sánh danh sách liên kết với mảng.
Danh sách liên kết bao gồm các nút và là cấu trúc dữ liệu tuyến tính do chúng tôi tự tạo, không giống như mảng là cấu trúc dữ liệu hiện có trong ngôn ngữ lập trình mà chúng tôi có thể sử dụng.
Các nút trong danh sách liên kết lưu trữ liên kết đến các nút khác, nhưng các phần tử mảng không cần lưu trữ liên kết đến các phần tử khác.
Lưu ý: Cách lưu trữ danh sách và mảng liên kết trong bộ nhớ sẽ được giải thích chi tiết hơn ở trang tiếp theo .
Bảng bên dưới so sánh danh sách liên kết với mảng để hiểu rõ hơn về danh sách liên kết là gì.
| Arrays | Linked Lists | |
|---|---|---|
| An existing data structure in the programming language | Yes | No |
| Fixed size in memory | Yes | No |
| Elements, or nodes, are stored right after each other in memory (contiguously) | Yes | No |
| Memory usage is low (each node only contains data, no links to other nodes) |
Yes | No |
| Elements, or nodes, can be accessed directly (random access) | Yes | No |
| Elements, or nodes, can be inserted or deleted in constant time, no shifting operations in memory needed. | No | Yes |
Để giải thích những khác biệt này một cách chi tiết hơn, trang tiếp theo sẽ tập trung vào cách các danh sách và mảng liên kết được lưu trữ trong bộ nhớ.
