Danh Sach Lien Ket

Định nghĩa:
  Trong khoa học máy tính , một danh sách liên kết là một cấu trúc dữ liệu bao gồm một nhóm các nút với nhau đại diện cho một chuỗi. Dưới hình thức đơn giản, mỗi nút bao gồm dữ liệu và  một liên kết đến nút tiếp theo trong chuỗi các biến thể phức tạp thêm các liên kết bổ sung. Cấu trúc này cho phép chèn hoặc loại bỏ có hiệu quả các yếu tố từ bất kỳ vị trí theo thứ tự.

  Danh sách liên kết là một trong những đơn giản và cấu trúc dữ liệu phổ biến nhất. Chúng có thể được sử dụng để thực hiện một số khác phổ biến dữ liệu trừu tượng các loại , bao gồm cả ngăn xếp , hàng đợi , mảng kết hợp , và các biểu thức tượng trưng , mặc dù nó không phải là phổ biến để thực hiện các cấu trúc dữ liệu khác trực tiếp mà không cần sử dụng một danh sách các cơ sở thực hiện.

  Lợi ích chủ yếu của một danh sách liên kết trong một thông thường mảng là danh sách các yếu tố có thể dễ dàng thêm vào hoặc gỡ bỏ mà không tái phân bổ, tổ chức lại toàn bộ cấu trúc bởi vì các mục dữ liệu không cần phải được lưu trữ liên tục kế nhau trong bộ nhớ hoặc trên đĩa. Danh sách liên kết cho phép chèn và loại bỏ các nút tại bất kỳ điểm nào trong danh sách, và có thể làm như vậy với một số liên tục hoạt động nếu liên kết trước đó để liên kết được thêm vào hoặc gỡ bỏ được duy trì trong danh sách traversal.

Mặt khác, danh sách đơn giản liên kết tự không cho phép truy cập ngẫu nhiên các dữ liệu, hoặc bất kỳ hình thức lập chỉ mục hiệu quả. Vì vậy, nhiều hoạt động cơ bản - như có nút cuối cùng của danh sách (giả định rằng các nút cuối cùng không được duy trì như là tài liệu tham khảo nút riêng biệt trong cấu trúc danh sách), hoặc tìm kiếm một nút có chứa những mốc nhất định, hoặc vị trí nơi mà một nút mới cần được đưa vào có thể yêu cầu quét hầu hết hoặc tất cả danh sách các yếu tố.

Danh sách liên kết được xây dựng năm 1955-1956 bởi Allen Newell , Cliff Shaw và Herbert A. Simon tại RAND Corporation cấu trúc dữ liệu chính cho xử lý ngôn ngữ Thông tin . IPL được sử dụng bởi các tác giả để phát triển trí thông minh nhân tạo một số đầu chương trình, bao gồm cả máy Lý thuyết Logic, Giải quyết vấn đề chung , và cờ tướng máy tính một chương trình. Báo cáo về công việc của họ xuất hiện trong giao dịch IRE thông tin Lý thuyết vào năm 1956, và một số biên bản hội nghị từ 1957 đến 1959, bao gồm Kỷ yếu của Hội nghị máy tính phương Tây chung vào năm 1957 và 1958, và xử lý thông tin (Kỷ yếu đầu tiên UNESCO Hội nghị quốc tế về xử lý thông tin ) vào năm 1959. Sơ đồ cổ điển hiện nay bao gồm các khối đại diện cho các nút danh sách với các mũi tên trỏ đến các nút trong danh sách, xuất hiện trong "Lập trình máy Lý thuyết Logic" của Newell và Shaw trong Proc. WJCC, tháng 2 năm 1957. Newell và Simon đã được công nhận với giải thưởng ACM Turing năm 1975 đã có những đóng góp cơ bản vào trí thông minh nhân tạo, tâm lý của sự nhận thức của con người, và xử lý danh sách ". Các vấn đề của máy dịch thuật ngôn ngữ tự nhiên xử lý đã dẫn Victor Yngve tại Viện Công nghệ Massachusetts (MIT) để sử dụng danh sách liên kết cấu trúc dữ liệu trong ngôn ngữ lập trình COMIT của mình cho nghiên cứu máy tính trong lĩnh vực ngôn ngữ học . Một báo cáo về ngôn ngữ này mang tên "Một ngôn ngữ lập trình cho dịch cơ học" xuất hiện trong dịch cơ khí vào năm 1958.

LISP , đứng cho bộ xử lý danh sách, được tạo ra bởi John McCarthy vào năm 1958 trong khi ông tại MIT và vào năm 1960, ông xuất bản thiết kế của nó trong một bài báo trong truyền thông của ACM , mang tên "đệ quy Chức năng của biểu thức tượng trưng và tính toán của họ bằng máy, phần I ". Một trong những cấu trúc dữ liệu lớn của LISP là danh sách liên kết. Đầu những năm 1960, các tiện ích của cả hai danh sách liên kết và ngôn ngữ sử dụng các cấu trúc dữ liệu chính như đại diện của họ cũng được thành lập. Bert xanh của Phòng thí nghiệm Lincoln MIT xuất bản một bài báo mang tên "ngôn ngữ máy tính cho các thao tác biểu tượng" trong giao dịch IRE trên yếu tố con người trong Điện tử tháng 3 năm 1961 trong đó tóm tắt những lợi thế của phương pháp tiếp cận danh sách liên kết. Một bài báo sau đó, "So sánh các ngôn ngữ máy tính xử lý danh sách" Bobrow và Raphael, xuất hiện trong Truyền thông của ACM vào tháng Tư năm 1964.

