สรุปโครงสร้างข้อมูล

หน้านี้เป็น เอกสารอ้างอิงด่วน (cheat sheet) ไม่ใช่บทเรียน — เปิดทิ้งไว้ข้างจอตอนแก้โจทย์หรือเตรียมสอบได้เลย ด้านล่างคือตารางสรุปโครงสร้างข้อมูลที่หลักสูตรครอบคลุม พร้อมช่วงการอบรมที่เกี่ยวข้อง ตามด้วย ตารางต้นทุนหลัก (master cost table) ที่ลงลึกทุกปฏิบัติการ ของจริงใน Python และกับดักที่พบบ่อยของแต่ละโครงสร้าง

ตารางสรุปช่วงการอบรม

โครงสร้างข้อมูล	แนวคิดและคุณสมบัติสำคัญ	ความซับซ้อนเด่น	ช่วง
อาเรย์และลิสต์	จัดเก็บข้อมูลต่อเนื่อง เข้าถึงด้วยดัชนี	เข้าถึง `O(1)` · แทรกกลาง `O(n)`	๑.๔
สตริง	ลำดับของอักขระ มองเป็นอาเรย์ชนิดหนึ่ง	เข้าถึง `O(1)`	๑.๔
ลิงก์ลิสต์	ปมเชื่อมด้วยตัวชี้ ยืดหยุ่นต่อการแทรก/ลบ	แทรก/ลบ `O(1)` ณ ตำแหน่งที่ทราบ · ค้นหา `O(n)`	๒.๑
สแตก	เข้าหลังออกก่อน (LIFO) — undo, การเรียกซ้ำ	push/pop `O(1)`	๒.๑
คิว	เข้าก่อนออกก่อน (FIFO) — การจัดลำดับงาน	enqueue/dequeue `O(1)`	๒.๑
ตารางแฮช / พจนานุกรม	คู่คีย์–ค่า ค้นคืนรวดเร็ว โครงสร้างหลักของซอฟต์แวร์จริง	ค้นหา/แทรกเฉลี่ย `O(1)`	๒.๒
ต้นไม้ทวิภาค	โครงสร้างลำดับชั้น แต่ละปมมีลูกได้ไม่เกินสอง	ขึ้นกับความสูง	๒.๓
ต้นไม้ค้นหาแบบทวิภาค	ซ้ายน้อยกว่า ขวามากกว่า	ค้นหา `O(log n)` เมื่อสมดุล	๒.๓
กราฟ	แบบจำลองความสัมพันธ์ระหว่างปม	ขึ้นกับจำนวนปมและเส้นเชื่อม	๓.๓

เคล็ดลับการเลือกใช้: ดู การเลือกโครงสร้างข้อมูลให้เหมาะสมกับปัญหา

ตารางต้นทุนหลัก (Master Operation-Cost Table)

ตัวย่อ: n = จำนวนสมาชิก · เวลาทั้งหมดเป็น worst-case เว้นแต่ระบุว่า เฉลี่ย

