Xem mẫu
TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THÀNH PHỐ HỒ CHÍ MINH
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
Dẫn nhập
Mảng (array)
Danh sách liên kết (linked list)
2
Kích thước khó thay đổi
Cần cấp phát trước một vùng nhớ liên tục
Mất nhiều thao tác để chèn/xoá phần tử
Phù hợp với dữ liệu nhỏ, truy xuất nhanh
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
Cấu trúc dữ liệu và giải thuật - DSLK
Linked list – Khái niệm
Dã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
data
next
data
next
data
next
tail
head
NULL
3
Cấu trúc dữ liệu và giải thuật - DSLK
Các loại danh sách liên kết
Danh sách liên kết đơn (Singly linked list)
data
next
data
next
data
next
tail
head
NULL
Danh sách liên kết đôi/kép (Doubly linked list)
prev
data
next
prev
data
next
prev
data
next
tail
head
NULL
NULL
Danh sách liên kết vòng (Circular linked list)
data
next
data
next
head
4
Cấu trúc dữ liệu và giải thuật - DSLK
data
next
Mộ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
5
Lị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 động
Cấu trúc dữ liệu và giải thuật - DSLK
nguon tai.lieu . vn
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
Dẫn nhập
Mảng (array)
Danh sách liên kết (linked list)
2
Kích thước khó thay đổi
Cần cấp phát trước một vùng nhớ liên tục
Mất nhiều thao tác để chèn/xoá phần tử
Phù hợp với dữ liệu nhỏ, truy xuất nhanh
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
Cấu trúc dữ liệu và giải thuật - DSLK
Linked list – Khái niệm
Dã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
data
next
data
next
data
next
tail
head
NULL
3
Cấu trúc dữ liệu và giải thuật - DSLK
Các loại danh sách liên kết
Danh sách liên kết đơn (Singly linked list)
data
next
data
next
data
next
tail
head
NULL
Danh sách liên kết đôi/kép (Doubly linked list)
prev
data
next
prev
data
next
prev
data
next
tail
head
NULL
NULL
Danh sách liên kết vòng (Circular linked list)
data
next
data
next
head
4
Cấu trúc dữ liệu và giải thuật - DSLK
data
next
Mộ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
5
Lị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 động
Cấu trúc dữ liệu và giải thuật - DSLK