โครงสร้างข้อมูลใน C/C++

Singly Linked List

สร้าง วน และทำลาย linked list

Singly Linked List คืออะไร?

แต่ละ node เก็บ value และ link ไป node ถัดไป

ประเด็นสำคัญ

  • กำหนด invariant ก่อนเขียน operation
  • จัดการกรณีว่าง เต็ม และ allocation ล้มเหลว
  • ประเมิน complexity และ ownership พร้อมกัน

ดูการทำงาน

เพิ่มโหนดที่หัวหรือท้าย และคลิกโหนดเพื่อลบ กด เล่น เพื่อเดินตามพอยน์เตอร์ next จาก head ถึง NULL

ตัวอย่างโค้ด C และ C++

C
รันโค้ด →
main.c
#include <stdio.h>
#include <stdlib.h>

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

int main(void) {
    Node *head = NULL;
    for (int value = 3; value >= 1; --value) {
        Node *node = malloc(sizeof *node);
        if (!node) return 1;
        *node = (Node){value, head};
        head = node;
    }
    while (head) {
        Node *next = head->next;
        printf("%d ", head->value);
        free(head);
        head = next;
    }
    puts("");
    return 0;
}
ผลลัพธ์ที่คาดหวัง
1 2 3
C++
รันโค้ด →
main.cpp
#include <iostream>
#include <memory>

struct Node {
    int value;
    std::unique_ptr<Node> next;
};

int main() {
    std::unique_ptr<Node> head;
    for (int value = 3; value >= 1; --value) {
        head = std::make_unique<Node>(Node{value, std::move(head)});
    }
    for (Node *node = head.get(); node; node = node->next.get()) {
        std::cout << node->value << ' ';
    }
    std::cout << '\n';
}
ผลลัพธ์ที่คาดหวัง
1 2 3

เปรียบเทียบ C และ C++

C malloc และ free ทุก node ส่วน C++ unique_ptr ปล่อยทั้ง chain เมื่อ head ถูกทำลาย

C

Struct และ operation แยกกัน การจัดสรรชัดเจน

C++

Class และ container รักษา invariant และ resource

แบบฝึกหัด

รันทั้งสองเวอร์ชันแล้วแก้ไขเพื่อสังเกตความแตกต่างของภาษา

  • ทดสอบสถานะว่างและเต็ม
  • เขียน cleanup และตรวจ memory leak
  • เปรียบเทียบกับ standard container

ฝึกด้วยโจทย์

ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI

โจทย์ทั้งหมด