רשימה מקושרת יחידה לעומת רשימה מקושרת כפולה
רשימה מקושרת היא מבנה נתונים ליניארי המשמש לאחסון אוסף נתונים. רשימה מקושרת מקצה זיכרון לאלמנטים שלו בנפרד בבלוק זיכרון משלה והמבנה הכולל מתקבל על ידי קישור אלמנטים אלו כחוליות בשרשרת. רשימה מקושרת בודדת מורכבת מרצף של צמתים ולכל צומת יש הפניה לצומת הבא ברצף. רשימה מקושרת כפולה מכילה רצף של צמתים שבהם כל צומת מכיל הפניה לצומת הבא כמו גם לצומת הקודם.
רשימה מקושרת יחידה
לכל אלמנט ברשימה מקושרת בודדת יש שני שדות כפי שמוצג באיור 1. שדה הנתונים מכיל את הנתונים בפועל המאוחסנים והשדה הבא מכיל את ההפניה לרכיב הבא בשרשרת. הרכיב הראשון של הרשימה המקושרת מאוחסן כראש הרשימה המקושרת.
איור 2 מתאר רשימה מקושרת יחידה עם שלושה אלמנטים. כל אלמנט מאחסן את הנתונים שלו וכל האלמנטים מלבד האחרון מאחסנים הפניה לאלמנט הבא. האלמנט האחרון מחזיק ערך null בשדה הבא שלו. ניתן לגשת לכל רכיב ברשימה על ידי התחלה בראש ומעקב אחר המצביע הבא עד שתפגשו את הרכיב הנדרש.
רשימה מקושרת כפולה
לכל רכיב ברשימה מקושרת כפול יש שלושה שדות כפי שמוצג באיור 3.בדומה לרשימה מקושרת בודדת, שדה הנתונים מכיל את הנתונים המאוחסנים בפועל והשדה הבא מכיל את ההפניה לאלמנט הבא בשרשרת. בנוסף, השדה הקודם מכיל את ההפניה לאלמנט הקודם בשרשרת. הרכיב הראשון של הרשימה המקושרת מאוחסן כראש הרשימה המקושרת.
איור 4 מתאר רשימה מקושרת כפולה עם שלושה אלמנטים. כל רכיבי הביניים מאחסנים הפניות לאלמנטים הראשונים והקודמים. האלמנט האחרון ברשימה מחזיק ערך null בשדה הבא שלו והאלמנט הראשון ברשימה מחזיק ערך null בשדה הקודם שלו. ניתן לעבור ברשימה מקושרת כפולה קדימה על ידי מעקב אחר ההפניות הבאות בכל אלמנט ובאופן דומה ניתן לעבור לאחור באמצעות ההפניות הקודמות בכל אלמנט.
מה ההבדל בין רשימה מקושרת יחידה לרשימה מקושרת כפולה?
כל אלמנט ברשימה המקושרת בודדת מכיל הפניה לרכיב הבא ברשימה, בעוד שכל אלמנט ברשימה המקושרת כפול מכיל הפניות לרכיב הבא וכן לרכיב הקודם ברשימה. רשימות מקושרות כפולות דורשות יותר מקום עבור כל רכיב ברשימה ופעולות אלמנטריות כגון הכנסה ומחיקה מורכבות יותר מאחר והן צריכות להתמודד עם שתי הפניות. אבל רשימות קישורים כפולות מאפשרות מניפולציה קלה יותר מכיוון שהיא מאפשרת לעבור ברשימה לכיוונים קדימה ואחורה.