โครงสร้าง	เข้าถึง (index)	ค้นหา	แทรก	ลบ	พื้นที่
อาเรย์ (fixed-size)	`O(1)`	`O(n)`	ไม่รองรับ (ขนาดคงที่)	ไม่รองรับ	`O(n)`
อาเรย์พลวัต (dynamic array)	`O(1)`	`O(n)`	ท้าย: `O(1)` เฉลี่ย · กลาง: `O(n)`	ท้าย: `O(1)` · กลาง: `O(n)`	`O(n)`
ลิงก์ลิสต์เดี่ยว (singly linked list)	`O(n)`	`O(n)`	หัว: `O(1)` · ทราบตำแหน่ง: `O(1)`	หัว: `O(1)` · ทราบตำแหน่ง: `O(1)`	`O(n)`
ลิงก์ลิสต์คู่ (doubly linked list)	`O(n)`	`O(n)`	หัว/ท้าย: `O(1)` · ทราบตำแหน่ง: `O(1)`	หัว/ท้าย: `O(1)` · ทราบตำแหน่ง: `O(1)`	`O(n)`
สแตก (stack)	`O(n)`*	`O(n)`*	push `O(1)`	pop `O(1)`	`O(n)`
คิว (queue)	`O(n)`*	`O(n)`*	enqueue `O(1)`	dequeue `O(1)`	`O(n)`
ดีคิว (deque)	`O(n)`*	`O(n)`*	หัว/ท้าย `O(1)`	หัว/ท้าย `O(1)`	`O(n)`
ตารางแฮช (hash table)	ไม่มีดัชนี	เฉลี่ย `O(1)` · แย่สุด `O(n)`	เฉลี่ย `O(1)` · แย่สุด `O(n)`	เฉลี่ย `O(1)` · แย่สุด `O(n)`	`O(n)`
ต้นไม้ค้นหาแบบทวิภาค (BST)	—	`O(h)` แย่สุด `O(n)`	`O(h)` แย่สุด `O(n)`	`O(h)` แย่สุด `O(n)`	`O(n)`
BST สมดุล (AVL / Red-Black)	—	`O(log n)`	`O(log n)`	`O(log n)`	`O(n)`
ฮีป (binary heap)	min/max `O(1)`	`O(n)`	`O(log n)`	ดึงราก `O(log n)`	`O(n)`

* สแตก/คิว/ดีคิวมักไม่ได้ออกแบบมาให้ค้นหา/เข้าถึงกลาง — ถ้าต้องทำแบบนั้นบ่อย แปลว่าเลือกโครงสร้างผิดตั้งแต่แรก

ทำไมอาเรย์พลวัตถึง “amortized O(1)”: เวลา append ส่วนใหญ่คือ O(1) เพราะมีที่ว่างเหลืออยู่ แต่พอเต็มพอดี ต้องจอง หน่วยความจำก้อนใหม่ (เช่น เพิ่มเป็น ๒ เท่า) แล้วคัดลอกของเก่าทั้งหมด — ครั้งนั้นคือ O(n) แต่มันเกิดขึ้นไม่บ่อย เฉลี่ยรวมทุกการ append จึงยังเป็น O(1) ต่อครั้ง

รายละเอียดทีละโครงสร้าง

อาเรย์ / อาเรย์พลวัต

ใช้เมื่อ: ต้องเข้าถึงด้วยดัชนีบ่อย ขนาดรู้คร่าวๆ ล่วงหน้า หรือเน้น cache-locality (อ่านต่อเนื่องเร็วกว่าลิงก์ลิสต์มาก) หลีกเลี่ยงเมื่อ: ต้องแทรก/ลบกลางลิสต์บ่อยๆ ในข้อมูลขนาดใหญ่

Python built-in: list (dynamic array อยู่แล้วในตัว)
กับดักที่พบบ่อย: list.insert(0, x) หรือ list.pop(0) คือ O(n) เพราะต้องเลื่อนสมาชิกทุกตัว — ถ้าต้องเข้า/ออกที่หัวบ่อย ให้ใช้ collections.deque แทน ไม่ใช่ list

ลิงก์ลิสต์ (เดี่ยว/คู่)

ใช้เมื่อ: แทรก/ลบบ่อยที่หัวหรือ ณ ตำแหน่งที่มีตัวชี้อยู่แล้ว (เช่น implement คิว/สแตกเอง, LRU cache) หลีกเลี่ยงเมื่อ: ต้องเข้าถึงสมาชิกตัวที่ k บ่อยๆ — ต้องไล่ทีละปมเสมอ ไม่มีทางลัด

Python built-in: ไม่มีในตัวโดยตรง — collections.deque ใช้ doubly linked list ภายในและครอบคลุมการใช้งานส่วนใหญ่
กับดักที่พบบ่อย: ลืมอัปเดตตัวชี้ tail/prev ตอนแทรกหรือลบที่ปลาย ทำให้ลิสต์ขาดหรือวนลูปไม่รู้จบ

