Bài giảng Cấu trúc dữ liệu và giải thuật: Danh sách liên kết - TS. Ngô Hữu Dũng

Bài giảng Cấu trúc dữ liệu và giải thuật: Danh sách liên kết giới thiệu đến các bạn những nội dung về Kích thước thay đổi linh động, cấp phát bộ nhớ động, không cần vùng nhớ liên tục, chèn/xoá dễ dàng, cho phép dữ liệu lớn hơn, cấu trúc linh hoạt,...
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: Danh sách liên kết - TS. Ngô Hữu DũngTRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THÀNH PHỐ HỒ CHÍ MINHCấu trúc dữ liệu và giải thuậtDanh sách liên kếtTS. Ngô Hữu DũngDẫn nhậpMảng (array)Danh sách liên kết (linked list)2Kích thước khó thay đổiCần cấp phát trước một vùng nhớ liên tụcMất nhiều thao tác để chèn/xoá phần tửPhù hợp với dữ liệu nhỏ, truy xuất nhanhKích thước thay đổi linh độngCấp phát bộ nhớ động, không cần vùng nhớ liên tụcChèn/xoá dễ dàngCho phép dữ liệu lớn hơn, cấu trúc linh hoạtCấu trúc dữ liệu và giải thuật - DSLKLinked list – Khái niệmDãy phần tử nối với nhau bởi con trỏ (pointer) Mỗi phần tử là một nút (node)Phần dữ liệu (int, float, char, struct…)Phần liên kết (pointer)Con trỏ head trỏ vào nút đầu tiên Con trỏ tail trỏ vào nút cuối cùng Nút cuối cùng trỏ vào NULLdatanextdatanextdatanexttailheadNULL3Cấu trúc dữ liệu và giải thuật - DSLKCác loại danh sách liên kếtDanh sách liên kết đơn (Singly linked list)datanextdatanextdatanexttailheadNULLDanh sách liên kết đôi/kép (Doubly linked list)prevdatanextprevdatanextprevdatanexttailheadNULLNULLDanh sách liên kết vòng (Circular linked list)datanextdatanexthead4Cấu trúc dữ liệu và giải thuật - DSLKdatanextMột vài ứng dụngTổ chức các cấu trúc dữ liệu khác nhauLưu dấuBộ nhớ, tiến trình, tập tin…Phù hợp với các ứng dụng5Lịch sử truy cập web (history)Lưu các tác vụ (undo)Quản lý các thành phần trong máy tínhStack, queue, tree, graph, hash table…Dữ liệu lớn, cấu trúc linh độngCấu trúc dữ liệu và giải thuật - DSLK