Giải thích chèn phần tử vào danh sách liên kết bằng ngôn ngữ C

Danh sách liên kết sử dụng cấp phát bộ nhớ động, nghĩa là chúng tự động mở rộng và thu nhỏ khi cần. Chúng được định nghĩa là tập hợp các nút (node), mỗi nút gồm hai phần: dữ liệu (data) và liên kết (link). Biểu diễn dữ liệu, liên kết và danh sách liên kết được minh họa như sau:

Các thao tác trên danh sách liên kết

Có ba loại thao tác chính trên danh sách liên kết trong ngôn ngữ C:

• Chèn (Insertion)
• Xóa (Deletion)
• Duyệt (Traversing)

Thao tác chèn

Xét ví dụ chèn nút 5 vào giữa nút 2 và nút 3:

Chèn nút 5 vào đầu danh sách:

Chèn nút 5 vào cuối danh sách:

Chèn nút 5 vào cuối danh sách (trường hợp khác):

Lưu ý:

• Không thể chèn nút 5 trước nút 2 vì các nút không được đặt tên.
• Có thể chèn nút 5 trước nút 2 nếu vị trí của nó được chỉ định.

Chương trình mẫu

Dưới đây là chương trình C minh họa việc chèn phần tử vào danh sách liên kết:

#include <stdio.h>
#include <stdlib.h>

struct node {
    int val;
    struct node *next;
};

void print_list(struct node *head) {
    printf("H->");
    while(head) {
        printf("%d->", head->val);
        head = head->next;
    }
    printf("......\n\n");
}

void insert_front(struct node **head, int value) {
    struct node *new_node = (struct node *)malloc(sizeof(struct node));
    if (new_node == NULL) {
        printf("Out of memory");
        return;
    }
    new_node->val = value;
    new_node->next = *head;
    *head = new_node;
}

void insert_end(struct node **head, int value) {
    struct node *new_node = (struct node *)malloc(sizeof(struct node));
    if (new_node == NULL) {
        printf("Out of memory");
        return;
    }
    new_node->val = value;
    new_node->next = NULL;
    
    if (*head == NULL) {
        *head = new_node;
        return;
    }
    
    struct node *last = *head;
    while(last->next) last = last->next;
    last->next = new_node;
}

void insert_after(struct node *head, int value, int after) {
    struct node *tmp = head;
    while(tmp) {
        if(tmp->val == after) {
            struct node *new_node = (struct node *)malloc(sizeof(struct node));
            if (new_node == NULL) {
                printf("Out of memory");
                return;
            }
            new_node->val = value;
            new_node->next = tmp->next;
            tmp->next = new_node;
            return;
        }
        tmp = tmp->next;
    }
}

void insert_before(struct node **head, int value, int before) {
    struct node *new_node = (struct node *)malloc(sizeof(struct node));
    if (new_node == NULL) {
        printf("Out of memory");
        return;
    }
    new_node->val = value;
    
    if ((*head)->val == before) {
        new_node->next = *head;
        *head = new_node;
        return;
    }
    
    struct node *tmp = *head;
    while(tmp && tmp->next) {
        if(tmp->next->val == before) {
            new_node->next = tmp->next;
            tmp->next = new_node;
            return;
        }
        tmp = tmp->next;
    }
    // Không tìm thấy nút before
    free(new_node);
}

int main() {
    int count = 0, i, val, after, before;
    struct node *head = NULL;
    
    printf("Nhập số lượng phần tử: ");
    scanf("%d", &count);
    
    for (i = 0; i < count; i++) {
        printf("Nhập phần tử thứ %d: ", i);
        scanf("%d", &val);
        insert_front(&head, val);
    }
    
    printf("Danh sách ban đầu: ");
    print_list(head);
    
    printf("Nhập phần tử chèn đầu: ");
    scanf("%d", &val);
    insert_front(&head, val);
    printf("Danh sách sau khi chèn: ");
    print_list(head);
    
    printf("Nhập phần tử chèn cuối: ");
    scanf("%d", &val);
    insert_end(&head, val);
    printf("Danh sách sau khi chèn: ");
    print_list(head);
    
    printf("Nhập phần tử cần chèn: ");
    scanf("%d", &val);
    printf("Chèn sau giá trị: ");
    scanf("%d", &after);
    insert_after(head, val, after);
    printf("Danh sách sau khi chèn: ");
    print_list(head);
    
    printf("Nhập phần tử cần chèn: ");
    scanf("%d", &val);
    printf("Chèn trước giá trị: ");
    scanf("%d", &before);
    insert_before(&head, val, before);
    printf("Danh sách sau khi chèn: ");
    print_list(head);
    
    return 0;
}

Kết quả chạy chương trình

Khi thực thi chương trình trên, kết quả thu được như sau:

Nhập số lượng phần tử: 4
Nhập phần tử thứ 0: 1
Nhập phần tử thứ 1: 2
Nhập phần tử thứ 2: 3
Nhập phần tử thứ 3: 4
Danh sách ban đầu: H->4->3->2->1->......
Nhập phần tử chèn đầu: 5
Danh sách sau khi chèn: H->5->4->3->2->1->......
Nhập phần tử chèn cuối: 0
Danh sách sau khi chèn: H->5->4->3->2->1->0->......
Nhập phần tử cần chèn: 6
Chèn sau giá trị: 0
Danh sách sau khi chèn: H->5->4->3->2->1->0->6->......
Nhập phần tử cần chèn: 7
Chèn trước giá trị: 5
Danh sách sau khi chèn: H->7->5->4->3->2->1->0->6->......