สแตก (Stack)

ใช้เมื่อ: ต้องย้อนกลับลำดับล่าสุดก่อน (undo, ตรวจวงเล็บ, backtracking, call stack ของการเรียกซ้ำ) หลีกเลี่ยงเมื่อ: ต้องเข้าถึงสมาชิกที่ไม่ใช่ยอดบนสุด

Python built-in: list (append/pop ที่ท้ายลิสต์คือ O(1))
กับดักที่พบบ่อย: ใช้ list.pop(0) แทน list.pop() โดยไม่ทันสังเกต — เผลอทำสแตกให้กลายเป็น O(n) ต่อครั้ง

คิว (Queue) และดีคิว (Deque)

ใช้เมื่อ: ต้องประมวลผลตามลำดับที่เข้ามาก่อน (BFS, task scheduling, สตรีมข้อมูล) หลีกเลี่ยงเมื่อ: ต้องการ LIFO (ใช้สแตกแทน) หรือไม่สนลำดับเลย (list ธรรมดาพอ)

Python built-in: collections.deque — popleft()/appendleft() เป็น O(1) จริง ต่างจาก list
กับดักที่พบบ่อย: ใช้ list เป็นคิวด้วย pop(0) — ได้ผลลัพธ์ถูกต้องแต่ช้าเป็น O(n) ต่อการ dequeue หนึ่งครั้ง พอ n ใหญ่ โปรแกรมจะคลานเดี๋ยวไม่รู้สาเหตุ

ตารางแฮช (Hash Table) / พจนานุกรม

ใช้เมื่อ: ต้องค้นหา/แทรก/ลบด้วยคีย์เร็วที่สุด ไม่สนลำดับของข้อมูล (นับความถี่, cache, index แบบ key→value) หลีกเลี่ยงเมื่อ: ต้องการลำดับที่คงที่ (ใช้ list หรือ dict ที่รักษาลำดับการแทรกได้ใน Python 3.7+ แต่ไม่ใช่ลำดับ “เรียงแล้ว”) หรือต้องการช่วงค่า/เรียงลำดับ (range query → ใช้ BST/ต้นไม้แทน)

Python built-in: dict, set
กับดักที่พบบ่อย: ใช้ key เป็น object ที่ mutable (เช่น list) — ใช้เป็นคีย์ dict ไม่ได้เพราะ hash เปลี่ยนได้; หรือมองข้าม worst case O(n) เมื่อเกิด hash collision จำนวนมาก (โดนโจมตีแบบ hash-flooding ได้ถ้าคีย์มาจาก user input โดยตรง)

ต้นไม้ค้นหาแบบทวิภาค (BST) และ BST สมดุล

ใช้เมื่อ: ต้องการทั้งค้นหาเร็วและคงลำดับไว้ได้ (in-order traversal คือข้อมูลที่เรียงแล้ว), ต้องการ range query, หาค่า min/max ถัดไป หลีกเลี่ยงเมื่อ: แค่ต้องการค้นหาด้วยคีย์อย่างเดียวไม่สนลำดับ — ตารางแฮชเร็วกว่าและง่ายกว่า

Python built-in: ไม่มี BST ในตัว — ใช้ sortedcontainers.SortedList (ภายนอก) หรือโมดูล bisect กับ list ที่เรียงแล้ว สำหรับ range query แบบง่าย
กับดักที่พบบ่อย: ลืมสมดุลต้นไม้ — แทรกข้อมูลที่เรียงแล้วเข้า BST ธรรมดาไปเรื่อยๆ จะได้ต้นไม้ที่หน้าตาเหมือนลิงก์ลิสต์ (ความสูง O(n)) ทำให้ทุกปฏิบัติการกลายเป็น O(n) ทั้งที่ตั้งใจให้เป็น O(log n)