Một số hệ điều hành được phát triển bởi các hệ thống tư vấn kỹ thuật (ban đầu của West Lafayette Indiana, và sau đó Chapel Hill, Bắc Carolina) đã sử dụng danh sách đơn lẻ liên kết như các cấu trúc tập tin. Một mục nhập thư mục chỉ cho khu vực đầu tiên của một tập tin, và một phần thành công của tập tin được đặt con trỏ đi qua. Hệ thống sử dụng kỹ thuật này bao gồm Flex ( 6800 Motorola CPU), mini-Flex (cùng CPU), và Flex9 (cho Motorola 6809 CPU). Một biến thể được phát triển bởi TSC và tiếp thị bởi khói tín hiệu phát thanh truyền hình tại California, đã sử dụng danh sách liên kết kép trong cùng một cách thức.

  TSS/360 điều hành hệ thống, phát triển bởi IBM cho hệ thống 360/370 máy, sử dụng một danh sách liên kết đôi cho danh mục hệ thống tập tin của họ. Cấu trúc thư mục tương tự như Unix, một thư mục có thể chứa các tập tin và / hoặc thư mục khác và mở rộng đến chiều sâu nào. Một trời tiện ích được tạo ra để sửa chữa vấn đề hệ thống tập tin sau khi một tai nạn, kể từ khi phần sửa đổi của các cửa hàng của tập tin đôi khi trong bộ nhớ khi một vụ tai nạn xảy ra. Vấn đề đã được phát hiện bằng cách so sánh những liên kết về phía trước và lạc hậu nhất quán. Nếu một liên kết chuyển tiếp là tham nhũng, sau đó nếu một liên kết ngược trở lại, các nút bị nhiễm bệnh đã được tìm thấy, liên kết chuyển tiếp được thiết lập để các nút với các liên kết ngược. Một bình luận hài hước trong mã nguồn mà tiện ích này được gọi nói "Mọi người đều biết một cổ áo trời được thoát khỏi lỗi ở mèo".

  Khái niệm về một danh sách liên kết có thể được giải thích bằng một phép loại suy đơn giản để hộp bưu điện thế giới thực . Giả sử Alice là một gián điệp người muốn cung cấp cho một codebook cho Bob bằng cách đặt nó trong một hộp bưu điện và sau đó cho anh ta chìa khóa. Tuy nhiên, cuốn sách là quá dày để phù hợp với một hộp văn phòng bài duy nhất, do đó, thay vì chia cuốn sách thành hai nửa và mua hai hộp văn phòng bài. Trong ô đầu tiên, bà đặt một nửa đầu tiên của cuốn sách và một chìa khóa để vào ô thứ hai, và trong hộp thứ hai, cô đặt một nửa thứ hai của cuốn sách. Bà ta đưa cho Bob một chìa khóa để các hộp đầu tiên. Không có vấn đề lớn của cuốn sách, chương trình này có thể được mở rộng cho bất kỳ số lượng các hộp bằng cách luôn luôn đặt chìa khóa vào hộp tiếp theo trong hộp trước.

Trong tương tự này, các ô tương ứng với các yếu tố hoặc các nút, các phím tương ứng để con trỏ, và chính cuốn sách là các dữ liệu. Chìa khóa cho Bob là con trỏ đầu, trong khi những người được lưu trữ trong các hộp là con trỏ tiếp theo. Đề án như mô tả ở trên là một danh sách đơn lẻ liên kết (xem dưới đây). 

Các lọai DSLK:
 Danh sách vòng tròn :Trong các nút cuối cùng của một danh sách, các lĩnh vực liên kết thường có chứa một tham chiếu null, một giá trị đặc biệt được sử dụng để chỉ ra thiếu các nút tiếp tục. Một quy ước ít phổ biến hơn là để làm cho nó trỏ đến nút đầu tiên của danh sách, trong trường hợp đó, danh sách được cho là tròn hoặc tròn liên kết, nếu không nó được cho là cởi mở hay tuyến tính.

 Danh sách liên kết đơn: Danh sách đơn lẻ liên kết có chứa các nút có một trường dữ liệu cũng như các lĩnh vực tiếp theo, mà chỉ vào nút tiếp theo trong danh sách liên kết.

 Danh sách liên kết kép : trong một danh sách liên kết kép , mỗi nút chứa, bên cạnh các liên kết nút tiếp theo, một  liên kết thứ hai trỏ đến nút trước đó trong chuỗi. Hai liên kết có thể được gọi là phía trước (s) và sau, hoặc tiếp theo và trước (ious).