อาร์เรย์เทียบกับรายการที่เชื่อมโยง
อาร์เรย์คือโครงสร้างข้อมูลที่ใช้บ่อยที่สุดในการจัดเก็บคอลเลกชันขององค์ประกอบ ภาษาโปรแกรมส่วนใหญ่มีวิธีการประกาศอาร์เรย์และการเข้าถึงองค์ประกอบในอาร์เรย์อย่างง่ายดาย รายการที่เชื่อมโยง ซึ่งเป็นรายการที่เชื่อมโยงอย่างตรงไปตรงมายิ่งขึ้น ยังเป็นโครงสร้างข้อมูลที่สามารถใช้จัดเก็บคอลเลกชันขององค์ประกอบได้ ประกอบด้วยลำดับของโหนดและแต่ละโหนดมีการอ้างอิงไปยังโหนดถัดไปในลำดับ
แสดงในรูปที่ 1 เป็นโค้ดที่ปกติใช้ในการประกาศและกำหนดค่าให้กับอาร์เรย์ รูปที่ 2 แสดงให้เห็นว่าอาร์เรย์จะมีลักษณะอย่างไรในหน่วยความจำ
เหนือโค้ดกำหนดอาร์เรย์ที่สามารถเก็บจำนวนเต็ม 5 จำนวนและเข้าถึงได้โดยใช้ดัชนี 0 ถึง 4 คุณสมบัติที่สำคัญอย่างหนึ่งของอาร์เรย์คืออาร์เรย์ทั้งหมดได้รับการจัดสรรเป็นบล็อกหน่วยความจำเดียว และแต่ละองค์ประกอบจะมีพื้นที่ของตัวเอง ในอาร์เรย์ เมื่อกำหนดอาร์เรย์แล้ว ขนาดของอาร์เรย์จะคงที่ ดังนั้น หากคุณไม่แน่ใจเกี่ยวกับขนาดของอาร์เรย์ในขณะคอมไพล์ คุณจะต้องกำหนดอาร์เรย์ที่ใหญ่พอที่จะอยู่ในด้านที่ปลอดภัย แต่โดยส่วนใหญ่แล้วเราจะใช้องค์ประกอบน้อยกว่าที่เราจัดสรรไว้ ดังนั้นหน่วยความจำจำนวนมากจึงสูญเปล่าจริง ๆ ในทางกลับกัน ถ้า “อาร์เรย์ที่ใหญ่เพียงพอ” ไม่ใหญ่พอจริง ๆ โปรแกรมก็จะขัดข้อง
รายการที่เชื่อมโยงจะจัดสรรหน่วยความจำให้กับองค์ประกอบแยกกันในบล็อกหน่วยความจำของตัวเอง และโครงสร้างโดยรวมได้มาจากการเชื่อมโยงองค์ประกอบเหล่านี้เป็นลิงก์ในสายโซ่แต่ละองค์ประกอบในรายการที่เชื่อมโยงมีสองฟิลด์ดังแสดงในรูปที่ 3 ฟิลด์ข้อมูลเก็บข้อมูลจริงที่จัดเก็บและฟิลด์ถัดไปเก็บการอ้างอิงไปยังองค์ประกอบถัดไปในสายโซ่ องค์ประกอบแรกของรายการที่เชื่อมโยงจะถูกเก็บไว้เป็นส่วนหัวของรายการที่เชื่อมโยง
| data | ต่อไป |
รูปที่ 3: องค์ประกอบของรายการที่เชื่อมโยง
รูปที่ 4 แสดงรายการที่เชื่อมโยงที่มีสามองค์ประกอบ แต่ละองค์ประกอบเก็บข้อมูลและองค์ประกอบทั้งหมดยกเว้นองค์ประกอบสุดท้ายจะเก็บข้อมูลอ้างอิงไปยังองค์ประกอบถัดไป องค์ประกอบสุดท้ายมีค่าว่างในฟิลด์ถัดไป องค์ประกอบใด ๆ ในรายการสามารถเข้าถึงได้โดยเริ่มต้นที่ส่วนหัวและทำตามตัวชี้ถัดไปจนกว่าคุณจะพบกับองค์ประกอบที่ต้องการ
แม้ว่าอาร์เรย์และรายการที่เชื่อมโยงจะคล้ายคลึงกันในแง่ที่ว่าทั้งคู่ถูกใช้เพื่อจัดเก็บคอลเลกชันขององค์ประกอบ แต่ก็มีความแตกต่างกันเนื่องจากกลยุทธ์ที่ใช้ในการจัดสรรหน่วยความจำให้กับองค์ประกอบ อาร์เรย์จะจัดสรรหน่วยความจำให้กับองค์ประกอบทั้งหมดเป็นบล็อกเดียว และจะต้องกำหนดขนาดของอาร์เรย์เมื่อรันไทม์ ซึ่งจะทำให้อาร์เรย์ไม่มีประสิทธิภาพในสถานการณ์ที่คุณไม่ทราบขนาดของอาร์เรย์ในขณะรวบรวม เนื่องจากรายชื่อที่เชื่อมโยงจัดสรรหน่วยความจำให้กับองค์ประกอบแยกกัน มันจะมีประสิทธิภาพมากในสถานการณ์ที่คุณไม่ทราบขนาดของรายการในขณะรวบรวม การประกาศและการเข้าถึงองค์ประกอบในรายการที่เชื่อมโยงจะไม่ตรงไปตรงมา เมื่อเทียบกับวิธีที่คุณเข้าถึงองค์ประกอบในอาร์เรย์โดยตรงโดยใช้ดัชนี