14.3 ลิสต์ด้วยอาเรย์

สองหน้าที่ผ่านมาสร้าง linked list ด้วย malloc ตามตำราทั่วไป หน้านี้ตอบสองคำถามที่น้องต้องตัดสินใจเองตอนแข่ง คือเมื่อไรควรใช้ linked list แทนอาเรย์ และเมื่อใช้แล้วควรเขียนแบบไหน คำตอบของข้อหลังอาจแปลกใจ คนแข่งส่วนใหญ่ไม่ใช้ malloc ทำ linked list แต่ใช้อาเรย์ธรรมดาสองสามตัวแทน

อาเรย์กับ linked list ต่างกันตรงไหน

16 byte มาจาก sizeof(Node) ที่พิมพ์ได้จริงบน GCC ของ Code::Blocks คือ int 4 byte กับ pointer 8 byte และช่องว่างอีก 4 byte ที่ compiler เติมให้ pointer เริ่มที่ตำแหน่งหารด้วย 8 ลงตัว

ต่างกันมากแค่ไหนในทางปฏิบัติ ลองวัดงานที่อาเรย์ทำได้แย่ที่สุด คือเพิ่มที่หัวซ้ำๆ เทียบกับ linked list ที่เพิ่มที่หัวแล้วเดินอ่านทั้งลิสต์หนึ่งรอบ วัดด้วย clock() แบบหน้า 4.5 บนเครื่องที่เขียนเอกสารนี้ (ASUS Vivobook S 14 ซีพียู AMD Ryzen AI 9 HX 370 Windows 11) คอมไพล์ด้วย GCC 14.2 ของ Code::Blocks สองแบบ คือแบบที่ Code::Blocks ตั้งไว้ และแบบ -O2 ที่ grader ส่วนใหญ่ใช้ แต่ละค่ารันสามครั้ง

N เพิ่มสองเท่า เวลาของอาเรย์เพิ่มราวสี่เท่า เพราะการเพิ่มแต่ละครั้งต้องเลื่อนยาวขึ้นเรื่อยๆ ส่วน linked list เพิ่มแค่สองเท่าตาม N และเร็วกว่าเป็นร้อยเท่า

สรุปเป็นหลักเลือกได้ดังนี้

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

linked list ที่ทำจากอาเรย์

pointer ก็คือตัวเลขบอกตำแหน่งในหน่วยความจำ ถ้าเราเก็บ node ทุกตัวไว้ในอาเรย์ ตำแหน่งของ node ก็คือ index ธรรมดา แทนที่ next จะเก็บที่อยู่ ก็เก็บ index ของ node ถัดไปแทน แยกเป็นอาเรย์สองตัว value[i] คือค่าของ node ที่ i และ next[i] คือ index ของ node ถัดไป

เหลือแค่ต้องมีค่าหนึ่งแทน NULL วิธีที่สะดวกคือไม่ใช้ช่อง 0 ให้ node แรกที่สร้างเป็น node 1 แล้วใช้ 0 แปลว่า "ไม่มี node" อาเรย์ global เริ่มเป็น 0 ทุกช่องอยู่แล้วตามหน้า 5.5 ทุก next ที่ยังไม่ได้ตั้งจึงเป็น "ไม่มี" ให้เอง

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

#include <stdio.h>

int value[100001]; // (1)!
int next[100001];
int node_count = 0;

int new_node(int v)
{
    node_count++; // (2)!
    value[node_count] = v;
    next[node_count] = 0;
    return node_count;
}

int main()
{
    int n;
    scanf("%d", &n);
    int head = 0, tail = 0; // (3)!
    for (int i = 0; i < n; i++) {
        int car;
        scanf("%d", &car);
        int node = new_node(car);
        if (head == 0) {
            head = node;
        } else {
            next[tail] = node;
        }
        tail = node;
    }
    int front = new_node(5); // (4)!
    next[front] = head;
    head = front;
    for (int p = head; p != 0; p = next[p]) { // (5)!
        if (p != head) {
            printf(" ");
        }
        printf("%d", value[p]);
    }
    printf("\n");
    for (int i = 1; i <= node_count; i++) {
        printf("node %d: value %d, next %d\n", i, value[i], next[i]);
    }
    return 0;
}

1. ต้องมีช่องพอสำหรับ node ทุกตัวที่เคยสร้าง บวกช่อง 0 ที่ไม่ใช้อีกหนึ่ง โจทย์ให้สร้างไม่เกินแสนตัว จึงประกาศ 100001 ช่องไว้นอก main
2. เพิ่มก่อนแล้วค่อยใช้ node แรกจึงเป็น node 1 ไม่ใช่ 0
3. head กับ tail เป็น int ธรรมดา 0 คือลิสต์ว่าง
4. เพิ่มที่หัวสองจังหวะเหมือนหน้า 14.1 ทุกอย่าง
5. ลูปเดินลิสต์หน้าตาเหมือนเดิม แค่ p->next กลายเป็น next[p]

