Danh sách liên kết
Các nút được nối bằng con trỏ
- Một danh sách liên kết là chuỗi các cấu trúc nhỏ gọi là nút, phân tán trong vùng nhớ động (heap).
- Mỗi nút chứa một giá trị và một con trỏ đến nút tiếp theo. Duyệt qua các con trỏ để đi qua danh sách.
- Khác với mảng, danh sách có thể phát triển thêm một nút tại một thời điểm mà không cần di chuyển các nút khác.
Cấu trúc tự tham chiếu
- Một nút là một cấu trúc chứa con trỏ trỏ đến chính loại của nó:
struct Node { int data; struct Node *next; };—datalà giá trị,nexttrỏ đến node tiếp theo.- Điều này được cung cấp cho bạn dưới dạng
Nodetrong mỗi bộ khởi đầu. Con trỏnextcủa nút cuối cùng làNULL.
head và dấu chấm NULL
- Một con trỏ đơn, head (đầu), trỏ đến nút đầu tiên. Từ đó bạn có thể truy cập phần còn lại.
- Nút cuối cùng trỏ đến
NULL, đánh dấu sự kết thúc của danh sách. - Một danh sách rỗng chỉ là
head == NULL— hoàn toàn không có nút nào.
#include <stdio.h>
typedef struct Node { int data; struct Node *next; } Node;
int main(void) {
// A tiny list on the stack: 10 -> 20 -> 30 -> NULL
Node n3 = {30, NULL};
Node n2 = {20, &n3};
Node n1 = {10, &n2};
const Node *head = &n1;
// Walk it: follow ->next until NULL, counting nodes
int count = 0;
const Node *cur = head; // start at the head
while (cur != NULL) { // stop at the NULL end
count++;
cur = cur->next; // step to the next node
}
printf("length = %d\n", count); // length = 3
return 0;
}
Thêm một nút ở phía trước
- Để thêm vào đầu, tạo một node mới, trỏ
nextcủa nó vào đầu cũ, và trả về node mới làm đầu mới. - Việc này rất nhanh — nó không chạm vào bất kỳ nút nào khác.
- Vì head thay đổi, hàm trả về head mới, và người gọi lưu giữ nó.
Lỗi thường gặp
- Đừng bao giờ mất con trỏ
head, nếu không toàn bộ danh sách sẽ không thể truy cập được. - Giải phóng mọi nút; nút cuối cùng trỏ đến
NULL.
Bây giờ bạn thử
- Duyệt danh sách bằng cách dùng con trỏ
curvàcur = cur->next, dừng lại khi gặpNULL. - Các nút mới đến từ
malloc(sizeof(Node)); trình kiểm tra sẽ giải phóng danh sách. Đừng viết một hàmmain.
Nodes and pointers
Each node points to the next; insert/delete by re-linking.
Độ khó 5/5 · 400 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Complete int length(const Node *head) so it counts the nodes in the list (0 for an empty list). Walk with ->next until NULL. The Node type is given. Do không write a main.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 5/5 · 400 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Complete int sum_list(const Node *head) so it returns the total of every node's data (0 for an empty list). The Node type is given. Do không write a main.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 5/5 · 400 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Complete Node *push_front(Node *head, int value) so it makes a new node (with malloc), points its next at the old head, and returns it as the new head. The checker frees the list. Do không write a main.
Nhấn Chạy để xem kết quả ở đây.