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

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

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

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

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

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

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