อาร์เรย์และรายการโยง

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

Definition

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

Scope

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

Core questions

• เมื่อใดที่การจัดเก็บแบบต่อเนื่อง (อาร์เรย์) มีประสิทธิภาพเหนือกว่าการจัดเก็บแบบเชื่อมโยงด้วยพอยน์เตอร์ (รายการ)?
• อาร์เรย์แบบไดนามิกบรรลุการผนวกในเวลาคงที่แบบถัวเฉลี่ยได้อย่างไร แม้ว่าจะมีการปรับขนาดเป็นครั้งคราว?
• การแลกเปลี่ยนต้นทุนระหว่างอาร์เรย์กับรายการโยงสำหรับการแทรก การลบ และการเข้าถึงคืออะไร?
• สแตกและคิวถูกนำไปใช้บนโครงสร้างเหล่านี้ได้อย่างไร?
• การจัดวางหน่วยความจำส่งผลต่อประสิทธิภาพในโลกแห่งความเป็นจริงผ่านพฤติกรรมแคชอย่างไร?

Key concepts

• หน่วยความจำต่อเนื่อง
• การเข้าถึงด้วยดัชนี
• การปรับขนาดอาร์เรย์แบบไดนามิก
• รายการโยงแบบเดี่ยวและแบบคู่
• สแตก (LIFO)
• คิว (FIFO)
• ต้นทุนถัวเฉลี่ย
• ตำแหน่งแคช

Key theories

การเข้าถึงแบบสุ่มเทียบกับการเชื่อมโยงตามลำดับ

อาร์เรย์รองรับการเข้าถึงด้วยดัชนีแบบ O(1) แต่การแทรกหรือลบตรงกลางแบบ O(n) ในขณะที่รายการโยงรองรับการเชื่อมต่อแบบ O(1) เมื่อมีโหนด แต่การเข้าถึงตามตำแหน่งแบบ O(n) การเลือกที่เหมาะสมขึ้นอยู่กับการผสมผสานของการดำเนินการ

การเติบโตแบบถัวเฉลี่ยของอาร์เรย์แบบไดนามิก

อาร์เรย์แบบไดนามิกที่เพิ่มความจุเป็นสองเท่าเมื่อเต็มจะมีการคัดลอกแบบ O(n) เป็นครั้งคราว แต่จะถัวเฉลี่ยเป็น O(1) ต่อการผนวกตลอดลำดับของการดำเนินการใดๆ โดยใช้วิธีรวมหรือวิธีศักยภาพ

Clinical relevance

อาร์เรย์และรายการเป็นพื้นฐานของโปรแกรมเกือบทุกโปรแกรม: อาร์เรย์แบบไดนามิกใช้ในการสร้างชนิดรายการ/เวกเตอร์เริ่มต้นในภาษาโปรแกรมส่วนใหญ่ คิวเป็นพื้นฐานของการจัดตารางเวลาและการค้นหาแบบกว้าง สแตกเป็นพื้นฐานของการจัดการการเรียกใช้ฟังก์ชันและการประเมินนิพจน์ และการแลกเปลี่ยนระหว่างอาร์เรย์กับรายการเป็นการตัดสินใจออกแบบเชิงปฏิบัติทั่วไปที่ส่งผลต่อประสิทธิภาพ

History

อาร์เรย์เป็นหนึ่งในโครงสร้างข้อมูลแรกๆ ที่มีอยู่ในภาษาโปรแกรมแรกๆ และรายการโยงถูกนำมาใช้สำหรับการประมวลผลเชิงสัญลักษณ์และรายการ (โดยเฉพาะใน IPL ของ Newell, Shaw และ Simon และต่อมาคือ Lisp) ในช่วงปลายทศวรรษ 1950 การวิเคราะห์อย่างเป็นระบบของ Knuth ใน The Art of Computer Programming ได้สร้างการวิเคราะห์ที่เป็นมาตรฐานขึ้นมา

Key figures

• Donald Knuth
• Robert Sedgewick

Seminal works

• knuth1997vol1
• cormen2009

Frequently asked questions

ทำไมถึงใช้รายการโยงในเมื่ออาร์เรย์รองรับการเข้าถึงแบบสุ่มที่รวดเร็ว?

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

ทำไมการผนวกอาร์เรย์จึงถือว่าใช้เวลาคงที่ หากการปรับขนาดคัดลอกทุกอย่าง?

การปรับขนาดเกิดขึ้นไม่บ่อยนักเนื่องจากความจุมักจะเพิ่มเป็นสองเท่า ดังนั้นงานคัดลอกทั้งหมดตลอดการผนวก n ครั้งจึงเป็นสัดส่วนกับ n เมื่อกระจายไปทั่วการผนวกทั้งหมด จะให้ต้นทุนคงที่แบบถัวเฉลี่ยต่อการผนวก แม้ว่าการปรับขนาดแต่ละครั้งจะเป็น O(n) ก็ตาม