Danh sách liên kết

Trong khoa học máy tính, danh sách liên kết (tiếng Anh: linked list) là tập hợp tuyến tính các phần tử dữ liệu, với thứ tự không được đưa ra bởi vị trí vật lý nào của chúng trong bộ nhớ. Thay vào đó, mỗi phần tử sẽ trỏ đến phần tử tiếp theo. Nó là một cấu trúc dữ liệu bao gồm một tập hợp các nút cùng thể hiện cho một dãy. Ở dạng cơ bản nhất, mỗi nút chứa: dữ liệu và một tham chiếu (hay nói cách khác là một liên kết) đến nút tiếp theo trong chuỗi. Cấu trúc này cho phép chèn hay loại bỏ phần tử khỏi bất kì vị trí nào trong trong chuỗi một cách hiệu quả trong quá trình lặp. Các biến thể phức tạp hơn như thêm các liên kết bổ sung, cho phép chèn hay loại bỏ các nút hiệu quả hơn tại vị trí bất kì. Một nhược điểm của danh sách liên kết là thời gian truy cập là tuyến tính (và khó thực thi ống dẫn). Truy cập nhanh hơn, ví dụ như truy cập ngẫu nhiên, là không khả thi. Mảng có vùng đệm (cache locality) tốt hơn so với danh sách liên kết.

Danh sách liên kết là một trong những cấu trúc dữ liệu đơn giản và phổ biến nhất. Nó có thể được dùng để hiện thực một số kiểu dữ liệu trừu tượng phổ biến khác, bao gồm danh sách (list), ngăn xếp (stack), hàng đợi, mảng kết hợp, và S-expression, mặc dù không có gì lạ khi hiện thực các cấu trúc dữ liệu đó mà không dựa trên nền tảng của danh sách liên kết.

Lợi ích chính của danh sách liên kết so với mảng thông thường là các phần tử danh sách có thể được chèn hay xóa một cách dễ dàng mà không cần phân bổ lại hoặc sắp xếp lại toàn bộ cấu trúc vì các mục dữ liệu không cần được lưu trữ liên tục trong bộ nhớ hay trên đĩa, trong khi tái cấu trúc một mảng tại thời gian chạy là một hoạt động tốn kém hơn nhiều. Danh sách liên kết cho phép chèn hay xóa nút tại bất kì điểm nào trong danh sách.

Lịch sử
Allen Newell, Cliff Shaw and Herbert A. Simon từ RAND Corporation và Trường Đại học Carnegie Mellon đã phát triển danh sách liên kết vào năm 1955-1956. Nó được dùng làm một cấu trúc dữ liệu chính cho một ngôn ngữ lập trình gọi là Information Processing Language (IPL). IPL sau đó đã được được dùng để phát triển một số chương trình liên quan đến trí tuệ nhân tạo như Logic Theory Machine, General Problem Solver và một chương trình engine cờ vua.

Khái niệm và thuật ngữ
Mỗi một bản ghi của danh sách liên kết thường được gọi là "nút", "node" hoặc là "phần tử". Trường của nút chứa địa chỉ thường được gọi là "liên kết tiếp theo" hoặc "con trỏ tiếp theo". Trường còn lại được gọi là "dữ liệu", "thông tin" hay "giá trị".

Trong lập trình, các lập trình viên thường sử dụng từ khóa "head" như nút đầu tiên và "tail" như nút cuối cùng.

Danh sách liên kết đơn
Danh sách liên kết đơn là một danh sách liên kết đơn giản nhất khi bao gồm hai trường là "giá trị" và trường "liên kết tiếp theo". Các thao tác có thể thực hiện trên danh sách liên kết đơn như chèn, xóa và duyệt.
giữa|khung|Danh sách liên kết đơn
Một hàm thêm nút cơ bản trong C++:
{{Syntaxhighlight|lang=cpp|code=node addNode(node head, int value) {
node temp, p; // Tạo hai nút là temp và p
temp = createNode(); // Giả sử hàm createNode tạo một nút có giá trị bằng 0 và trỏ nút tiếp theo là NULL rồi gán cho nút temp
temp->value = value; // Gán giá trị value vào trường dữ liệu nút temp
if (head == NULL) {
head = temp;     // Liên kết đơn rỗng thì gán head bằng temp
}
else {
p = head; // Gán giá trị head cho p
while (p->next != NULL) {
p = p->next; // Chạy qua danh sách bằng hàm while-do cho đến khi cho trỏ tiếp theo là NULL thì dừng lại. Con trỏ cuối cùng sẽ là con trỏ NULL
}
p->next = temp; // Gán con trỏ cuối cùng bằng con trỏ mới tạo
}
return head;
}
}}

Danh sách liên kết đôi
Tương tự như danh sách liên kết đơn, danh sách liên kết đôi cũng có hai trường "giá trị" và "liên kết tiếp theo". Tuy nhiên, danh sách liên kết đôi sẽ bao gồm thêm một con trỏ chính là "liên kết trước đó", để trỏ về nút trước đó của nút hiện tại.

Cơ bản của node trong ngôn ngữ C++:
{{Syntaxhighlight|code=struct Node{
int data; // Cho giá trị có kiểu số nguyên
Node next; // Địa chỉ của con trỏ tiếp theo
Node prev; // Địa chỉ của con trỏ trước đó
};
typedef struct Node NODE;|lang=cpp}}

Danh sách liên kết nhân
Trong danh sách liên kết nhân, mỗi nút sẽ chứa từ hai hoặc nhiều trường liên kết, mỗi trường sẽ được sử dụng để nối với một tập hợp các dữ liệu nhất định cùng tập hợp (ví dụ: tên, phòng ban, ngày sinh,...). Danh sách liên kết đôi cũng có thể xem là trường hợp đặc biệt của danh sách liên kết nhân.

Danh sách liên kết vòng
Trong danh sách liên kết đơn, nút cuối cùng sẽ trỏ đến tham chiếu rỗng, tuy nhiên ở danh sách liên kết vòng, nút cuối cùng sẽ trỏ đến nút đầu tiên của danh sách liên kết.

Tham khảo

Tài liệu tham khảo

Liên kết ngoài

Description from the Dictionary of Algorithms and Data Structures
Introduction to Linked Lists, Stanford University Computer Science Library
Linked List Problems, Stanford University Computer Science Library
Open Data Structures - Chapter 3 - Linked Lists
Patent for the idea of having nodes which are in several linked lists simultaneously (note that this technique was widely used for many decades before the patent was granted)