14.1 linked list

ในหน้า 5.5 เราแทรกคนเข้าหัวแถวที่เก็บในอาเรย์ ทุกคนในแถวต้องถอยหลังหนึ่งช่อง แถวยาว N คน การแทรกครั้งเดียวต้องเลื่อน N ครั้ง ถ้าโจทย์สั่งแทรกหัวแถวหนึ่งแสนครั้ง ก็ต้องเลื่อนรวมกันราว 5 × 10⁹ ครั้ง หน้า 14.3 วัดไว้ว่าคอมไพล์แบบ -O2 ยังใช้แค่ราว 0.21 วินาที เพราะการเลื่อนช่องที่ติดกันเป็นงานที่ซีพียูทำได้เร็วมาก แต่แบบ Code::Blocks ใช้ราว 2.5 วินาที และพอเพิ่มเป็นสองแสนครั้ง งานโตขึ้นสี่เท่า แบบ -O2 ก็ใช้ราว 0.85 วินาที เฉียดขอบเวลาแล้ว ปัญหาอยู่ที่อาเรย์บังคับให้ของที่อยู่ติดกันในแถว ต้องอยู่ช่องติดกันในหน่วยความจำด้วย

ลองนึกถึงขบวนรถไฟ ตู้แต่ละตู้ไม่ได้จอดอยู่ในช่องที่ตีเส้นไว้ แต่ละตู้แค่มีขอเกี่ยวไปยังตู้ถัดไป จะพ่วงตู้ใหม่ไว้หน้าขบวนก็แค่เกี่ยวขอของตู้ใหม่เข้ากับตู้แรก ตู้อื่นไม่ต้องขยับเลย โครงสร้างข้อมูลแบบนี้เรียกว่า linked list (รายการโยง) หน้านี้สร้าง linked list ด้วย struct malloc และ -> จากบทที่ 10 และ 11

node หนึ่งตู้

ข้อมูลหนึ่งตัวใน linked list เรียกว่า node (โหนด) node หนึ่งเก็บสองอย่าง คือ ค่าของมัน กับ pointer ที่ชี้ไป node ถัดไป node สุดท้ายไม่มีตัวถัดไป จึงให้ pointer เป็น NULL และเราจำแค่ pointer ที่ชี้ node แรก เรียกว่า head (หัว) ที่เหลือเดินตาม pointer ไปเอา

กล่องซ้ายของแต่ละ node คือค่า กล่องขวาคือ pointer ชื่อ next ลูกศรแปลว่า "เก็บที่อยู่ของ node นั้นไว้" node ทั้งสี่ไม่จำเป็นต้องอยู่ติดกันในหน่วยความจำ จะกระจัดกระจายแค่ไหนก็ได้ ขอแค่ลูกศรต่อกันครบ

struct ของ node คือแบบเดียวกับที่ประกาศไว้ในหน้า 11.4

typedef struct Node { // (1)!
    int value;
    struct Node *next; // (2)!
} Node;

ตั้งชื่อ struct ว่า Node ไว้หลังคำว่า struct ด้วย และใช้ typedef ให้ชื่อ Node เฉยๆ ใช้แทน struct Node ได้
ตรงนี้ต้องเขียนเต็มว่า struct Node * เพราะชื่อสั้น Node จาก typedef ยังไม่เกิด ถ้าเขียนแบบสั้นจะเจอ unknown type name 'Node' ตามส่วนลองทำให้พังของหน้า 11.4

หน้า 11.4 ต่อ node สองตัวที่เป็นตัวแปรธรรมดาใน main แต่ลิสต์จริงต้องยาวได้ตามข้อมูลเข้า ซึ่งไม่รู้ล่วงหน้าว่ากี่ตัว จึงต้องขอ node ใหม่ระหว่างรันด้วย malloc จากบทที่ 10 node ที่ได้จาก malloc อยู่จนกว่าจะ free ไม่หายไปตอนฟังก์ชันที่สร้างมันจบ

ต่อสาม node ด้วยมือ

เริ่มจากขบวนรถไฟสามตู้ หมายเลข 3 9 และ 2 ขอหน่วยความจำให้แต่ละตู้ด้วย malloc แล้วเกี่ยว next ทีละตู้

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

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

