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

TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THÀNH PHỐ HỒ CHÍ MINH<br /> <br /> Cấu trúc dữ liệu và giải thuật<br /> Danh sách liên kết<br /> TS. Ngô Hữu Dũng<br /> <br /> Dẫn nhập<br /> <br /> <br /> Mảng (array)<br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> Danh sách liên kết (linked list)<br /> <br /> <br /> <br /> <br /> <br /> 2<br /> <br /> Kích thước khó thay đổi<br /> Cần cấp phát trước một vùng nhớ liên tục<br /> Mất nhiều thao tác để chèn/xoá phần tử<br /> Phù hợp với dữ liệu nhỏ, truy xuất nhanh<br /> Kích thước thay đổi linh động<br /> Cấp phát bộ nhớ động, không cần vùng nhớ liên tục<br /> Chèn/xoá dễ dàng<br /> Cho phép dữ liệu lớn hơn, cấu trúc linh hoạt<br /> Cấu trúc dữ liệu và giải thuật - DSLK<br /> <br /> Linked list – Khái niệm<br /> Dãy phần tử nối với nhau bởi con trỏ (pointer)<br />  Mỗi phần tử là một nút (node)<br /> <br /> <br /> <br /> <br /> <br /> Phần dữ liệu (int, float, char, struct…)<br /> Phần liên kết (pointer)<br /> <br /> Con trỏ head trỏ vào nút đầu tiên<br />  Con trỏ tail trỏ vào nút cuối cùng<br />  Nút cuối cùng trỏ vào NULL<br /> <br /> <br /> data<br /> <br /> next<br /> <br /> data<br /> <br /> next<br /> <br /> data<br /> <br /> next<br /> tail<br /> <br /> head<br /> NULL<br /> 3<br /> <br /> Cấu trúc dữ liệu và giải thuật - DSLK<br /> <br /> Các loại danh sách liên kết<br /> Danh sách liên kết đơn (Singly linked list)<br /> <br /> <br /> <br /> data<br /> <br /> next<br /> <br /> data<br /> <br /> next<br /> <br /> data<br /> <br /> next<br /> tail<br /> <br /> head<br /> NULL<br /> <br /> <br /> <br /> Danh sách liên kết đôi/kép (Doubly linked list)<br /> prev<br /> <br /> data<br /> <br /> next<br /> <br /> prev<br /> <br /> data<br /> <br /> next<br /> <br /> prev<br /> <br /> data<br /> <br /> next<br /> tail<br /> <br /> head<br /> NULL<br /> <br /> <br /> <br /> NULL<br /> <br /> Danh sách liên kết vòng (Circular linked list)<br /> data<br /> <br /> next<br /> <br /> data<br /> <br /> next<br /> <br /> head<br /> <br /> 4<br /> <br /> Cấu trúc dữ liệu và giải thuật - DSLK<br /> <br /> data<br /> <br /> next<br /> <br /> Một vài ứng dụng<br /> <br /> <br /> Tổ chức các cấu trúc dữ liệu khác nhau<br /> <br /> <br /> <br /> <br /> Lưu dấu<br /> <br /> <br /> <br /> <br /> <br /> Bộ nhớ, tiến trình, tập tin…<br /> <br /> Phù hợp với các ứng dụng<br /> <br /> <br /> 5<br /> <br /> Lịch sử truy cập web (history)<br /> Lưu các tác vụ (undo)<br /> <br /> Quản lý các thành phần trong máy tính<br /> <br /> <br /> <br /> <br /> Stack, queue, tree, graph, hash table…<br /> <br /> Dữ liệu lớn, cấu trúc linh động<br /> Cấu trúc dữ liệu và giải thuật - DSLK<br /> <br />