รายการที่เชื่อมโยงแบบเดี่ยว vs รายการเชื่อมโยงแบบทวีคูณ
รายการที่เชื่อมโยงเป็นโครงสร้างข้อมูลเชิงเส้นที่ใช้เพื่อจัดเก็บชุดข้อมูล รายการที่เชื่อมโยงจะจัดสรรหน่วยความจำให้กับองค์ประกอบแยกกันในบล็อกหน่วยความจำของตัวเอง และโครงสร้างโดยรวมได้มาจากการเชื่อมโยงองค์ประกอบเหล่านี้เป็นลิงก์ในสายโซ่ รายการที่เชื่อมโยงอย่างเดียวประกอบด้วยลำดับของโหนด และแต่ละโหนดมีการอ้างอิงไปยังโหนดถัดไปในลำดับ รายการที่เชื่อมโยงแบบทวีคูณประกอบด้วยลำดับของโหนดซึ่งแต่ละโหนดมีการอ้างอิงไปยังโหนดถัดไปและโหนดก่อนหน้า
รายการลิงค์เดี่ยว
แต่ละองค์ประกอบในรายการที่เชื่อมโยงเพียงอย่างเดียวมีสองฟิลด์ดังแสดงในรูปที่ 1 ฟิลด์ข้อมูลเก็บข้อมูลจริงที่เก็บไว้และฟิลด์ถัดไปเก็บการอ้างอิงไปยังองค์ประกอบถัดไปในสายโซ่ องค์ประกอบแรกของรายการที่เชื่อมโยงจะถูกเก็บไว้เป็นส่วนหัวของรายการที่เชื่อมโยง
รูปที่ 2 แสดงรายการที่เชื่อมโยงโดยลำพังที่มีสามองค์ประกอบ แต่ละองค์ประกอบเก็บข้อมูลและองค์ประกอบทั้งหมดยกเว้นองค์ประกอบสุดท้ายจะเก็บข้อมูลอ้างอิงไปยังองค์ประกอบถัดไป องค์ประกอบสุดท้ายมีค่าว่างในฟิลด์ถัดไป องค์ประกอบใด ๆ ในรายการสามารถเข้าถึงได้โดยเริ่มต้นที่ส่วนหัวและทำตามตัวชี้ถัดไปจนกว่าคุณจะพบกับองค์ประกอบที่ต้องการ
รายการเชื่อมโยงทวีคูณ
แต่ละองค์ประกอบในรายการเชื่อมโยงแบบทวีคูณมีสามฟิลด์ดังแสดงในรูปที่ 3ฟิลด์ข้อมูลจะเก็บข้อมูลจริงที่จัดเก็บไว้ เช่นเดียวกับรายการที่เชื่อมโยงอย่างเดียว และฟิลด์ถัดไปจะเก็บข้อมูลอ้างอิงไปยังองค์ประกอบถัดไปในห่วงโซ่ นอกจากนี้ ฟิลด์ก่อนหน้าจะมีการอ้างอิงถึงองค์ประกอบก่อนหน้าในเชน องค์ประกอบแรกของรายการที่เชื่อมโยงจะถูกเก็บไว้เป็นส่วนหัวของรายการที่เชื่อมโยง
รูปที่ 4 แสดงรายการที่เชื่อมโยงแบบทวีคูณที่มีสามองค์ประกอบ องค์ประกอบระดับกลางทั้งหมดเก็บการอ้างอิงถึงองค์ประกอบแรกและองค์ประกอบก่อนหน้า องค์ประกอบสุดท้ายในรายการเก็บค่า Null ในฟิลด์ถัดไป และองค์ประกอบแรกในรายการเก็บค่า Null ในฟิลด์ก่อนหน้า รายการที่เชื่อมโยงแบบทวีคูณสามารถข้ามไปข้างหน้าได้โดยทำตามการอ้างอิงถัดไปในแต่ละองค์ประกอบ และสามารถย้อนกลับในทำนองเดียวกันได้โดยใช้ข้อมูลอ้างอิงก่อนหน้าในแต่ละองค์ประกอบ
รายการเชื่อมโยงแบบเดี่ยวและรายการที่เชื่อมโยงเป็นสองเท่าแตกต่างกันอย่างไร
แต่ละองค์ประกอบในรายการที่เชื่อมโยงโดยลำพังมีการอ้างอิงไปยังองค์ประกอบถัดไปในรายการ ในขณะที่องค์ประกอบในรายการที่เชื่อมโยงแบบทวีคูณจะมีการอ้างอิงไปยังองค์ประกอบถัดไปและองค์ประกอบก่อนหน้าในรายการ รายการที่เชื่อมโยงแบบทวีคูณต้องการพื้นที่มากขึ้นสำหรับแต่ละองค์ประกอบในรายการ และการดำเนินการเบื้องต้น เช่น การแทรกและการลบนั้นซับซ้อนกว่า เนื่องจากต้องจัดการกับการอ้างอิงสองรายการ แต่รายการลิงก์แบบทวีคูณช่วยให้จัดการได้ง่ายขึ้นเนื่องจากช่วยให้สามารถข้ามรายการในทิศทางไปข้างหน้าและย้อนกลับได้