Giảng viên: TS. Ngo Huu Phuc
Tel: 0438 326 077
Mob: 098 5696 580
Email: ngohuuphuc76@gmail.com
Cấu trúc dữ liệu và giải thuật
Bài 15. Danh sách liên kết
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
1Tháng 09 năm 2009
Bài 15: Danh sách liên kết
Nội dung:
15.1. Giới thiệu chung.
15.2. Danh sách liên kết đơn.
15.2.1. Khái niệm về danh sách liên kết đơn.
15.2.2. Các thao tác cơ bản của danh sách liên kết đơn.
15.3. Danh sách liên kết vòng.
15.3.1. Khái niệm về danh sách liên kết vòng.
15.3.2. Các thao tác cơ bản của danh sách liên kết vòng.
15.4. Danh sách liên kết kép.
15.4.1. Khái niệm về danh sách liên kết kép.
15.4.2. Các thao tác cơ bản của danh sách liên kết kép.
15.5. Một số ví dụ về danh sách liên kết.
Tham khảo:
1. Deshpande Kakde: C and Data structures.chm, Chapter 20: Linked Lists
2. Elliz Horowitz – Fundamentals of Data Structures.chm, Chapter 4: Linked Lists
3. Kyle Loudon: Mastering Algorithms with C.chm, Chapter 5 Linked Lists.
4. Bài giảng TS Nguyễn Nam Hồng
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
2Tháng 09 năm 2009
15.1. 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.
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
3Tháng 09 năm 2009
15.1. 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.
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
4Tháng 09 năm 2009
15.2. Danh sách liên kết đơn (1/23)
Trong rất nhiều trường hợp cần sử dụng đến danh sách liên kết
động, danh sách liên kết động cần dùng đến khi kích thước
danh sách chưa biết tại thời điểm biên dịch chương trình.
Khi đó, danh sách có thể mở rộng hoặc thu hẹp lại tại thời
điểm chạy chương trình.
Cấu trúc dữ liệu linked list sử dụng mô hình liên kết động.
Một số dạng của danh sách liên kết:
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.
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
5Tháng 09 năm 2009