Tài liệu Danh sách liên kết (DSLK) trong Cấu trúc dữ liệu

1. Khái niệm DSLK
Có lẽ trước hết bạn cần nắm vững khái niệm ô nhớ và con trỏ. Trong tư duy của bạn cần tách biệt rõ ràng 2 khái niệm này. Ô nhớ luôn nằm cố định rải rác đâu đó trên bộ nhớ máy tính, con trỏ là 1 công cụ giúp ta biết được địa chỉ ô nhớ đó, truy xuất, chỉnh sữa dữ liệu trên ô nhớ, hay thậm chí là giải phóng ô nhớ. Như vậy 1 con trỏ khi đang trỏ vào 1 ô nhớ, nó chỉ có thể cho ta thông tin trên ô đó mà thôi, làm thế nào để có thể lấy thông tin ở 1 ô nhớ khác? Và DSLK ra đời từ đây!
Chúng ta xem qua cách định nghĩa sau:

struct node
{ int value;
node* next;
};

Có 1 điều thú vị trong định nghĩa này đó là sự đệ quy, chúng ta sử dụng node trong lúc đang định nghĩa node. Trường next có 1 ý nghĩa rất quan trọng, và nó chính là chiếc cầu dẫn bạn từ ô nhớ này đi sang ô nhớ khác.
Cấp phát bộ nhớ: giả sử bạn đang có 1 con trỏ t kiểu node, nó chưa trỏ vào đâu cả, bạn cần xin cấp phát 1 ô nhớ mới kiểu node cho t trỏ vào, dùng lệnh:

t = (node*)malloc(sizeof(node));

Hàm malloc(int size) sẽ tạo ra 1 ô nhớ mới trên bộ nhớ có kích thước size byte đồng thời trả về 1 con trỏ kiểu tổng quát đang trỏ vào ô nhớ đấy, ta phải ép kiểu thành con trỏ kiểu node. Lúc này ta có thể thoải mái thao tác trên ô nhớ thông qua con trỏ t.
Bây giờ ta tạo ra 1 con trỏ z tương tự như vậy, hãy xem đoạn code sau:

z->value = 2006;
z->next = NULL;
t->value = 3006;
t->next = z;


Câu lệnh cuối cùng đáng xem, trường next của t (là 1 con trỏ kiểu node) được trỏ vào z, hay chính xác hơn là vào ô nhớ mà z đang trỏ vào. Vậy là từ ô nhớ này ta đã có thể nhảy sang ô nhớ khác.
Chú ý câu lệnh có chữ NULL, có nghĩa rằng từ ô nhớ mà z đang trỏ vào này, bạn chẳng thể nhảy đi đâu được nữa, kĩ thuật này dùng để nhận biết phần tử nằm cuối danh sách.
Như vậy, chỉ cần có trong tay 1 con trỏ (chính xác là 1 ô nhớ và con trỏ đang trỏ vào đó), thông qua trường next bạn có thể nhảy tuần tự đến các ô nhớ khác, lấy thông tin trên đó, cho đến khi nào không nhảy được nữa. Đó chính là 1 DSLK. Tuy nhiên để có thể nhảy nhót thoái mái như thế bạn cần phải biết cách tạo ra trước đó 1 DSLK đã. Chúng ta chuyển qua phần 2