"Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 15: Danh sách liên kết" trình bày giới thiệu chung, danh sách liên kết đơn, danh sách liên kết vòng, danh sách liên kết kép, một số ví dụ về danh sách liên kết. | Cấu trúc dữ liệu và giải thuật Bài 15. Danh sách liên kết Giảng viên TS. Ngo Huu Phuc Tel 0438 326 077 Mob 098 5696 580 Email ngohuuphuc76@ 1 @copyright by PhD Ngo Huu Phuc Le Quy Don Technical University Tháng 09 năm 2009 Bài 15 Danh sách liên kết Nội dung . Giới thiệu chung. . Danh sách liên kết đơn. . Khái niệm về danh sách liên kết đơn. . Các thao tác cơ bản của danh sách liên kết đơn. . Danh sách liên kết vòng. . Khái niệm về danh sách liên kết vòng. . Các thao tác cơ bản của danh sách liên kết vòng. . Danh sách liên kết kép. . Khái niệm về danh sách liên kết kép. . Các thao tác cơ bản của danh sách liên kết kép. . Một số ví dụ về danh sách liên kết. Tham khảo 1. Deshpande Kakde C and Data Chapter 20 Linked Lists 2. Elliz Horowitz Fundamentals of Data Chapter 4 Linked Lists 3. Kyle Loudon Mastering Algorithms with Chapter 5 Linked Lists. 4. Bài giảng TS Nguyễn Nam Hồng 2 @copyright by PhD Ngo Huu Phuc Le Quy Don Technical University Tháng 09 năm 2009 . Giới thiệu chung 1 2 Với CTDL dạng mảng bộ nhớ được sử dụng là một dãy liền kề và có kích thước cố định. Tuy nhiên CTDL này có m ột số nhược điểm Thời gian cho việc thêm hay bớt phần tử trong mảng khá lâu vì phải thay đổi cả các phần tử còn lại trong mảng. Ngay cả khi khai báo một lượng lớn các phần tử cho mảng để có thể áp dụng được cho nhiều bài toán chúng ta cũng thấy khả năng dư thừa bộ nhớ xuất hiện. 3 @copyright by PhD Ngo Huu Phuc Le Quy Don Technical University Tháng 09 năm 2009 . Giới thiệu chung 2 2 Để khắc phục nhược điểm trên có thể sử dụng danh sách liên kết như là cấu trúc dữ liệu thay thế. Trong cấu trúc này không cần xác định kích thước cho các phần tử trước. Ta có thể định nghĩa phần tử bất cứ lúc nào sau đó liên kết phần tử đó với danh sách đã có trước đó. Như vậy mỗi phần tử sẽ bao gồm thông tin cần lưu trữ và liên kết với các phần tử khác. 4 @copyright by PhD Ngo Huu Phuc Le Quy Don .
