โครงสร้างข้อมูล คือวิธีการจัดระเบียบและจัดเก็บข้อมูลในหน่วยความจำเพื่อให้สามารถเข้าถึงและแก้ไขได้อย่างมีประสิทธิภาพ ประเภทข้อมูลนามธรรม (ADT) คือ โมเดลตรรกะ — การดำเนินการและพฤติกรรมของมัน — โดยไม่ขึ้นกับวิธีการนำไปใช้งาน
ADT อธิบาย ที่มีอยู่ โครงสร้างข้อมูลตัดสินใจ ที่เก็บไว้และความเร็วในการเรียกใช้
ADT: Stack → push, pop, peek (LIFO behavior)
Implementations: → array-backed OR linked-list-backed
ADT: List → get(i), insert, remove
Implementations: → dynamic array OR linked list
# Both satisfy the "Stack" ADT, but have different cost profiles
stack = [] # list-backed stack
stack.append(10) # push -> amortized O(1)
top = stack[-1] # peek -> O(1)
stack.pop() # pop -> O(1)
| ข้อกังวล | คำถามที่ต้องถาม |
|---|---|
| รูปแบบการเข้าถึง | การเข้าถึงแบบสุ่มหรือตามลำดับ? |
| การแก้ไข | ใส่/ลบบ่อยครั้งตรงกลาง? |
| การเรียงลำดับ | เรียงลำดับ FIFO LIFO หรือไม่มี? |
| การค้นหา | ตามดัชนีหรือตามคีย์? |
ตัวเลือกที่ถูกต้องคือตัวที่มี การดำเนินการทั่วไปราคาถูก สำหรับภาระงานของคุณ
การเลือกโครงสร้างที่ผิดจะเปลี่ยนการดำเนินการ O(1) เป็น O(n) ซึ่งสามารถทำให้โค้ดช้าลงหลายพันครั้งในระดับที่ใหญ่
การคิดในแง่ของ ADT ช่วยให้คุณสามารถให้เหตุผลเกี่ยวกับ พฤติกรรม ก่อน จากนั้นจึงสามารถสลับการนำไปใช้งานในภายหลังโดยไม่ต้องเขียนโปรแกรมใหม่