การแทรกข้อมูลใน Linked List ด้วยภาษา C

Linked List ใช้การจัดสรรหน่วยความจำแบบไดนามิก (Dynamic Memory Allocation) หมายความว่ามันสามารถขยายหรือย่อขนาดได้ตามต้องการ โครงสร้างข้อมูลนี้ถูกนิยามเป็นชุดของโหนด (Nodes) โดยแต่ละโหนดประกอบด้วย 2 ส่วนคือ ส่วนข้อมูล (Data) และส่วนลิงก์ (Link/Pointer) ที่ชี้ไปยังโหนดถัดไป รูปแบบการแสดงข้อมูล ลิงก์ และ Linked List แสดงในภาพด้านล่าง

การดำเนินการบน Linked List

ในภาษา C มีการดำเนินการหลัก 3 แบบบน Linked List ดังนี้

• Insertion (การแทรก) - เพิ่มโหนดใหม่เข้าไปในรายการ
• Deletion (การลบ) - ลบโหนดออกจากรายการ
• Traversing (การเดินทาง/วนลูป) - เข้าถึงข้อมูลในแต่ละโหนดตามลำดับ

การแทรกข้อมูล (Insertion)

พิจารณาตัวอย่างการแทรกโหนดที่มีค่า 5 ระหว่างโหนด 2 และ 3

การแทรกโหนด 5 ที่จุดเริ่มต้น (Head)

การแทรกโหนด 5 ที่จุดสิ้นสุด (Tail)

หมายเหตุ:

• ไม่สามารถแทรกโหนด 5 ก่อนโหนด 2 ได้โดยตรง เนื่องจากโหนดไม่ได้มีชื่อตัวระบุ (Node ไม่มีชื่อ)
• สามารถแทรกโหนด 5 ก่อนโหนด 2 ได้ หากระบุตำแหน่ง (Position) ให้ชัดเจน

โปรแกรมตัวอย่าง

โปรแกรม C ต่อไปนี้สาธิตการแทรกข้อมูลใน Linked List แบบครบถ้วน (แทรกหน้า แทรกท้าย แทรกหลังค่าใด แทรกก่อนค่าใด)

#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;
    }
    printf("Node with value %d not found\n", after);
}

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;
    }
    printf("Node with value %d not found\n", before);
    free(new_node);
}

int main() {
    int count = 0, i, val, after, before;
    struct node *head = NULL;
    
    printf("Enter number of elements: ");
    scanf("%d", &count);
    
    for (i = 0; i < count; i++) {
        printf("Enter %dth element: ", i);
        scanf("%d", &val);
        insert_front(&head, val);
    }
    
    printf("Starting list: ");
    print_list(head);
    
    printf("Enter front element: ");
    scanf("%d", &val);
    insert_front(&head, val);
    printf("Items after insertion: ");
    print_list(head);
    
    printf("Enter last element: ");
    scanf("%d", &val);
    insert_end(&head, val);
    printf("Items after insertion: ");
    print_list(head);
    
    printf("Enter element to insert: ");
    scanf("%d", &val);
    printf("Insert after: ");
    scanf("%d", &after);
    insert_after(head, val, after);
    printf("List after insertion: ");
    print_list(head);
    
    printf("Enter element to insert: ");
    scanf("%d", &val);
    printf("Insert before: ");
    scanf("%d", &before);
    insert_before(&head, val, before);
    printf("List after insertion: ");
    print_list(head);
    
    return 0;
}

ผลลัพธ์การรันโปรแกรม

Enter no: of elements: 4
Enter 0th element: 1
Enter 1th element: 2
Enter 2th element: 3
Enter 3th element: 4
starting list: H->4->3->2->1->......
enter front element: 5
items after insertion: H->5->4->3->2->1->......
enter last element: 0
items after insertion: H->5->4->3->2->1->0->......
Enter an ele to insert in the list: 6
Insert after: 0
List after insertion: H->5->4->3->2->1->0->6->......
Enter an ele to insert in the list: 7
Insert before: 5
List after insertion: H->7->5->4->3->2->1->0->6->......