Xem mã nguồn của Danh sách liên kết

[[Tập tin:Singly-linked-list.svg|nhỏ|385x385px|Danh sách liên kết là một chuỗi các nút chứa hai trường: giá trị số nguyên và liên kết đến nút tiếp theo. Nút cuối cùng được liên kết với một dấu chấm cuối được sử dụng để biểu thị sự kết thúc của danh sách.]]
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 (khoa học máy tính)|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.<ref>{{Chú thích web|url=https://www.geeksforgeeks.org/data-structures/linked-list/|tựa đề=Linked List Data Structure|website=GeeksforGeeks|ngôn ngữ=en-us|ngày truy cập=2022-11-12}}</ref> 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ấu trúc dữ liệu)|Mảng]] có [[Cache (tin học)|vùng đệm]] (cache locality) tốt hơn so với danh sách liên kết.<ref>{{Chú thích web|url=https://www.programiz.com/dsa/linked-list|tựa đề=Linked List Data Structure|website=www.programiz.com|ngày truy cập=2022-11-12}}</ref>

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.<ref name=":0">{{Chú thích|title=Linked list|date=2022-11-12|url=https://en.wikipedia.org/w/index.php?title=Linked_list&oldid=1121408648|work=Wikipedia|language=en|access-date=2022-11-12}}</ref>

Lợi ích chính của danh sách liên kết so với [[Mảng (cấu trúc dữ liệu)|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ữ [[wikt:contiguous|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.<ref name=":0" />

== 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.
[[Tập_tin:Singly-linked-list.svg|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;
 <nowiki>}</nowiki>
}}

=== 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.
[[Tập tin:Doubly-linked-list.svg|thế=Danh sách liên kết đôi.|giữa|nhỏ|573x573px|Danh sách liên kế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.
[[Tập tin:Circularly-linked-list.svg|thế=Danh sách liên kết vòng|giữa|nhỏ|379x379px|Danh sách liên kết vòng]]

== Tham khảo ==
{{tham khảo|30em}}

== Tài liệu tham khảo ==
*{{chú thích web |last=Juan |first=Angel |date=2006 |title=Ch20 –Data Structures; ID06 - PROGRAMMING with JAVA (slide part of the book 'Big Java', by CayS. Horstmann) |url=http://www.uoc.edu/in3/emath/docs/java/ch20.pdf |format=PDF |page=3 |ngày truy cập=2019-03-08 |archive-date = ngày 6 tháng 1 năm 2012 |archive-url=https://web.archive.org/web/20120106141608/http://www.uoc.edu/in3/emath/docs/java/ch20.pdf |url-status=dead }}
*{{chú thích web |last=Black |first=Paul E. |editor1-last=Pieterse |editor1-first=Vreda |editor2-last=Black |editor2-first=Paul E. |date = ngày 16 tháng 8 năm 2004 |title=linked list |work=Dictionary of Algorithms and Data Structures |publisher=[[National Institute of Standards and Technology]] |url=http://nist.gov/dads/HTML/linkedList.html |access-date = ngày 14 tháng 12 năm 2004}}
*{{chú thích sách |last1=Antonakos |first1=James L. |last2=Mansfield |first2=Kenneth C., Jr. |date=1999 |title=Practical Data Structures Using C/C++ |url=https://archive.org/details/practicaldatastr0000anto |publisher=Prentice-Hall |isbn=0-13-280843-9 |pages=[https://archive.org/details/practicaldatastr0000anto/page/165 165]–190}}
*{{chú thích sách |last=Collins |first=William J. |date=2005 |origyear=2002 |title=Data Structures and the Java Collections Framework |publisher=McGraw Hill |location=New York |isbn=0-07-282379-8 |pages=239–303}}
*{{chú thích sách |last1=Cormen |first1=Thomas H. |authorlink1=Thomas H. Cormen |last2=Leiserson |first2=Charles E. |authorlink2=Charles E. Leiserson |last3=Rivest |first3=Ronald L. |authorlink3=Ronald L. Rivest |last4=Stein |first4=Clifford |authorlink4=Clifford Stein |date=2003 |title=Introduction to Algorithms |publisher=MIT Press |isbn=0-262-03293-7 |pages=205–213, 501–505}}
*{{chú thích sách |last1=Cormen |first1=Thomas H. |authorlink1=Thomas H. Cormen |last2=Leiserson |first2=Charles E. |authorlink2=Charles E. Leiserson |last3=Rivest |first3=Ronald L. |authorlink3=Ronald L. Rivest |last4=Stein |first4=Clifford |authorlink4=Clifford Stein |date=2001 |title=[[Introduction to Algorithms]] |edition=2nd |chapter=10.2: Linked lists |publisher=MIT Press |isbn=0-262-03293-7 |pages=[https://archive.org/details/bwb_P9-BJD-587/page/204 204]–209}}
*{{chú thích tạp chí |last=Green |first=Bert F., Jr. |date=1961 |title=Computer Languages for Symbol Manipulation |journal=IRE Transactions on Human Factors in Electronics |issue=2 |doi=10.1109/THFE2.1961.4503292 |pages=3–8}}
*{{chú thích tạp chí |last=McCarthy |first=John |authorlink=John McCarthy (computer scientist) |date=1960 |title=Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I |journal=[[Communications of the ACM]] |url=http://www-formal.stanford.edu/jmc/recursive.html |doi=10.1145/367177.367199 |volume=3 |issue=4 |page=184}}
*{{chú thích sách |last=Knuth |first=Donald |authorlink=Donald Knuth |date=1997 |title=Fundamental Algorithms |edition=3rd |chapter=2.2.3-2.2.5 |publisher=Addison-Wesley |isbn=0-201-89683-4 |pages=254–298}}
*{{chú thích tạp chí |last1=Newell |first1=Allen |authorlink1=Allen Newell |last2=Shaw |first2=F. C. |date=1957 |title=Programming the Logic Theory Machine |journal=Proceedings of the Western Joint Computer Conference |pages=230–240}}
*{{chú thích web |last=Parlante |first=Nick |date=2001 |title=Linked list basics |publisher=Stanford University |url=http://cslibrary.stanford.edu/103/LinkedListBasics.pdf |format=PDF |access-date = ngày 21 tháng 9 năm 2009}}
*{{chú thích sách |last=Sedgewick |first=Robert |authorlink=Robert Sedgewick (computer scientist) |date=1998 |title=Algorithms in C |url=https://archive.org/details/isbn_0201350882 |publisher=Addison Wesley |isbn=0-201-31452-5 |pages=[https://archive.org/details/isbn_0201350882/page/n89 90]–109}}
*{{chú thích sách |last=Shaffer |first=Clifford A. |date=1998 |title=A Practical Introduction to Data Structures and Algorithm Analysis |url=https://archive.org/details/practicalintrodu0000shaf_y4u1 |publisher=Prentice Hall |location=New Jersey |isbn=0-13-660911-2 |pages=[https://archive.org/details/practicalintrodu0000shaf_y4u1/page/77 77]–102}}
*{{chú thích tạp chí |last=Wilkes |first=Maurice Vincent |authorlink=Maurice Vincent Wilkes |date=1964 |title=An Experiment with a Self-compiling Compiler for a Simple List-Processing Language |journal=Annual Review in Automatic Programming |publisher=Pergamon Press |volume=4 |issue=1 |doi=10.1016/0066-4138(64)90013-8 |page=1}}
*{{chú thích tạp chí |last=Wilkes |first=Maurice Vincent |authorlink=Maurice Vincent Wilkes |date=1964 |title=Lists and Why They are Useful |journal=Proceeds of the ACM National Conference, Philadelphia 1964 |publisher=ACM |issue=P–64 |pages=F1–1}}
*{{chú thích web |last=Shanmugasundaram |first=Kulesh |date=ngày 4 tháng 4 năm 2005 |title=Linux Kernel Linked List Explained |url=http://isis.poly.edu/kulesh/stuff/src/klist/ |access-date=ngày 21 tháng 9 năm 2009 |archive-date=2009-09-25 |archive-url=https://web.archive.org/web/20090925130610/http://isis.poly.edu/kulesh/stuff/src/klist/ |url-status=dead }}

==Liên kết ngoài==
{{Thể loại Commons|Linked lists}}
*[http://nist.gov/dads/HTML/linkedList.html Description] from the [[Dictionary of Algorithms and Data Structures]]
*[http://cslibrary.stanford.edu/103/ Introduction to Linked Lists], Stanford University Computer Science Library
*[http://cslibrary.stanford.edu/105/ Linked List Problems], Stanford University Computer Science Library
*[http://opendatastructures.org/versions/edition-0.1g/ods-python/3_Linked_Lists.html Open Data Structures - Chapter 3 - Linked Lists]
*[http://www.google.com/patents?vid=USPAT7028023 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)

{{Cấu trúc dữ liệu}}

{{Authority control}}

{{DEFAULTSORT:Danh sách liên kết}}
[[Thể loại:Danh sách liên kết|*]]