Đáp án Câu hỏi 1 Bài 15. Cấu trúc dữ liệu danh sách liên kết và ứng dụng (trang 146) – SGK Tin học 11 Cánh diều. Gợi ý: Dựa vào kiến thức đã học.
Câu hỏi/Đề bài:
Hãy nêu các phép toán danh sách liên kết có thời gian thực hiện O(1)
Hướng dẫn:
Dựa vào kiến thức đã học.
Lời giải:
Phép toán danh sách liên kết là các thao tác trên các phần tử trong danh sách liên kết. Thời gian thực hiện của các phép toán này phụ thuộc vào cách triển khai danh sách liên kết và thường là O(1) hoặc O(n).
Các phép toán danh sách liên kết có thời gian thực hiện O(1) bao gồm:
– Truy cập phần tử đầu tiên (head) và phần tử cuối cùng (tail) của danh sách liên kết. Thao tác này được thực hiện bằng cách truy cập trực tiếp vào head hoặc tail của danh sách, không cần phải duyệt qua toàn bộ danh sách.
– Thêm phần tử vào đầu danh sách và cuối danh sách. Thao tác này được thực hiện bằng cách tạo một phần tử mới, gán con trỏ next của phần tử mới thành head hoặc tail của danh sách và cập nhật lại head hoặc tail.
– Xóa phần tử đầu danh sách và cuối danh sách. Thao tác này được thực hiện bằng cách giải phóng phần tử head hoặc tail của danh sách và cập nhật lại head hoặc tail.