โครงสร้างข้อมูล — Array, Linked List, Tree และ Graph

โครงสร้างข้อมูลคือวิธีจัดระเบียบข้อมูล เพื่อให้งานทั่วไปอย่างการค้นหา การแทรก การลบ และการไล่ดูข้อมูลทำได้ง่ายขึ้น ถ้าคุณอยากเข้าใจ array, linked list, tree และ graph วิธีที่เร็วที่สุดคือถาม 2 คำถาม: ข้อมูลมีรูปร่างแบบไหน และการทำงานแบบใดที่ควรมีต้นทุนต่ำ?

ถ้าข้อมูลเป็นลำดับ Array มักเป็นจุดเริ่มต้นที่ดี ถ้าแต่ละรายการชี้ไปยังรายการถัดไปเป็นหลัก linked list อาจเหมาะกว่า ถ้าข้อมูลมีหลายระดับ ให้ใช้ tree ถ้ารายการต่าง ๆ เชื่อมต่อกันได้หลายทิศทาง ให้ใช้ graph

นี่คือกฎสั้นที่สุดที่ยังใช้งานได้จริง:

• Array: เหมาะที่สุดกับลำดับที่เข้าถึงด้วยดัชนี
• Linked list: เหมาะที่สุดกับการเชื่อมต่อแบบลูกโซ่เฉพาะจุด
• Tree: เหมาะที่สุดกับโครงสร้างลำดับชั้น
• Graph: เหมาะที่สุดกับเครือข่าย

Array, linked list, tree และ graph ทำหน้าที่อะไรจริง ๆ

Array เก็บข้อมูลตามลำดับคงที่ และให้คุณอ้างถึงตำแหน่งได้โดยตรง เช่น "รายการที่ $7$" ในการติดตั้งใช้งานแบบเก็บต่อเนื่องตามปกติ การเข้าถึงด้วยดัชนีโดยตรงนี้มีค่าเป็น $O(1)$

Linked list เก็บข้อมูลเป็นโหนด โดยแต่ละโหนดจะชี้ไปยังอีกโหนดหนึ่ง คุณสามารถเดินจากโหนดหนึ่งไปอีกโหนดหนึ่งได้ แต่ถ้าจะไปถึงรายการลำดับที่ $n$ โดยทั่วไปต้องไล่ผ่านโหนดก่อนหน้า ดังนั้นการเข้าถึงตามตำแหน่งจึงมักเป็น $O(n)$

Tree เก็บข้อมูลเป็นระดับ ๆ แต่ละโหนดสามารถมีลูกได้ จึงใช้แทนโครงสร้างที่ซ้อนกันตามธรรมชาติ เช่น โฟลเดอร์ภายในโฟลเดอร์ ต้นทุนของการค้นหาและการอัปเดตขึ้นอยู่กับชนิดของ tree และขึ้นอยู่กับว่ามันยังคงสมดุลหรือไม่

Graph เก็บโหนดและเส้นเชื่อม ต่างจาก tree ตรงที่โหนดหนึ่งสามารถเชื่อมกับอีกหลายโหนดได้อย่างอิสระ และอนุญาตให้มีวงวนได้ ทำให้ graph เป็นแบบจำลองตามธรรมชาติสำหรับถนน โซเชียลเน็ตเวิร์ก และแผนที่ความขึ้นต่อกัน

เปรียบเทียบแบบเร็ว: โครงสร้างข้อมูลแต่ละแบบเหมาะเมื่อไร

Structure	Best mental model	Usually good at	Common limitation
Array	แถวของรายการที่มีหมายเลขกำกับ	เข้าถึงด้วยดัชนีโดยตรง	การแทรกและลบตรงกลางมักต้องเลื่อนข้อมูล
Linked list	โซ่ของโหนด	แทรกหรือลบใกล้โหนดที่รู้อยู่แล้ว	การเข้าถึงแบบสุ่มช้า
Tree	ลำดับชั้นแบบแตกกิ่ง	แทนระดับและความสัมพันธ์แบบพ่อแม่-ลูก	พฤติกรรมขึ้นอยู่กับชนิดของ tree มาก
Graph	เครือข่ายของความเชื่อมโยง	การเข้าถึงได้ เส้นทาง และความสัมพันธ์	อัลกอริทึมมักซับซ้อนกว่า

