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

Danh sách link đơn(Single linked list) là ví dụ tốt nhất và dễ dàng độc nhất về cấu tạo dữ liệu hễ thực hiện con trỏ để thiết lập. Do đó, kỹ năng và kiến thức bé trỏ là khôn cùng đặc trưng nhằm đọc cách danh sách liên kết vận động, vày vậy nếu như bạn chưa tồn tại kiến thức về nhỏ trỏ thì chúng ta nên học về nhỏ trỏ trước. quý khách hàng cũng cần được hiểu một chút ít về cấp phát bộ lưu trữ cồn. Để đơn giản với dễ dàng nắm bắt, phần nội dung thiết đặt list link của nội dung bài viết này sẽ chỉ trình bày về danh sách link đơ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 list liên kết3.4. Xóa Node ngoài danh sách liên kết3.8. Một số hàm hỗ trợ khác

1. Lý tngày tiết về list liên kết

Về bản chất, danh sách liên kết gồm tác dụng như một mảng, có thể thêm với xóa những bộ phận nghỉ ngơi bất kỳ địa điểm nào Khi quan trọng. Một số sự không giống nhau giữa danh sách link và mảng:

Nội dungMảngDanh sách liên kết
Kích thướcKích thước chũm địnhCần chỉ rõ form size trong lúc knhị báoKích thước đổi khác vào quá trình thêm/ xóa phần tửKích thước tối nhiều nhờ vào vào bộ nhớ
Cấp vạc bộ nhớTĩnh: Sở lưu giữ được cấp phép vào quy trình biên dịchĐộng: Sở lưu giữ được cấp phát trong quá trình chạy
Thứ tự & sắp xếpĐược lưu trữ bên trên một dãy ô nhớ liên tụcĐược lưu trữ trên các ô lưu giữ ngẫu nhiên
Truy cậpTruy cùa đến bộ phận đột nhiên thẳng bằng cách thực hiện chỉ số mảng: O(1)Truy cùa đến bộ phận thốt nhiên rất cần phải coi ngó trường đoản cú đầu/cuối mang đến bộ phận đó: O(n)
Tìm kiếmTìm tìm con đường tính hoặc tìm kiếm tìm nhị phânChỉ hoàn toàn có thể kiếm tìm tìm tuyến đường tính

Lưu ý: Tại bảng bên trên, những phần in nghiêng biểu thị chính là điểm mạnh so với đối phương sót lại.

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

Danh sách link đơn là một tập thích hợp những Node được phân bổ hễ, được thu xếp theo cách sao cho từng Node cất “một giá trị”(Data) và “một nhỏ trỏ”(Next). Con trỏ vẫn trỏ mang đến bộ phận kế tiếp của danh sách links kia. Nếu bé trỏ mà trỏ tới NULL, tức thị sẽ là phần tử sau cùng của linked các mục.

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

Tấm hình trình bày cho một Node vào list link đơn:

*
*
*
Mô rộp của danh sách link đơn

Danh sách các dạng hình list liên kết:

Danh sách links đơn(Single linked list): Chỉ gồm sự kết nối tự thành phần vùng trước tới phần tử vùng phía đằng sau.Danh sách link đôi(Double linked list): Có sự kết nối 2 chiều thân thành phần vùng phía đằng trước với phần tử phía sauDanh sách links vòng(Circular Linked List): Có thêm sự liên kết thân 2 thành phần thứ nhất và bộ phận cuối cùng để tạo nên thành vòng khxay kín đáo.

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

3.1. Knhị báo linked list

Để dễ dàng hóa, data của chúng ta đang là số nguyên(int). Quý khách hàng cũng rất có thể sử dụng những hình dáng nguyên thủy khác(float, char,…) hay giao diện tài liệu struct(SinhVien, CanBo,…) trường đoản cú sản xuất.