Linked lists

English

Nodes joined by pointers

A linked list is a chain of small structs called nodes, scattered around the heap.
Each node holds a value and a pointer to the next node. Follow the pointers to walk the list.
Unlike an array, a list can grow one node at a time without moving the others.

Tiếng Việ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.

English

A self-referential struct

A node is a struct that contains a pointer to its own type:
struct Node { int data; struct Node *next; }; — data is the value, next points to the following node.
This is given for you as Node in each starter. The last node's next is NULL.

Tiếng Việt

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; }; — data là giá trị, next trỏ đến node tiếp theo.
Điều này được cung cấp cho bạn dưới dạng Node trong mỗi bộ khởi đầu. Con trỏ next của nút cuối cùng là NULL.

English

head and the NULL end

A single pointer, the head, points to the first node. From there you reach the rest.
The very last node points to NULL, which marks the end of the list.
An empty list is just head == NULL — there are no nodes at all.

Tiếng Việt

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;
}

English

Adding a node at the front

To add to the front, make a new node, point its next at the old head, and return the new node as the new head.
This is fast — it does not touch any other node.
Because the head changes, the function returns the new head, and the caller saves it.

Tiếng Việt

Thêm một nút ở phía trước

Để thêm vào đầu, tạo một node mới, trỏ next củ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ó.

English

Common mistakes

Never lose the head pointer, or the whole list is unreachable.
Free every node; the last node points to NULL.

Tiếng Việt

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.

English

Now you try

Walk a list with a cur pointer and cur = cur->next, stopping at NULL.
New nodes come from malloc(sizeof(Node)); the checker frees the list. Do not write a main.

Tiếng Việt

Bây giờ bạn thử

Duyệt danh sách bằng cách dùng con trỏ cur và cur = cur->next, dừng lại khi gặp NULL.
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àm main.

Explore · ⁨Khám phá⁩

Nodes and pointers

Each node points to the next; insert/delete by re-linking.

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 not write a main.

typedef struct Node {
    int data;
    struct Node *next;
} Node;

/* Count the nodes from head (0 for NULL). Do not write main(). */
int length(const Node *head) {
    return 0;   /* walk with ->next until NULL */
}

Click Run to see the output here. · ⁨Nhấn Chạy để xem kết quả ở đây.⁩

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 not write a main.

typedef struct Node {
    int data;
    struct Node *next;
} Node;

/* Total every node's data (0 for NULL). Do not write main(). */
int sum_list(const Node *head) {
    return 0;   /* walk and add cur->data */
}

Click Run to see the output here. · ⁨Nhấn Chạy để xem kết quả ở đây.⁩

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 not write a main.

#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

/* Make a new node holding value, link it before head, return it. Do not write main(). */
Node *push_front(Node *head, int value) {
    /* malloc a Node, set its data and next, return it */
    return head;
}

Click Run to see the output here. · ⁨Nhấn Chạy để xem kết quả ở đây.⁩

Nodes joined by pointers

Các nút được nối bằng con trỏ

A self-referential struct

Cấu trúc tự tham chiếu

head and the NULL end

head và dấu chấm NULL

Adding a node at the front

Thêm một nút ở phía trước

Common mistakes

Lỗi thường gặp

Now you try

Bây giờ bạn thử

Nodes and pointers

Handout · ⁨Tài liệu⁩

Log in or create account · ⁨Đăng nhập hoặc tạo tài khoản⁩

Your subject · ⁨Môn học của bạn⁩

All sections · ⁨Tất cả các mục⁩

Feedback & help · ⁨Phản hồi & hỗ trợ⁩