ตัวอย่างจริง: เลือกโครงสร้างในแอปมหาวิทยาลัยเดียวกัน

สมมติว่าคุณกำลังสร้างแอปมหาวิทยาลัยที่มีหน้าตารางเรียน แคตตาล็อกรายวิชา และแผนที่การเดิน วิธีที่ง่ายที่สุดในการเลือกโครงสร้างข้อมูลคือจับคู่แต่ละฟีเจอร์กับรูปร่างของข้อมูล

แท็บวันธรรมดาในหน้าตารางเรียนมีลักษณะเป็น array โดยธรรมชาติ:

$$[\text{Mon}, \text{Tue}, \text{Wed}, \text{Thu}, \text{Fri}]$$

ฟีเจอร์สำคัญคือการเข้าถึงตามตำแหน่งโดยตรง คำสั่งอย่าง "แสดงแท็บที่ $3$" มีความหมาย และลำดับก็สำคัญ

แคตตาล็อกรายวิชามีลักษณะเป็น tree โดยธรรมชาติ:

$$\text{Department} \rightarrow \text{Course} \rightarrow \text{Section}$$

แต่ละระดับบรรจุระดับถัดไป นี่คือลำดับชั้น ดังนั้น tree จึงเป็นแบบจำลองที่สะอาดที่สุด

ทางเดินระหว่างอาคารมีลักษณะเป็น graph โดยธรรมชาติ อาคารหนึ่งสามารถเชื่อมกับอาคารอื่นได้หลายแห่ง และเส้นทางสามารถวนกลับมาได้ ถ้าคุณต้องการหาเส้นทางที่สั้นที่สุดจากห้องสมุดไปยังห้องแล็บ คุณกำลังแก้ปัญหา graph ไม่ใช่ปัญหา tree

Linked list เหมาะกับส่วนที่แคบกว่าของแอปเดียวกัน เช่น ลำดับของหน้าจอที่เพิ่งเข้าชม ถ้าการทำงานหลักคือเลื่อนไปข้างหน้าหรือย้อนกลับทีละหนึ่งขั้น ในกรณีนั้น แต่ละหน้าจอจำเป็นต้องมีลิงก์ไปยังหน้าจอใกล้เคียงมากกว่าการเข้าถึงหน้าจอลำดับที่ $20$ อย่างรวดเร็ว

บทเรียนสำคัญคือคำว่า "ดีที่สุด" ขึ้นอยู่กับงาน ผลิตภัณฑ์เดียวสามารถใช้โครงสร้างข้อมูลหลายแบบได้ เพราะแต่ละส่วนของข้อมูลมีความสัมพันธ์ต่างกัน

จะแยกความต่างได้อย่างรวดเร็วอย่างไร

นักเรียนจำนวนมากเริ่มเรียนเรื่องนี้ในฐานะคำศัพท์ ทำให้หัวข้อนี้ดูเป็นนามธรรม แต่คำถามเชิงปฏิบัติง่ายกว่านั้นมาก

ให้ถามว่า: การทำงานแบบไหนควรมีต้นทุนต่ำ?

ถ้าคุณต้องการให้ "กระโดดไปยังตำแหน่ง $i$" มีต้นทุนต่ำ array จะเด่นมาก ถ้าคุณต้องการให้ "ตามการเชื่อมต่อถัดไป" มีต้นทุนต่ำ โครงสร้างแบบลิงก์จะช่วยได้ ถ้าคุณต้องการ "เลื่อนลงไปตามลำดับชั้น" tree เหมาะกว่า ถ้าคุณต้องการ "หาว่าสองสิ่งเชื่อมถึงกันหรือไม่" graph เหมาะกว่า

ข้อผิดพลาดที่พบบ่อยเมื่อเรียนโครงสร้างข้อมูล

คิดว่าโครงสร้างหนึ่งเร็วที่สุดเสมอ

ไม่มีผู้ชนะที่ใช้ได้กับทุกกรณี คำว่า "เร็ว" ขึ้นอยู่กับว่าคุณทำอะไรบ่อยที่สุด และขึ้นอยู่กับการติดตั้งใช้งานด้วย