int main()
{
    Node *a = malloc(sizeof(Node)); // (1)!
    Node *b = malloc(sizeof(Node));
    Node *c = malloc(sizeof(Node));
    a->value = 3;
    b->value = 9;
    c->value = 2;
    a->next = b; // (2)!
    b->next = c;
    c->next = NULL; // (3)!
    Node *head = a;
    for (Node *p = head; p != NULL; p = p->next) { // (4)!
        if (p != head) {
            printf(" ");
        }
        printf("%d", p->value);
    }
    printf("\n");
    free(a); // (5)!
    free(b);
    free(c);
    return 0;
}

ขอพื้นที่ขนาดหนึ่ง Node แล้วได้ที่อยู่ของพื้นที่นั้นกลับมา malloc อยู่ใน stdlib.h
เก็บที่อยู่ของตู้ 9 ไว้ใน next ของตู้ 3 นี่คือการเกี่ยวขอ
ตู้สุดท้ายต้องบอกว่าไม่มีตู้ต่อแล้ว ห้ามลืมบรรทัดนี้
เดินจากหัวไปทีละตู้จนเจอ NULL อธิบายในหัวข้อถัดไป
ทุกพื้นที่ที่ได้จาก malloc ต้องคืนด้วย free เมื่อเลิกใช้

3 9 2

เดินไปตามลิสต์

อาเรย์ไปช่องถัดไปด้วย i++ linked list ไป node ถัดไปด้วย p = p->next คือเอาที่อยู่ที่เก็บใน next ของ node ปัจจุบันมาใส่ p ลูปจึงมีหน้าตาแบบนี้เสมอ

for (Node *p = head; p != NULL; p = p->next) {
    // ทำอะไรกับ p->value
}

รอบ	`p` ชี้ node ที่เก็บ	พิมพ์	หลัง `p = p->next`
1	3	3	ชี้ node 9
2	9	9	ชี้ node 2
3	2	2	`NULL` ลูปหยุด

เงื่อนไข p != NULL คือหัวใจของลูปนี้ ถ้าลิสต์ว่าง head เป็น NULL ตั้งแต่แรก ลูปจะไม่ทำเลยสักรอบ โดยไม่ต้องเขียนกรณีพิเศษ

สังเกตว่าเราใช้ตัวแปร p แยกต่างหาก ไม่ได้เลื่อน head เอง เพราะ head เป็นทางเดียวที่จะกลับมาหาลิสต์ได้ ถ้าเลื่อนมันไปจนเป็น NULL ลิสต์ทั้งขบวนก็หายไปจากมือเรา ดูได้ในส่วนลองทำให้พัง

อีกเรื่องที่ต่างจากอาเรย์ คือ linked list ไม่มี a[i] อยากได้ตัวที่ 1000 ต้องเดินจากหัวไป 999 ก้าว ไม่มีทางลัด

เพิ่มที่หัว

พ่วงตู้ใหม่ไว้หน้าขบวนทำสองจังหวะ

ให้ next ของตู้ใหม่ชี้ตู้ที่เป็นหัวอยู่ตอนนี้
ย้าย head มาชี้ตู้ใหม่

ลูกศรสีส้มคือสองเส้นที่เปลี่ยน ตู้ 9 กับตู้ 2 ไม่ได้ถูกแตะเลย ไม่ว่าขบวนยาวแค่ไหนก็ทำแค่สองจังหวะนี้ เขียนเป็นฟังก์ชันได้ดังนี้ ฟังก์ชันเปลี่ยน head ของ main ตรงๆ ไม่ได้ เพราะได้รับแค่สำเนาค่า จึงคืนหัวใหม่กลับไป แล้วให้คนเรียกเขียน head = push_front(head, x);

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

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

Node *push_front(Node *head, int value)
{
    Node *node = malloc(sizeof(Node));
    node->value = value;
    node->next = head; // (1)!
    return node; // (2)!
}

