Bạn đã bao giờ gặp trường hợp không biết trước số lượng phần tử cần lưu trữ trong chương trình C chưa? Hoặc bạn muốn thêm, xóa phần tử mà không cần dịch chuyển dữ liệu trong mảng?
💡 Danh sách liên kết (Linked List) chính là giải pháp hoàn hảo!
Trong bài viết này, chúng ta sẽ đi sâu vào danh sách liên kết trong C, từ khái niệm đến cách sử dụng, ưu nhược điểm, các loại danh sách liên kết và nhiều ví dụ thực tế giúp bạn hiểu sâu – làm chủ nó! 🚀
📌 1. Danh sách liên kết là gì?
🔹 Định nghĩa
Danh sách liên kết (Linked List) là một cấu trúc dữ liệu động, gồm nhiều nút (node) liên kết với nhau bằng con trỏ.
💡 Giải thích:
- Nút (Node) trong danh sách liên kết có thể chứa một phần tử dữ liệu và một con trỏ trỏ đến nút tiếp theo.
- Danh sách liên kết có thể được khai báo và sử dụng linh hoạt, không cần biết trước kích thước danh sách.
Mỗi nút chứa hai phần:
- Dữ liệu (data): Giá trị của phần tử trong danh sách.
- Con trỏ (pointer): Trỏ đến nút tiếp theo trong danh sách.
🔹 So sánh Danh sách liên kết và Mảng
| Tính năng | Mảng | Danh sách liên kết |
|---|---|---|
| Kích thước | Cố định | Linh hoạt |
| Truy xuất phần tử | Nhanh (O(1)) | Chậm (O(n)) |
| Chèn/Xóa phần tử | Tốn chi phí (O(n)) | Nhanh hơn (O(1) – nếu có con trỏ) |
| Dùng bộ nhớ | Có thể lãng phí | Tối ưu hơn |
💡 Giải thích:
- Mảng có kích thước cố định, trong khi danh sách liên kết cho phép mở rộng linh hoạt mà không phải dịch chuyển dữ liệu.
- Mảng hỗ trợ truy xuất nhanh qua chỉ số, trong khi danh sách liên kết phải duyệt từng phần tử.
🔥 2. Các loại danh sách liên kết trong C
Có nhiều loại danh sách liên kết, tùy vào cách chúng ta liên kết các phần tử:
🔹 Danh sách liên kết đơn (Singly Linked List)
- Mỗi nút chỉ chứa một con trỏ trỏ đến nút kế tiếp.
- Duyệt danh sách từ đầu đến cuối.
💡 Giải thích:
Danh sách liên kết đơn là dạng cơ bản nhất của danh sách liên kết. Mỗi nút chỉ trỏ đến phần tử kế tiếp, điều này giúp đơn giản hóa việc thao tác nhưng lại có nhược điểm khi cần duyệt ngược hoặc xóa phần tử giữa danh sách.
👉 Cấu trúc một nút:
struct Node {
int data; // Dữ liệu của nút
struct Node *next; // Con trỏ trỏ đến nút kế tiếp
};
👉 Ví dụ:
struct Node *head = NULL; // Khai báo danh sách rỗng
🔹 Danh sách liên kết đôi (Doubly Linked List)
- Mỗi nút chứa hai con trỏ:
- next trỏ đến nút kế tiếp.
- prev trỏ đến nút trước đó.
- Duyệt danh sách cả hai chiều.
💡 Giải thích:
Danh sách liên kết đôi cho phép bạn duyệt qua danh sách từ cả hai chiều (từ đầu đến cuối và ngược lại). Điều này giúp thao tác xóa phần tử giữa danh sách dễ dàng hơn.
👉 Cấu trúc một nút:
struct Node {
int data; // Dữ liệu của nút
struct Node *next; // Con trỏ trỏ đến nút kế tiếp
struct Node *prev; // Con trỏ trỏ đến nút trước đó
};
👉 Ưu điểm:
Dễ dàng duyệt ngược và xóa phần tử giữa danh sách.
🔹 Danh sách liên kết vòng (Circular Linked List)
- Nút cuối cùng trỏ ngược lại nút đầu tiên thay vì NULL.
- Giúp lặp vòng vô hạn, hữu ích trong hệ điều hành, bộ lập lịch…
💡 Giải thích:
Danh sách liên kết vòng giúp duy trì liên kết vòng lặp vô hạn, hữu ích cho các tác vụ lặp lại liên tục, ví dụ như trong lịch trình của hệ điều hành.
👉 Ví dụ:
head->next->next->next = head; // Liên kết vòng
🎯 3. Các thao tác trên danh sách liên kết
✅ Thêm phần tử vào đầu danh sách
void insertAtHead(struct Node **head, int value) {
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = *head;
*head = newNode;
}
💡 Giải thích:
- Cấp phát bộ nhớ cho nút mới, gán giá trị và trỏ con trỏ next của nó đến nút đầu tiên hiện tại.
- Sau đó, head được cập nhật để trỏ đến nút mới.
✅ Thêm phần tử vào cuối danh sách
void insertAtTail(struct Node **head, int value) {
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if (*head == NULL) {
*head = newNode;
return;
}
struct Node *temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
💡 Giải thích:
- Nếu danh sách rỗng, gán newNode làm head.
- Nếu không, duyệt đến nút cuối cùng và gán next của nó bằng newNode.
✅ Xóa phần tử đầu tiên của danh sách
void deleteAtHead(struct Node **head) {
if (*head == NULL) return;
struct Node *temp = *head;
*head = (*head)->next;
free(temp);
}
💡 Giải thích:
- Lưu trữ nút đầu tiên vào temp, sau đó cập nhật head trỏ đến nút tiếp theo.
- Giải phóng bộ nhớ của nút đầu tiên.
✅ Duyệt danh sách liên kết
void printList(struct Node *head) {
struct Node *temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
💡 Giải thích:
- Duyệt qua từng nút và in ra giá trị của nó cho đến khi gặp NULL, dấu hiệu kết thúc danh sách.
🚀 4. Chương trình hoàn chỉnh
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
void insertAtHead(struct Node **head, int value) {
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = *head;
*head = newNode;
}
void printList(struct Node *head) {
struct Node *temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main() {
struct Node *head = NULL;
insertAtHead(&head, 5);
insertAtHead(&head, 10);
insertAtHead(&head, 20);
printList(head);
return 0;
}
💡 Giải thích:
Chương trình này tạo một danh sách liên kết, thêm ba phần tử vào đầu danh sách và in ra danh sách kết quả.
🔥 5. Tổng kết
💡 Tóm tắt kiến thức quan trọng về danh sách liên kết:
✅ Cấu trúc dữ liệu động, không cần cấp phát trước.
✅ Thêm, xóa phần tử nhanh chóng và dễ dàng.
✅ Các loại danh sách liên kết: đơn, đôi, vòng giúp giải quyết nhiều bài toán linh hoạt hơn.
✅ Việc thao tác, duyệt danh sách liên kết rất quan trọng trong các ứng dụng thực tế.
💬 Bạn đã từng sử dụng danh sách liên kết trong bài toán nào chưa? Bình luận bên dưới nhé! ⬇️⬇️⬇️
📌 Bạn thấy bài viết này hữu ích? Đừng quên LIKE & CHIA SẺ cho bạn bè cùng học nhé! 🚀