Cơ bản về cấu trúc dữ liệu và giải thuật - Danh sách P2
Ở phần này. Mình sẽ hướng dẫn cài đặt 1 số phương thức trên danh sách liên kết. Đó là:
Insertion (thêm) và Deletion(xóa)
Đối với các thư viện dựng sẵn, tất nhiên bạn không cần phải cài đặt mà có thể sử dụng các API có sẵn. Mục đích của bài viết là để các bạn có thể nắm đc cách hoạt động cơ bản của các API đó.
Đối với mảng, việc thêm hay xóa một phần tử nằm ở giữa của mảng tốn rất nhiều tài nguyên và thời gian.
Ví dụ:
Ở đoạn code trên, ta thấy có 1 số vấn đề sau:
- Đầu tiên cần cung cấp 1 vùng nhớ nhất định cho mảng. Điều này có thể khiến chương trình có thể cấp phát thừa hoặc thiếu
- Cần phải gán lại các phần tử phía sau phần tử được thêm hay xóa. Điều này khiến chương trình mất khá nhiều thời gian và tài nguyên
Trong khi đó, đối với danh sách liên kết, việc này trở nên khá đơn giản.
Ở phần trước, có giới thiệu cấu trúc của 1 phần tử trong dách sách liên kết( ở đây tạm dùng danh sách liên kết đơn)
Ta định nghĩa cấu trúc đó là một kiểu con trỏ: PointerType
Khi đó việc thêm một phần tử được biểu diễn theo sơ đồ sau:
Tương tự với hàm xóa:
Trên đây là 2 cài đặt cơ bản nhất với 1 danh sách liên kết. Ở phần tiếp theo mình sẽ hướng dẫn thêm 1 số cài đặt khác