Danh Sách Liên Kết – Wikipedia Tiếng Việt

Bài viết này có một danh sách các nguồn tham khảo, nhưng vẫn chưa đáp ứng khả năng kiểm chứng được bởi thân bài vẫn còn thiếu các chú thích trong hàng. Hãy giúp cải thiện bài viết này bằng cách bổ sung các chú thích nguồn cho các nội dung tương ứng. (March 2012) (Tìm hiểu cách thức và thời điểm xóa thông báo này)

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.[1] 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.[2]

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.[3]

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.[3]

Lịch sử

[sửa | sửa mã nguồn]

Xin hãy đóng góp cho bài viết này bằng cách phát triển nó. Nếu bài viết đã được phát triển, hãy gỡ bản mẫu này. Thông tin thêm có thể được tìm thấy tại trang thảo luận.

Khái niệm và thuật ngữ

[sửa | sửa mã nguồn]

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

[sửa | sửa mã nguồ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++:

nodeaddNode(nodehead,intvalue){     nodetemp,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     }     returnhead; }

Danh sách liên kết đôi

[sửa | sửa mã nguồn]

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

structNode{ intdata;// 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 đó }; typedefstructNodeNODE;

Danh sách liên kết nhân

[sửa | sửa mã nguồ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

[sửa | sửa mã nguồn]

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

[sửa | sửa mã nguồn]

1. ^ “Linked List Data Structure”. GeeksforGeeks (bằng tiếng Anh). Truy cập ngày 12 tháng 11 năm 2022.
2. ^ “Linked List Data Structure”. www.programiz.com. Truy cập ngày 12 tháng 11 năm 2022.
3. ^ a b “Linked list”, Wikipedia (bằng tiếng Anh), 12 tháng 11 năm 2022, truy cập ngày 12 tháng 11 năm 2022

Tài liệu tham khảo

[sửa | sửa mã nguồn]

• 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 thứ 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 thứ 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.

Liên kết ngoài

[sửa | sửa mã nguồn] Wikimedia Commons có thêm hình ảnh và phương tiện truyền tải về Danh sách liên kết.

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

x t s Cấu trúc dữ liệu
Kiểu	Collection · Container
Trừu tượng	Danh sách · Mảng kết hợp · Multimap · Set · Multiset · Double-ended queue · Hàng đợi · Hàng đợi ưu tiên · Ngăn xếp
Mảng	Mảng động · Sparse array · Circular buffer · Mảng bit · Bảng băm
Liên kết	Danh sách liên kết · Unrolled linked list · Danh sách liên kết XOR · Skip list
Cây	B-cây · Cây tìm kiếm nhị phân (tự cân bằng: AA, AVL, đỏ đen, splay) · Đống (nhị phân, nhị thức, Fibonacci) · Trie
Đồ thị	Directed graph · Directed acyclic graph · Sơ đồ quyết định nhị phân · Siêu đồ thị
Danh sách các cấu trúc dữ liệu

Tiêu đề chuẩn	GND: 4783888-7