14. Khái niệm danh sách liên kết ? Cho ví dụ minh hoạ ?

            Danh sách ngăn xếp stacj và hàng đợi Queue cần 1 không gian nhớ đủ lớ để chứa toàn bộ dữ liệu. trong trường hợp các miền không gian nhớ nằm rải rác khắp nơi tuy vẫn đủ chứa toàn bộ dữ liệu nhưng không liên tực nhau thì bài toán cũng không giải được. vì thế người ta xuất hiện ý tưởng trong trường hợp này sẽ liên kết các vùng dữ liệu để chứa được trong các miền ô nhớ rải rác gọi là phương pháp sưu tàm chỗ bị thải.

            Theo p2 này không nhất thiết các miền không gian nhớ phải đủ lớn và nằm cùng 1 vị trí mà chỉ cần bộ nhớ đủ chứa dữ liệu và nằm ở bất kì chỗ nào trong không gian nhớ cũng được.

            Với ý tưởng như vậy, người ta tổ chức 1 kiểu chứa dữ liệu đặc biệt gọi là danh sách liên kết. mỗi danh sách như vậy bao gồm nhiều thành phần gọi là các node.mỗi node và danh sách có cầu trúc gồm 2 phần:

                        Phần 1: dữ liệu của node (Data)

                        Phần 2 : địa chỉ của node sau ( trường liên kết)

                        Người ta dùng 1 con trỏ L để chỉ đầu vào của danh sách liên kết. với cấu trúc như vậy đầu vào của danh sách liên kết về mặt logic và vật lí là không đồng nhất.

            VD: so sánh DS đặc và ds liên kết

            DS đặc             stt         tên        nghề nghiệp

                                    1          ngọc     sinh viên

                                    2          mai       bác sĩ

                                    3          hùng     bảo vệ

                                    4          linh       kế toán

            Ds lket             stt         tên        nghề nghiệp      next

                 L  =>          1          ngọc     sinh viên           4

                                    2          mai       bác sĩ               0

                                    3          hùng     bảo vệ              2

                                    4          linh       kế toán             3

            Qua ví dụ trên ta thấy việc tổ chức dữ liệu ds lk trở nên cơ động hơn vì không hoàn toàn phụ thuộc vào các miền không gian nhớ phải liên tiếp nhau, có nghĩa là chỉ cần có không gian nhớ là được, chúng có thể ở bất kì vị trí nào trong bộ nhớ/

            Với cấu trúc tổ chức như vậy, dslk rất thuận tiện cho các phép toán bổ sung và loại bỏ bởi vì chúng ta không cần dọn chỗ để chứa các tp bổ sung hoặc dồn các tp của ds khi loại bỏ. để bổ sung chúng ta chỉ cần chọn 1 vị trí tự do bất kì nào đó trong danh sách để chứa phần tử bổ sung và sau đó chỉnh sửa trường liên kết của phần tử đứng trước nó. Quá trình loại bỏ chúng ta không cần dịch chuyển không gian nhớ như ds đặc mà chỉ cần chỉnh con trỏ của phần tử đứng trước nó mà thôi.