ฮีป (Binary Heap) / Priority Queue

ใช้เมื่อ: ต้องดึงค่าที่เล็กสุด/ใหญ่สุดซ้ำๆ เร็ว (priority queue, Dijkstra, heap sort, top-k) หลีกเลี่ยงเมื่อ: ต้องค้นหาสมาชิกที่ไม่ใช่ราก — ฮีปไม่รองรับการค้นหาทั่วไปแบบ O(log n)

Python built-in: heapq (min-heap เท่านั้น — ทำ max-heap ได้ด้วยการใส่ค่าติดลบ)
กับดักที่พบบ่อย: คิดว่า heapq.heappop() คืนค่าตามลำดับที่ใส่เข้าไป (ไม่ใช่ — คืนค่าน้อยสุดเสมอ) และลืมว่าฮีปไม่ใช่โครงสร้างที่เรียงสมบูรณ์ — แค่รากเท่านั้นที่การันตีว่าเล็กสุด

ตารางเทียบ Python built-in โดยสรุป

ต้องการ…	ใช้	ไม่ใช่
อาเรย์พลวัต	`list`	—
สแตก	`list` (`append`/`pop`)	`collections.deque` ก็ได้แต่ `list` พอ
คิว / ดีคิว	`collections.deque`	`list` (`pop(0)` ช้า)
คู่คีย์–ค่า	`dict`	—
เซตไม่ซ้ำ	`set`	`list` แล้วเช็ค `in` เอง (ช้ากว่ามาก)
priority queue	`heapq`	เรียง `list` ใหม่ทุกครั้ง
ข้อมูลเรียงลำดับ + ค้นหาเร็ว	`bisect` + `list` หรือ `sortedcontainers.SortedList`	BST มือเขียนเอง (เว้นแต่กำลังฝึก)

กติกาทองคำ: ก่อนเขียนโครงสร้างข้อมูลเองใน Python ให้เช็ค collections, heapq, bisect ก่อนเสมอ — ส่วนใหญ่มีให้แล้วและผ่านการ optimize มาอย่างดี

เจาะลึกเพิ่มเติม

MIT 6.006 — Introduction to Algorithms — บทเรียนปูพื้นโครงสร้างข้อมูลแบบเป็นระบบ
Stanford CS161 — เชื่อมโยงโครงสร้างข้อมูลกับการวิเคราะห์ความซับซ้อนอย่างเข้มข้น
Harvard CS50 — อธิบายด้วยภาพและตัวอย่างเข้าใจง่ายสำหรับผู้เริ่มต้น
CLRS (Cormen, Leiserson, Rivest, Stein) Introduction to Algorithms 4th ed. — ตำราอ้างอิงมาตรฐาน มีบทเฉพาะสำหรับ heap (บทที่ ๖), hash table (บทที่ ๑๑), BST (บทที่ ๑๒), red-black tree (บทที่ ๑๓)
Sedgewick & Wayne Algorithms 4th ed. — โค้ด implementation จริงของทุกโครงสร้างในตารางนี้ พร้อมการวิเคราะห์ amortized cost ของ dynamic array อย่างละเอียด
Weiss Data Structures and Algorithm Analysis — เจาะลึกเรื่อง hashing (การจัดการ collision หลายแบบ) และ balanced tree ได้ดีเป็นพิเศษ
Goodrich, Tamassia & Goldwasser Data Structures and Algorithms in Python — ใช้ภาษา Python ตรงกับหลักสูตรนี้ เทียบ built-in กับโครงสร้างที่สอนได้ตรงตัว
Big-O Cheat Sheet (bigocheatsheet.com) — ตารางเทียบความซับซ้อนแบบเดียวกับหน้านี้ ใช้ทบทวนคู่กันได้

เคล็ดลับการเลือกใช้: ดู การเลือกโครงสร้างข้อมูลให้เหมาะสมกับปัญหา