4
3 9 2 7

5 3 9 2 7
node 1: value 3, next 2
node 2: value 9, next 3
node 3: value 2, next 4
node 4: value 7, next 0
node 5: value 5, next 1

node 5 อยู่ช่องสุดท้ายของอาเรย์ แต่อยู่หน้าสุดของลิสต์ เพราะลำดับในลิสต์ดูจาก next ไม่ได้ดูจาก index ถ้าโปรแกรมมีบั๊ก ให้พิมพ์ตารางแบบนี้ออกมาดูแล้วไล่ลูกศรด้วยมือ ซึ่งทำได้ง่ายกว่าดูที่อยู่ในหน่วยความจำมาก

ทำไมคนแข่งชอบแบบอาเรย์

• ไม่ต้อง malloc ไม่ต้อง free ไม่มีทางลืม free ไม่มีทางใช้ node หลัง free และไม่มี memory leak
• เร็วกว่า บนเครื่องเดียวกับตารางข้างบน สร้างลิสต์ 10⁶ ตัวด้วยการเพิ่มที่หัวแล้วเดินหนึ่งรอบ แบบ malloc ใช้ประมาณ 0.033 วินาที และ free อีก 0.018 วินาที แบบอาเรย์ใช้ประมาณ 0.004 วินาที ทั้งสองแบบเร็วพอสำหรับโจทย์ทั่วไป แต่แบบอาเรย์ไม่ต้องห่วงเลย
• พังน้อยกว่า ลืมเช็กแล้วไปอ่าน value[0] ได้ค่า 0 กลับมาเฉยๆ ไม่ปิดโปรแกรมด้วย 0xC0000005 แบบ NULL->value ข้อนี้มีสองด้าน คำตอบอาจผิดเงียบๆ แทน
• ดูข้างในง่าย พิมพ์อาเรย์ออกมาตรวจได้ทันทีแบบตัวอย่างข้างบน
• ใช้หมายเลขของข้อมูลเป็น index ได้เลย ถ้าข้อมูลแต่ละตัวมีหมายเลขไม่ซ้ำและไม่ใหญ่เกินอาเรย์ เช่น นักเรียนหมายเลข 1 ถึง N ไม่ต้องมี value[] และหา node ของนักเรียนคนที่ x ได้ทันทีโดยไม่ต้องเดินหา ซึ่งเป็นจุดอ่อนที่เราเจอในหน้า 14.2

ข้อเสียคือต้องรู้ล่วงหน้าว่าจะสร้าง node รวมกันไม่เกินกี่ตัว ซึ่งโจทย์แข่งขันบอกขอบเขตไว้เสมอ

ลิสต์สองทางกับ node 0 ที่ไม่มีวันหาย

หน้า 14.2 ลบ node แต่ละครั้งต้องหา node ก่อนหน้าด้วยการเดิน ถ้าแต่ละ node จำทั้งตัวถัดไปและตัวก่อนหน้า ก็ลบได้ทันที ลิสต์แบบนี้เรียกว่า doubly linked list (ลิสต์สองทาง) แบบอาเรย์ก็แค่เพิ่มอาเรย์ prev[] อีกตัว

เทคนิคที่ทำให้โค้ดสั้นลงมาก คือให้ node 0 เป็นหัวขบวนปลอมที่อยู่ในลิสต์ตลอดเวลา และต่อหัวกับท้ายเข้าหากันเป็นวง next[0] คือตัวแรกจริง prev[0] คือตัวสุดท้ายจริง ลิสต์ว่างคือ next[0] กับ prev[0] เป็น 0 ทั้งคู่ ทุก node จริงจึงมีตัวก่อนหน้าและตัวถัดไปเสมอ การลบหัว ลบท้าย หรือแทรกหน้าสุด ไม่ต้องเขียนกรณีพิเศษเลย

ตัวอย่าง นักเรียนหมายเลข 1 ถึง N เข้าแถวเรียงตามหมายเลข ครูสั่งงานสามแบบ L x นักเรียน x ออกจากแถว F x นักเรียน x ย้ายไปหัวแถว B x นักเรียน x ย้ายไปท้ายแถว ให้พิมพ์แถวสุดท้าย หมายเลขนักเรียนใช้เป็น index ของ node ได้เลย

#include <stdio.h>

int prev[100001];
int next[100001];

void remove_node(int x) // (1)!
{
    next[prev[x]] = next[x];
    prev[next[x]] = prev[x];
}

void insert_after(int p, int x) // (2)!
{
    prev[x] = p;
    next[x] = next[p];
    prev[next[p]] = x;
    next[p] = x;
}

