Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3 - ThS. Nguyễn Hà Giang

Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Danh sách liên kết - Linked list. Chương 3 gồm có những nội dung chính sau: Danh sách liên kết đơn, danh sách vòng, danh sách liên kết kép. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3 - ThS. Nguyễn Hà GiangDanh Sách Liên Kết - Linked ListThS. Nguyễn Hà GiangKhoa CNTT - HutechNội dungDanh sách liên kết đơnGiới thiệuCài đặtThao tácỨng dụngDanh sách vòngDanh sách liên kết kép2Nguyen Ha Giang - 2008Singly Linked List - Giới thiệuMảng 1 chiềuKích thước cố định (fixed size)Chèn 1 phần tử vào mảng rất khóCác phần tử tuần tự theo chỉ số 0  n-1Truy cập ngẫu nhiên (random access)chèn012343n-2n-1Nguyen Ha Giang - 2008Singly Linked List - Giới thiệuDanh sách liên kếtCấp phát động lúc chạy chương trìnhCác phần tử nằm rải rác ở nhiều nơi trong bộ nhớKích thước danh sách chỉ bị giới hạn do RAMThao tác thêm xoá đơn giảnInsert,Delete4Nguyen Ha Giang - 2008Singly Linked List - định nghĩaDSLK đơn là chuỗi các node, được tổ chức theo thứ tựtuyến tínhMỗi node gồm 2 phần:Phần Data, informationPhần link hay con trỏ trỏ đến node kế tiếpDataLinkNode5Nguyen Ha Giang - 2008