Trước khi tìm hiểu danh sách liên kết, chúng ta hãy tìm hiểu về nhược điểm của mảng và ưu điểm của con trỏ trong ngôn ngữ lập trình C.
Nhược điểm của Mảng
-
Nó bao gồm cấp phát bộ nhớ tĩnh
-
Sự lãng phí bộ nhớ có thể xảy ra trong các mảng.
-
Bộ nhớ kém hiệu quả là một trong những nhược điểm quan trọng của mảng.
Ưu điểm của con trỏ
- Nó bao gồm cấp phát bộ nhớ động.
- Có thể trải nghiệm việc sử dụng bộ nhớ hiệu quả trong con trỏ.
Danh sách được Liên kết
Danh sách được liên kết sử dụng phân bổ bộ nhớ động, tức là chúng phát triển và thu nhỏ tương ứng. Chúng được định nghĩa là một tập hợp các nút. Ở đây, các nút có hai phần, đó là dữ liệu và liên kết. Trình bày dữ liệu, liên kết và danh sách được liên kết được đưa ra dưới đây -
Các loại danh sách được liên kết
Danh sách được liên kết có bốn loại, như sau -
- Danh sách được liên kết đơn / lẻ
- Danh sách được liên kết đôi / liên kết đôi
- Danh sách liên kết đơn hình tròn
- Danh sách liên kết kép hình tròn
Danh sách liên kết đơn
Tham khảo cách trình bày dưới đây -
Nút bao gồm hai phần như sau -
- Dữ liệu
- Liên kết
Trường liên kết luôn trỏ đến nút tiếp theo trong danh sách.
Trường liên kết của nút cuối cùng là rỗng.
Danh sách liên kết đôi
Tham khảo cách trình bày dưới đây -
Nút bao gồm ba phần cụ thể là
- Phần dữ liệu
- Liên kết trái
- Liên kết bên phải
Liên kết bên trái luôn trỏ đến nút bên trái trong danh sách và liên kết bên phải luôn trỏ đến nút bên phải trong danh sách.
Liên kết bên trái của nút đầu tiên và liên kết bên phải của nút cuối cùng phải là Null.
Danh sách liên kết đơn hình tròn
Tham khảo cách trình bày dưới đây -
Nút bao gồm hai phần, đó là
- Phần dữ liệu
- Liên kết phần
Trường liên kết luôn trỏ đến nút tiếp theo trong danh sách.
Phần liên kết của nút cuối cùng luôn trỏ đến nút đầu tiên.
Danh sách liên kết kép hình tròn
Tham khảo cách trình bày dưới đây -
Nút bao gồm ba phần, đó là
- Phần dữ liệu
- Liên kết trái
- Liên kết bên phải
Liên kết trái luôn trỏ đến nút bên trái trong danh sách và liên kết bên phải trỏ đến nút bên phải trong danh sách.
Liên kết trái của nút đầu tiên trỏ đến nút cuối cùng và liên kết phải của nút cuối cùng trỏ đến nút đầu tiên.