int main()
{
    int n, q;
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; i++) {
        insert_after(prev[0], i); // (3)!
    }
    for (int i = 0; i < q; i++) {
        char command;
        int x;
        scanf(" %c %d", &command, &x);
        remove_node(x);
        if (command == 'F') {
            insert_after(0, x); // (4)!
        } else if (command == 'B') {
            insert_after(prev[0], x);
        }
    }
    for (int p = next[0]; p != 0; p = next[p]) {
        if (p != next[0]) {
            printf(" ");
        }
        printf("%d", p);
    }
    printf("\n");
    return 0;
}

1. ให้ตัวก่อนหน้าเกี่ยวข้าม x ไปหาตัวถัดไป และให้ตัวถัดไปชี้ย้อนข้าม x กลับมา ถ้า x เป็นตัวแรก prev[x] คือ 0 ก็แก้ next[0] ซึ่งก็คือหัวแถว ถูกต้องพอดี
2. สี่เส้นที่เปลี่ยน สองเส้นแรกของ x เอง สองเส้นหลังของเพื่อนบ้าน บรรทัดที่ 16 ต้องมาก่อนบรรทัดที่ 17 เพราะยังต้องใช้ next[p] ค่าเดิม
3. แทรกหลังตัวสุดท้าย คือเพิ่มที่ท้าย ตอนลิสต์ว่าง prev[0] เป็น 0 ก็แทรกหลัง node 0 ได้เหมือนกัน
4. แทรกหลัง node 0 คือขึ้นเป็นหัวแถว

5 4
L 3
F 5
B 1
L 2

5 4 1

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

ลองทำให้พัง ใช้ช่อง 0 เป็น node จริง

ในโปรแกรม array-list เขียน new_node ให้ใช้ช่องก่อนแล้วค่อยเพิ่มตัวนับ ซึ่งดูเป็นธรรมชาติกว่าถ้าเคยชินกับอาเรย์ที่เริ่มจาก 0

#include <stdio.h>

int value[100001];
int next[100001];
int node_count = 0;

int new_node(int v)
{
    value[node_count] = v;
    next[node_count] = 0;
    node_count++;
    return node_count - 1;
}

int main()
{
    int n;
    scanf("%d", &n);
    int head = 0, tail = 0;
    for (int i = 0; i < n; i++) {
        int car;
        scanf("%d", &car);
        int node = new_node(car);
        if (head == 0) {
            head = node;
        } else {
            next[tail] = node;
        }
        tail = node;
    }
    int front = new_node(5);
    next[front] = head;
    head = front;
    for (int p = head; p != 0; p = next[p]) {
        if (p != head) {
            printf(" ");
        }
        printf("%d", value[p]);
    }
    printf("\n");
    return 0;
}

4
3 9 2 7

5 9 2 7

ตู้ 3 หายไปเงียบๆ ไม่มี error ไม่มีคำเตือน ตู้ 3 ได้ node 0 ไป head จึงเป็น 0 ซึ่งแปลว่าลิสต์ยังว่าง พอตู้ 9 มา โปรแกรมเห็นว่าลิสต์ว่างก็ตั้งตู้ 9 เป็นหัวใหม่ ตู้ 3 จึงหลุดจากขบวนตั้งแต่ตอนนั้น ค่าที่ใช้แทน NULL ต้องไม่ใช่ index ของ node จริงเด็ดขาด จะใช้ 0 แล้วเริ่ม node ที่ 1 หรือจะใช้ -1 แทน NULL ก็ได้ แต่ต้องเลือกแบบเดียวแล้วใช้ให้ตรงกันทั้งโปรแกรม

สรุป

• อาเรย์อ่านตัวที่ i ได้ทันที linked list แทรกและลบตรงที่รู้ตำแหน่งได้ทันที โจทย์ส่วนใหญ่ใช้อาเรย์
• linked list ช่วยเฉพาะตอนที่ไม่ต้องเดินหาตำแหน่งก่อน
• ในการแข่งขันนิยมทำ linked list ด้วยอาเรย์ value[] next[] ใช้ index แทน pointer และใช้ 0 แทน NULL โดยเริ่ม node ที่ 1
• อาเรย์ต้องมีช่องพอสำหรับ node ทุกตัวที่เคยสร้าง ไม่ต้อง free
• เพิ่ม prev[] ได้ลิสต์สองทางที่ลบได้ทันที และใช้ node 0 เป็นหัวขบวนปลอมต่อเป็นวง จะไม่มีกรณีพิเศษเลย
• ถ้าหมายเลขข้อมูลไม่ซ้ำและไม่ใหญ่ ใช้หมายเลขนั้นเป็น index ของ node ได้ทันที