BÀI TẬP DANH SÁCH LIÊN KẾT ĐƠN CÓ LỜI GIẢI

Danh sách liên kết đơn(Single linked list) là ví dụ tốt nhất và đơn giản nhất về cấu trúc dữ liệu động sử dụng con trỏ để cài đặt. Do đó, kiến thức con trỏ là rất quan trọng để hiểu cách danh sách liên kết hoạt động, vì vậy nếu bạn chưa có kiến thức về con trỏ thì bạn nên học về con trỏ trước. Bạn cũng cần hiểu một chút về cấp phát bộ nhớ động. Để đơn giản và dễ hiểu, phần nội dung cài đặt danh sách liên kết của bài viết này sẽ chỉ trình bày về danh sách liên kết đơn.

Bạn đang xem: Bài tập danh sách liên kết đơn có lời giải


3. Cài đặt danh sách liên kết đơn3.3. Thêm Node vào danh sách liên kết3.4. Xóa Node khỏi danh sách liên kết3.8. Một số hàm bổ trợ khác

1. Lý thuyết về danh sách liên kết

Về bản chất, danh sách liên kết có chức năng như một mảng, có thể thêm và xóa các phần tử ở bất kỳ vị trí nào khi cần thiết. Một số sự khác nhau giữa danh sách liên kết và mảng:

Nội dungMảngDanh sách liên kết
Kích thướcKích thước cố địnhCần chỉ rõ kích thước trong khi khai báoKích thước thay đổi trong quá trình thêm/ xóa phần tửKích thước tối đa phụ thuộc vào bộ nhớ
Cấp phát bộ nhớTĩnh: Bộ nhớ được cấp phát trong quá trình biên dịchĐộng: Bộ nhớ được cấp phát trong quá trình chạy
Thứ tự & sắp xếpĐược lưu trữ trên một dãy ô nhớ liên tụcĐược lưu trữ trên các ô nhớ ngẫu nhiên
Truy cậpTruy cập tới phần tử ngẫu nhiên trực tiếp bằng cách sử dụng chỉ số mảng: O(1)Truy cập tới phần tử ngẫu nhiên cần phải duyệt từ đầu/cuối đến phần tử đó: O(n)
Tìm kiếmTìm kiếm tuyến tính hoặc tìm kiếm nhị phânChỉ có thể tìm kiếm tuyến tính

Lưu ý: Ở bảng phía trên, các phần in nghiêng thể hiện đó là ưu điểm so với đối thủ còn lại.

2. Danh sách liên kết là gì?

Danh sách liên kết đơn là một tập hợp các Node được phân bố động, được sắp xếp theo cách sao cho mỗi Node chứa “một giá trị”(Data) và “một con trỏ”(Next). Con trỏ sẽ trỏ đến phần tử kế tiếp của danh sách liên kết đó. Nếu con trỏ mà trỏ tới NULL, nghĩa là đó là phần tử cuối cùng của linked list.

Xem thêm: Cách Gieo Hạt Hoa Lan Bằng Phương Pháp Gieo Hạt, Hướng Dẫn Ươm Lan Con Từ Hạt

Hình ảnh mô tả cho một Node trong danh sách liên kết đơn:

*
*
*
Mô phỏng của danh sách liên kết đơn

Danh sách các kiểu danh sách liên kết:

Danh sách liên kết đơn(Single linked list): Chỉ có sự kết nối từ phần tử phía trước tới phần tử phía sau.Danh sách liên kết đôi(Double linked list): Có sự kết nối 2 chiều giữa phần tử phía trước với phần tử phía sauDanh sách liên kết vòng(Circular Linked List): Có thêm sự kết nối giữa 2 phần tử đầu tiên và phần tử cuối cùng để tạo thành vòng khép kín.

3. Cài đặt danh sách liên kết đơn

3.1. Khai báo linked list

Để đơn giản hóa, data của chúng ta sẽ là số nguyên(int). Bạn cũng có thể sử dụng các kiểu nguyên thủy khác(float, char,…) hay kiểu dữ liệu struct(SinhVien, CanBo,…) tự tạo.