Khác biệt giữa bản sửa đổi của “Danh sách liên kết”

n
clean up
(Add 2 books for Wikipedia:Thông tin kiểm chứng được (20210305)) #IABot (v2.0.8) (GreenC bot)
n (clean up)
Trong [[khoa học máy tính]], '''danh sách liên kết''' (tiếng Anh: ''linked list'') là một 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ý của chúng trong bộ nhớ. Thay vào đó, mỗi phần tử [[pointer (computer programming)|chỉ đế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 [[node (computer science)|nút]] cùng thể hiện một [[Dãy (toán học)|dãy]]. Ở dạng cơ bản nhất, mỗi nút chứa: [[Dữ liệu (máy tính)|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à ''liên kết'') tới nút kế tiếp trong dãy. 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 [[instruction pipelining|ố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ó [[locality of reference|vùng đệm]] (cache locality) tốt hơn so với danh sách liên kết.
 
<div class="center">[[FileTập tin:Singly-linked-list.svg]]<br><small>''Một danh sách liên kết có nút chứa 2 trường: một giá trị nguyên và một nút liên kết đến nút tiếp theo. Nút cuối cùng được liên kết với bộ kết thúc (terminator) để biểu thị phần cuối của danh sách.''</small></div>
 
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 (kiểu dữ liệu trừu tượng)|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.
Mặc khác, vì bản thân danh sách liên kết được liên kết đơn giản nên không cho phép [[truy cập ngẫu nhiên]] tới dữ liệu hoặc bất kì hình thức đánh chỉ mục hiệu quả nào, nhiều toán tử cơ bản như lấy nút cuối cùng của danh sách, tìm một nút có chứa dữ liệu đã cho, hay tìm vị trí của nút để chèn một nút mới sẽ yêu cầu lặp qua hầu hết hoặc tất cả các phần tử của danh sách. Những ưu điểm và nhược điểm của danh sách liên kết được đưa ra dưới đây. Danh sách liên kết là động, vì vậy độ dài của nó có thể tăng hay giảm khi cần thiết. Mỗi nút không cần phải theo nút trước đó trong bộ nhớ.
 
==Notes Ghi chú ==
{{reflisttham khảo|group=note}}
 
==Footnotes==
{{reflisttham khảo}}
 
==Tham khảo==
*{{citechú 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-01-06 |archive-url=https://web.archive.org/web/20120106141608/http://www.uoc.edu/in3/emath/docs/java/ch20.pdf |url-status=dead }}
*{{citechú thích web |last=Black |first=Paul E. |editor1-last=Pieterse |editor1-first=Vreda |editor2-last=Black |editor2-first=Paul E. |date =2004-08- 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 |accessdate=2004-12access-date = ngày 14 tháng 12 năm 2004}}
*{{citechú bookthí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}}
*{{citechú bookthí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}}
*{{citechú bookthí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}}
*{{citechú bookthí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/introductiontoal00corm_691/page/n226 204]–209}}
*{{cite journal |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}}
*{{cite journal |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}}
*{{citechú bookthí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}}
*{{cite journal |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}}
*{{citechú 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 |accessdate=2009-09access-date = ngày 21 tháng 9 năm 2009}}
*{{citechú bookthí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}}
*{{citechú bookthí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/practicalintrodu00shaf_419 |publisher=Prentice Hall |location=New Jersey |isbn=0-13-660911-2 |pages=[https://archive.org/details/practicalintrodu00shaf_419/page/77 77]–102}}
*{{cite journal |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}}
*{{cite journal |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}}
*{{citechú thích web |last=Shanmugasundaram |first=Kulesh |date = ngày 4 tháng 4 năm 2005-04-04 |title=Linux Kernel Linked List Explained |url=http://isis.poly.edu/kulesh/stuff/src/klist/ |accessdate=2009-09access-date = ngày 21 tháng 9 năm 2009}}
 
==Liên kết ngoài==
 
{{Cấu trúc dữ liệu}}
 
 
{{Authority control}}
 
{{DEFAULTSORT:Danh sách liên kết}}
[[CategoryThể loại:Danh sách liên kết|*]]