Khi các ứng dụng ngày càng trở nên phức tạp với lượng dữ liệu khổng lồ, việc hiểu và áp dụng đúng Cấu trúc dữ liệu và Giải thuật (CTDL & GT) không còn là tùy chọn mà là yêu cầu bắt buộc đối với mọi kỹ sư. Bài viết này sẽ giúp bạn hiểu rõ bản chất của CTDL & GT và đi sâu vào một trong những cấu trúc dữ liệu động phổ biến nhất: Danh sách liên kết đơn.
🎯 Mục tiêu học tập
- Nắm vững khái niệm và vai trò của CTDL & GT trong phát triển phần mềm.
- Hiểu bản chất và đặc điểm của Danh sách liên kết đơn (Singly Linked List).
- Thành thạo kỹ thuật cài đặt các thao tác cơ bản: Thêm, Xóa, Tìm kiếm, Duyệt trên Linked List.
- Biết cách quản lý bộ nhớ thông qua việc cấp phát động cho từng Node.
1. Giới thiệu về Cấu trúc dữ liệu và Thuật toán
Khái niệm
- Cấu trúc dữ liệu (Data Structure): Là cách lập trình để lưu trữ và tổ chức dữ liệu sao cho chúng có thể được sử dụng một cách hiệu quả nhất.
- Thuật toán (Algorithms): Là một tập hợp các lệnh được thực hiện theo một thứ tự nhất định để giải quyết một vấn đề hoặc đạt được một đầu ra mong muốn.
CTDL & GT là sự kết hợp tối ưu giữa cách tổ chức dữ liệu và phương pháp xử lý để giải quyết các bài toán lớn một cách hiệu quả về cả không gian (bộ nhớ) và thời gian (tốc độ).
Tại sao CTDL & GT lại quan trọng?
Trong kỷ nguyên Big Data, các ứng dụng phải đối mặt với 3 thách thức lớn:
- Tìm kiếm dữ liệu: Xử lý hàng tỷ bản ghi yêu cầu thuật toán tìm kiếm cực nhanh.
- Giới hạn tốc độ xử lý: Dù CPU rất mạnh nhưng vẫn có giới hạn nếu cấu trúc dữ liệu quá cồng kềnh.
- Xử lý đa yêu cầu: Hàng ngàn người dùng truy cập đồng thời yêu cầu dữ liệu phải được tổ chức khoa học để không gây lỗi máy chủ.
2. Danh sách liên kết đơn (Singly Linked List)
Định nghĩa
Danh sách liên kết đơn là một cấu trúc dữ liệu gồm một nhóm các Nút (Node) tạo thành một chuỗi. Mỗi nút bao gồm hai thành phần chính:
- Thành phần dữ liệu (Data): Lưu trữ thông tin của phần tử.
- Thành phần liên kết (Next): Lưu địa chỉ của nút kế tiếp trong chuỗi. Nếu là nút cuối cùng, thành phần này trỏ tới
NULL.
Đặc điểm nổi bật
- Là cấu trúc dữ liệu động: Kích thước có thể thay đổi linh hoạt khi chương trình đang chạy.
- Quản lý bộ nhớ hiệu quả: Các phần tử được lưu trữ ngẫu nhiên trong RAM, không cần một khối nhớ liên tục như mảng.
- Truy cập tuần tự: Để tìm một phần tử, ta phải duyệt từ đầu danh sách (Linear Search).
3. Cài đặt Danh sách liên kết đơn bằng C
Khai báo cấu trúc Node
struct LinkedList {
int data;
struct LinkedList *next; // Con trỏ trỏ đến Node kế tiếp
};
typedef struct LinkedList *node;
Các thao tác cơ bản
Tạo mới một Node
node CreateNode(int value) {
node temp = (node)malloc(sizeof(struct LinkedList));
temp->next = NULL;
temp->data = value;
return temp;
}
Thêm Node vào đầu danh sách
node AddHead(node head, int value) {
node temp = CreateNode(value);
if (head == NULL) {
head = temp;
} else {
temp->next = head;
head = temp;
}
return head;
}
Thêm Node vào cuối danh sách
node AddTail(node head, int value) {
node temp = CreateNode(value);
if (head == NULL) {
head = temp;
} else {
node p = head;
while (p->next != NULL) {
p = p->next; // Duyệt đến cuối danh sách
}
p->next = temp;
}
return head;
}
Xóa Node ở vị trí bất kỳ
node DelAt(node head, int position) {
if (position == 0 || head == NULL || head->next == NULL) {
head = DelHead(head);
} else {
int k = 1;
node p = head;
while (p->next->next != NULL && k != position) {
p = p->next;
++k;
}
if (k == position) {
p->next = p->next->next; // Bỏ qua phần tử tại vị trí cần xóa
}
}
return head;
}
🚀 Bài tập về nhà
Dựa trên kiến thức đã học về Linked List, hãy thực hiện yêu cầu sau:
- Viết lại bài toán Quản lý danh sách nhân viên (đã làm ở Buổi 4) nhưng sử dụng Danh sách liên kết đơn thay cho mảng tĩnh.
- Đảm bảo các tính năng: Thêm nhân viên, Xóa nhân viên theo mã, và Hiển thị danh sách hoạt động chính xác.
📝 Tóm tắt: Danh sách liên kết là bước đệm quan trọng để hiểu về quản lý bộ nhớ động. Khác với mảng, nó mang lại sự linh hoạt tuyệt vời trong việc thêm/xóa phần tử nhưng đòi hỏi kỹ năng quản lý con trỏ vững vàng.
Gợi ý bài tiếp theo: Các thuật toán sắp xếp (Bubble Sort, Selection Sort, Insertion Sort). Chúng ta sẽ học cách đưa dữ liệu trong danh sách về đúng thứ tự mong muốn.
Người thực hiện: Nguyễn Đình Tuấn
Email: tuannguyen.aiot@gmail.com | Website: aiots.vn