Singly Linked List
สร้าง วน และทำลาย linked list
Singly Linked List คืออะไร?
แต่ละ node เก็บ value และ link ไป node ถัดไป
ประเด็นสำคัญ
- กำหนด invariant ก่อนเขียน operation
- จัดการกรณีว่าง เต็ม และ allocation ล้มเหลว
- ประเมิน complexity และ ownership พร้อมกัน
ดูการทำงาน
เพิ่มโหนดที่หัวหรือท้าย และคลิกโหนดเพื่อลบ กด เล่น เพื่อเดินตามพอยน์เตอร์ next จาก head ถึง NULL
ตัวอย่างโค้ด 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
- การดำเนินการกับลิงก์ลิสต์ จำลองลิงก์ลิสต์: เพิ่มที่ปลายทั้งสองด้าน ลบจากหัวหรือตามค่า และกลับลำดับ ง่าย