void free_list(Node *head) // (3)!
{
    while (head != NULL) {
        Node *next = head->next;
        free(head);
        head = next;
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    Node *head = NULL; // (4)!
    for (int i = 0; i < n; i++) {
        int car;
        scanf("%d", &car);
        head = push_front(head, car);
    }
    for (Node *p = head; p != NULL; p = p->next) {
        if (p != head) {
            printf(" ");
        }
        printf("%d", p->value);
    }
    printf("\n");
    free_list(head);
    return 0;
}

จังหวะที่ 1 ตู้ใหม่เกี่ยวตู้หัวเดิม ถ้าลิสต์ว่าง head เป็น NULL ตู้ใหม่ก็กลายเป็นตู้สุดท้ายเองโดยอัตโนมัติ
จังหวะที่ 2 ส่งที่อยู่ของตู้ใหม่กลับไป ให้คนเรียกเอาไปใส่ head
คืนหน่วยความจำทุก node อธิบายในหัวข้อ คืนหน่วยความจำทั้งลิสต์
ลิสต์ว่างคือ head เป็น NULL ต้องกำหนดค่านี้เสมอ ถ้าปล่อยเป็นค่าขยะ ลูปจะเดินไปตามที่อยู่มั่วๆ

4
3 9 2 7

7 2 9 3

ลำดับกลับกันกับที่ป้อน เพราะตู้ที่มาทีหลังไปอยู่หน้าเสมอ เป็นวิธีกลับลำดับที่ง่ายที่สุดวิธีหนึ่ง และจะเห็นอีกครั้งในหน้า 14.4 เพราะการเพิ่มและเอาออกที่หัวคือ stack นั่นเอง

เพิ่มที่ท้าย

ถ้าอยากได้ลำดับเดียวกับที่ป้อน ต้องพ่วงตู้ใหม่ไว้ท้ายขบวน วิธีตรงๆ คือเดินจากหัวไปหาตู้สุดท้ายทุกครั้ง แต่ตู้ที่ i ต้องเดิน i ก้าว รวม N ตู้ก็ราว N × N / 2 ก้าว ช้าพอๆ กับแทรกหัวอาเรย์ที่เราหนีมา วิธีที่ดีกว่าคือจำตู้สุดท้ายไว้อีกตัวแปรหนึ่ง เรียกว่า tail (หาง)

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

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

void free_list(Node *head)
{
    while (head != NULL) {
        Node *next = head->next;
        free(head);
        head = next;
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    Node *head = NULL;
    Node *tail = NULL;
    for (int i = 0; i < n; i++) {
        Node *node = malloc(sizeof(Node));
        scanf("%d", &node->value); // (1)!
        node->next = NULL; // (2)!
        if (head == NULL) { // (3)!
            head = node;
        } else {
            tail->next = node;
        }
        tail = node;
    }
    for (Node *p = head; p != NULL; p = p->next) {
        if (p != head) {
            printf(" ");
        }
        printf("%d", p->value);
    }
    printf("\n");
    free_list(head);
    return 0;
}

node->value คือตัวแปร int ตัวหนึ่ง จึงส่งที่อยู่ &node->value ให้ scanf ได้เลย
ตู้ใหม่จะเป็นตู้สุดท้าย จึงไม่มีตู้ต่อ
ตู้แรกเป็นกรณีพิเศษ ตอนนั้นยังไม่มี tail ให้เกี่ยว ถ้าเขียน tail->next ตอน tail เป็น NULL โปรแกรมจะพัง

4
3 9 2 7

3 9 2 7

ทุกครั้งที่เขียนโค้ดลิสต์ ให้ถามตัวเองสามคำถาม ถ้าลิสต์ว่างจะเป็นอย่างไร ถ้ามีตัวเดียวจะเป็นอย่างไร และตัวแปร head กับ tail ยังชี้ถูกตัวไหม บั๊กของ linked list เกือบทั้งหมดอยู่ที่สามจุดนี้

ค้นหา

หาตู้ที่มีหมายเลขที่ต้องการ ต้องเดินดูทีละตู้แบบค้นหาในอาเรย์ ถ้าเจอให้คืน pointer ของตู้นั้น ถ้าเดินจนสุดแล้วไม่เจอให้คืน NULL คืนเป็น pointer ดีกว่าคืนลำดับที่ เพราะหน้าถัดไปจะเอา pointer นี้ไปแทรกตู้ต่อท้ายตู้ที่หาเจอได้ทันที

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

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

Node *push_front(Node *head, int value)
{
    Node *node = malloc(sizeof(Node));
    node->value = value;
    node->next = head;
    return node;
}

Node *find(Node *head, int value)
{
    for (Node *p = head; p != NULL; p = p->next) {
        if (p->value == value) {
            return p;
        }
    }
    return NULL;
}

int length(Node *head)
{
    int count = 0;
    for (Node *p = head; p != NULL; p = p->next) {
        count++;
    }
    return count;
}

void free_list(Node *head)
{
    while (head != NULL) {
        Node *next = head->next;
        free(head);
        head = next;
    }
}

int main()
{
    int n, q;
    scanf("%d %d", &n, &q);
    Node *head = NULL;
    for (int i = 0; i < n; i++) {
        int car;
        scanf("%d", &car);
        head = push_front(head, car);
    }
    printf("length = %d\n", length(head));
    for (int i = 0; i < q; i++) {
        int car;
        scanf("%d", &car);
        Node *found = find(head, car);
        if (found != NULL) { // (1)!
            printf("car %d found\n", found->value);
        } else {
            printf("car %d not found\n", car);
        }
    }
    free_list(head);
    return 0;
}

ต้องเช็ก NULL ก่อนใช้ found->value เสมอ ถ้า find หาไม่เจอแล้วเราใช้ -> กับ NULL โปรแกรมพังทันที

length = 4
car 9 found
car 5 not found
car 7 found

คืนหน่วยความจำทั้งลิสต์

node ทุกตัวได้มาจาก malloc จึงต้อง free ทีละตัว ฟังก์ชัน free_list ที่ใช้มาตั้งแต่โปรแกรม push-front ทำแบบนี้

void free_list(Node *head)
{
    while (head != NULL) {
        Node *next = head->next; // (1)!
        free(head);
        head = next; // (2)!
    }
}

จำที่อยู่ของ node ถัดไปไว้ ก่อน free เพราะหลัง free แล้ว node นี้ไม่ใช่ของเรา ห้ามอ่าน head->next อีก
head ในฟังก์ชันเป็นสำเนา เลื่อนได้ตามสบาย head ของ main ไม่เปลี่ยน แต่หลังเรียกฟังก์ชันนี้แล้ว ห้ามใช้ลิสต์นั้นอีก

ถ้าไม่ free เรียกว่า memory leak (หน่วยความจำรั่ว) โปรแกรมที่รันครั้งเดียวแล้วจบ Windows จะเก็บคืนให้ตอนจบอยู่แล้ว แต่ถ้าโจทย์มีหลายชุดข้อมูลในไฟล์เดียว แล้วแต่ละชุดสร้างลิสต์ใหม่โดยไม่คืนลิสต์เก่า หน่วยความจำจะสะสมจนเกินที่โจทย์กำหนดได้ ฝึกคืนให้ครบตั้งแต่ตอนนี้ หน้า 14.3 จะมีอีกวิธีที่ไม่ต้องคิดเรื่องนี้เลย

ลองทำให้พัง

แบบที่ 1 ลืมปิดท้ายด้วย NULL

ในโปรแกรม push-back ลบบรรทัด node->next = NULL; ออก คอมไพล์ผ่านโดยไม่มีคำเตือน แล้วป้อน 3 กับ 9 2 7

บนเครื่องที่เขียนเอกสารนี้ โปรแกรมยังพิมพ์ 9 2 7 ถูกต้อง ดูเหมือนไม่มีอะไรผิด แต่พอลบ free_list ออกอีกอย่าง ซึ่งไม่เกี่ยวกับการสร้างหรือพิมพ์ลิสต์เลย แล้วรันจากโปรแกรม terminal ชื่อ Git Bash โปรแกรมพังทุกครั้งที่ลอง ส่วนรันจาก Command Prompt ยังได้ 9 2 7 ถูก

สาเหตุคือ malloc ไม่ได้ล้างพื้นที่ให้เป็น 0 ใน next ของตู้สุดท้ายจึงเป็นค่าที่ค้างอยู่ในหน่วยความจำตรงนั้น บางครั้งบังเอิญเป็น 0 ซึ่งก็คือ NULL ลูปจึงหยุดถูกที่ บางครั้งเป็นที่อยู่มั่วๆ ลูปก็เดินเลยตู้สุดท้ายไปที่ที่ไม่มีสิทธิ์อ่าน บั๊กแบบนี้ทดสอบในเครื่องตัวเองผ่าน แล้วไปพังใน grader ได้ ตู้สุดท้ายต้องตั้ง next เป็น NULL เองทุกครั้ง

แบบที่ 2 เลื่อน head แทนที่จะใช้ p

ต่อจากโปรแกรม push-back อยากพิมพ์ลิสต์สองรอบ แต่รอบแรกเขียนลูปด้วย head ตรงๆ

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

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

int main()
{
    int n;
    scanf("%d", &n);
    Node *head = NULL;
    Node *tail = NULL;
    for (int i = 0; i < n; i++) {
        Node *node = malloc(sizeof(Node));
        scanf("%d", &node->value);
        node->next = NULL;
        if (head == NULL) {
            head = node;
        } else {
            tail->next = node;
        }
        tail = node;
    }
    printf("first:");
    while (head != NULL) {
        printf(" %d", head->value);
        head = head->next;
    }
    printf("\n");
    printf("second:");
    for (Node *p = head; p != NULL; p = p->next) {
        printf(" %d", p->value);
    }
    printf("\n");
    return 0;
}

4
3 9 2 7

first: 3 9 2 7
second:

รอบแรกถูก แต่จบรอบแรก head เป็น NULL ไปแล้ว รอบที่สองจึงไม่มีอะไรให้พิมพ์ ตู้ทั้งสี่ยังอยู่ในหน่วยความจำ แต่ไม่มีตัวแปรไหนรู้ที่อยู่ของมันอีก จะใช้หรือจะ free ก็ทำไม่ได้แล้ว โปรแกรมนี้จึงไม่ได้เรียก free_list ตอนจบ เพราะไม่มีหัวให้เรียก เดินลิสต์ด้วยตัวแปรแยกเสมอ

แบบที่ 3 ใช้ head ของลิสต์ว่าง

เขียนโปรแกรมที่สร้างลิสต์ด้วย push_front แล้วพิมพ์ตู้หัวขบวนด้วย printf("first = %d\n", head->value); โดยไม่เช็กอะไร ป้อน 0 คือไม่มีตู้เลย คอมไพล์ผ่านโดยไม่มีคำเตือน แต่โปรแกรมปิดตัวโดยไม่พิมพ์อะไร และ Code::Blocks ขึ้นว่า

Process returned -1073741819 (0xC0000005)

รหัสเดียวกับใช้ index ไกลเกินอาเรย์ในหน้า 5.5 คือเข้าถึงหน่วยความจำที่ไม่มีสิทธิ์ NULL คือที่อยู่ที่ไม่มีของอะไรเลย ใช้ -> กับมันเมื่อไรก็พัง ก่อนเขียน x-> ทุกครั้ง ให้ถามว่า x เป็น NULL ได้ไหม ถ้าได้ต้องเช็กก่อน

สรุป

node เก็บค่ากับ next ที่ชี้ node ถัดไป node สุดท้ายชี้ NULL ลิสต์ว่างคือ head == NULL
ใน struct ของตัวเองต้องเขียน struct Node *next เต็มชื่อ
เดินลิสต์ด้วย for (Node *p = head; p != NULL; p = p->next) ใช้ตัวแปรแยก ไม่เลื่อน head
เพิ่มที่หัวทำสองจังหวะ ไม่ต้องขยับตู้อื่น เพิ่มที่ท้ายให้จำ tail ไว้
ฟังก์ชันที่อาจเปลี่ยนหัว ให้คืนหัวใหม่ แล้วเขียน head = f(head, ...)
ไม่มี a[i] อยากได้ตัวที่ i ต้องเดินจากหัว
free ทุก node โดยจำ next ไว้ก่อน free