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