คิดว่า tree มีประสิทธิภาพโดยอัตโนมัติ

Tree บางชนิดรองรับการค้นหาที่มีประสิทธิภาพมาก แต่สิ่งนี้ขึ้นอยู่กับชนิดของ tree และเงื่อนไขของโครงสร้าง เช่น ความสมดุล Tree ที่มีรูปทรงไม่ดีอาจทำงานแย่กว่า tree ที่สมดุลมาก

เลือก linked list เพียงเพราะได้ยินว่าการแทรกราคาถูก

การแทรกอาจมีต้นทุนต่ำได้ก็ต่อเมื่อคุณมีโหนดที่ถูกต้องอยู่แล้ว การหาโหนดนั้นอาจยังต้องใช้เวลา

ใช้ tree ทั้งที่ข้อมูลจริง ๆ เป็น graph

ถ้ารายการหนึ่งมีพ่อแม่ได้หลายตัว มีลิงก์ข้าม หรือมีวงวน การบังคับให้ข้อมูลอยู่ในรูป tree อาจซ่อนโครงสร้างจริง และทำให้การทำงานภายหลังยุ่งยาก

สับสนระหว่างโครงสร้างเชิงนามธรรมกับฟีเจอร์ของภาษาโปรแกรม

คำว่า "array", "list", "map" หรือ "tree" ในภาษาโปรแกรมอาจมาพร้อมตัวเลือกการติดตั้งใช้งานที่ส่งผลต่อการใช้หน่วยความจำและความเร็ว แนวคิดเชิงนามธรรมกับคอนเทนเนอร์ที่ใช้งานจริงเกี่ยวข้องกัน แต่ไม่เหมือนกันเสียทีเดียว

Array, linked list, tree และ graph ถูกใช้เมื่อไร

Array ใช้กับคอลเลกชันที่มีลำดับ ตาราง บัฟเฟอร์ และทุกกรณีที่ตำแหน่งมีความสำคัญ

Linked list ปรากฏในงานติดตั้งใช้งานเฉพาะทางที่การอัปเดตตัวชี้เฉพาะจุดสำคัญกว่าการเข้าถึงแบบสุ่ม

Tree ใช้กับข้อมูลแบบลำดับชั้น เช่น ระบบไฟล์ โครงสร้างเอกสาร expression tree และดัชนีสำหรับการค้นหาหลายชนิด

Graph ใช้กับเส้นทาง การวิเคราะห์ความขึ้นต่อกัน การสร้างแบบจำลองเครือข่าย ลิงก์คำแนะนำ และปัญหาความเชื่อมโยงโดยทั่วไป

จะเลือกโครงสร้างข้อมูลที่เหมาะสมอย่างไร

เริ่มจากถาม 2 คำถาม:

1. ข้อมูลมีความสัมพันธ์แบบใด: ลำดับ ลำดับชั้น หรือเครือข่าย?
2. การทำงานใดสำคัญที่สุด: การเข้าถึงด้วยดัชนี การอัปเดตเฉพาะจุด การไล่ดูตามลำดับชั้น หรือการหาเส้นทาง?

คำตอบสองข้อนี้มักช่วยจำกัดตัวเลือกได้อย่างรวดเร็ว

ถ้าคุณยังไม่แน่ใจ ให้ลองวาดข้อมูลเวอร์ชันเล็ก ๆ ลงบนกระดาษ ภาพที่ได้มักเผยให้เห็นโครงสร้างก่อนที่โค้ดจะบอกคุณ

ลองทำเวอร์ชันของคุณเอง

เลือกตัวอย่างที่คุ้นเคย 3 อย่าง เช่น เพลย์ลิสต์ ระบบโฟลเดอร์ และแผนที่ขนส่ง ระบุว่าแต่ละอย่างมีลักษณะหลักเป็นลำดับ ลำดับชั้น หรือเครือข่าย จากนั้นเลือกโครงสร้างที่ทำให้การทำงานหลักง่ายขึ้น ถ้าคุณอยากได้กรณีเพิ่มเติมไว้ทดสอบตัวเอง GPAI Solver สามารถสร้างตัวอย่างการจำแนกประเภทที่คล้ายกันได้