ลิงก์ลิสต์แบบทางเดียว

ลิงก์ลิสต์คืออะไร

#include <stdio.h>

struct Node {
    int value;
    struct Node *next;
};

int main(void) {
    printf("A node holds a value and a next pointer\n");
    return 0;
}

การกำหนดโหนด

#include <stdio.h>

struct Node {
    int value;
    struct Node *next;
};

int main(void) {
    struct Node n;
    n.value = 42;
    n.next = NULL;
    printf("value=%d, next is NULL: %d\n", n.value, n.next == NULL);
    return 0;
}

พอยน์เตอร์ส่วนหัว

#include <stdio.h>

struct Node { int value; struct Node *next; };

int main(void) {
    struct Node *head = NULL;
    printf("List is empty: %d\n", head == NULL);
    return 0;
}

การจัดสรรโหนด

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

struct Node { int value; struct Node *next; };

int main(void) {
    struct Node *n = malloc(sizeof(struct Node));
    n->value = 7;
    n->next = NULL;
    printf("%d\n", n->value);
    free(n);
    return 0;
}

ตัวดำเนินการลูกศร

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

struct Node { int value; struct Node *next; };

int main(void) {
    struct Node *n = malloc(sizeof(struct Node));
    n->value = 99;
    printf("%d\n", n->value);
    free(n);
    return 0;
}

การเชื่อมโหนดสองโหนด

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

struct Node { int value; struct Node *next; };

int main(void) {
    struct Node *a = malloc(sizeof(struct Node));
    struct Node *b = malloc(sizeof(struct Node));
    a->value = 1; a->next = b;
    b->value = 2; b->next = NULL;
    printf("%d -> %d\n", a->value, a->next->value);
    free(a); free(b);
    return 0;
}

ตัวช่วยสร้างโหนด

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

struct Node { int value; struct Node *next; };

struct Node *make(int v) {
    struct Node *n = malloc(sizeof(struct Node));
    n->value = v;
    n->next = NULL;
    return n;
}

int main(void) {
    struct Node *n = make(5);
    printf("%d\n", n->value);
    free(n);
    return 0;
}

การสร้างลิสต์ขนาดเล็ก

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    head->next->next = make(3);
    printf("%d %d %d\n", head->value, head->next->value, head->next->next->value);
    return 0;
}

การพิมพ์ลิสต์

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    for (struct Node *p = head; p; p = p->next)
        printf("%d ", p->value);
    printf("\n");
    return 0;
}

อาร์เรย์กับลิงก์ลิสต์

#include <stdio.h>

int main(void) {
    printf("Array: O(1) index, costly resize\n");
    printf("List:  O(n) index, cheap insert/delete\n");
    return 0;
}

การคืนหน่วยความจำของรายการทั้งหมด

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    struct Node *p = head;
    while (p) {
        struct Node *nxt = p->next;
        free(p);
        p = nxt;
    }
    printf("freed all nodes\n");
    return 0;
}

ตรวจสอบความเข้าใจอย่างรวดเร็ว

สรุปทบทวน