Danh Sách Liên Kết

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.

Mỗi một bản ghi của danh sách liên kết thường được gọi là "nút" 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.

 

Một hàm thêm nút cơ bản trong C++:

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++:

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; 

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.

 

• Juan, Angel (2006). “Ch20 –Data Structures; ID06 - PROGRAMMING with JAVA (slide part of the book 'Big Java', by CayS. Horstmann)” (PDF). tr. 3. Bản gốc (PDF) lưu trữ ngày 6 tháng 1 năm 2012. Truy cập ngày 8 tháng 3 năm 2019.
• Black, Paul E. (ngày 16 tháng 8 năm 2004). Pieterse, Vreda; Black, Paul E. (biên tập). “linked list”. Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. Truy cập ngày 14 tháng 12 năm 2004.
• Antonakos, James L.; Mansfield, Kenneth C., Jr. (1999). Practical Data Structures Using C/C++. Prentice-Hall. tr. 165–190. ISBN 0-13-280843-9.
• Collins, William J. (2005) [2002]. Data Structures and the Java Collections Framework. New York: McGraw Hill. tr. 239–303. ISBN 0-07-282379-8.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2003). Introduction to Algorithms. MIT Press. tr. 205–213, 501–505. ISBN 0-262-03293-7.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). “10.2: Linked lists”. Introduction to Algorithms (ấn bản 2). MIT Press. tr. 204–209. ISBN 0-262-03293-7.
• Green, Bert F., Jr. (1961). “Computer Languages for Symbol Manipulation”. IRE Transactions on Human Factors in Electronics (2): 3–8. doi:10.1109/THFE2.1961.4503292.
• McCarthy, John (1960). “Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I”. Communications of the ACM. 3 (4): 184. doi:10.1145/367177.367199.
• Knuth, Donald (1997). “2.2.3-2.2.5”. Fundamental Algorithms (ấn bản 3). Addison-Wesley. tr. 254–298. ISBN 0-201-89683-4.
• Newell, Allen; Shaw, F. C. (1957). “Programming the Logic Theory Machine”. Proceedings of the Western Joint Computer Conference: 230–240.
• Parlante, Nick (2001). “Linked list basics” (PDF). Stanford University. Truy cập ngày 21 tháng 9 năm 2009.
• Sedgewick, Robert (1998). Algorithms in C. Addison Wesley. tr. 90–109. ISBN 0-201-31452-5.
• Shaffer, Clifford A. (1998). A Practical Introduction to Data Structures and Algorithm Analysis. New Jersey: Prentice Hall. tr. 77–102. ISBN 0-13-660911-2.
• Wilkes, Maurice Vincent (1964). “An Experiment with a Self-compiling Compiler for a Simple List-Processing Language”. Annual Review in Automatic Programming. Pergamon Press. 4 (1): 1. doi:10.1016/0066-4138(64)90013-8.
• Wilkes, Maurice Vincent (1964). “Lists and Why They are Useful”. Proceeds of the ACM National Conference, Philadelphia 1964. ACM (P–64): F1–1.
• Shanmugasundaram, Kulesh (ngày 4 tháng 4 năm 2005). “Linux Kernel Linked List Explained”. Bản gốc lưu trữ ngày 25 tháng 9 năm 2009. Truy cập ngày 21 tháng 9 năm 2009.

• 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)