מערכים לעומת רשימות מקושרות
מערכים הם מבנה הנתונים הנפוץ ביותר לאחסון אוסף של אלמנטים. רוב שפות התכנות מספקות שיטות להכריז בקלות על מערכים וגישה לאלמנטים במערכים. רשימה מקושרת, ליתר דיוק רשימה מקושרת בודדת, היא גם מבנה נתונים שניתן להשתמש בו כדי לאחסן אוסף של אלמנטים. הוא מורכב מרצף של צמתים ולכל צומת יש הפניה לצומת הבא ברצף.
מוצג באיור 1, הוא קטע קוד המשמש בדרך כלל להכרזה והקצאת ערכים למערך. איור 2 מתאר כיצד ייראה מערך בזיכרון.
קוד למעלה מגדיר מערך שיכול לאחסן 5 מספרים שלמים והגישה אליהם מתבצעת באמצעות מדדים 0 עד 4. מאפיין חשוב אחד של מערך הוא שמערך כולו מוקצה כגוש זיכרון בודד וכל רכיב מקבל מרחב משלו במערך. לאחר הגדרת מערך, גודלו קבוע. אז אם אתה לא בטוח לגבי גודל המערך בזמן ההידור, תצטרך להגדיר מערך גדול מספיק כדי להיות בצד הבטוח. אבל, רוב הזמן אנחנו בעצם הולכים להשתמש במספר קטן יותר של אלמנטים ממה שהקצנו. אז כמות ניכרת של זיכרון בעצם מבוזבזת. מצד שני, אם "המערך הגדול מספיק" אינו גדול מספיק, התוכנית תתרסק.
רשימה מקושרת מקצה זיכרון לאלמנטים שלו בנפרד בבלוק זיכרון משלה והמבנה הכללי מתקבל על ידי קישור אלמנטים אלה כחוליות בשרשרת.לכל אלמנט ברשימה מקושרת יש שני שדות כפי שמוצג באיור 3. שדה הנתונים מכיל את הנתונים המאוחסנים בפועל והשדה הבא מכיל את ההפניה לאלמנט הבא בשרשרת. הרכיב הראשון של הרשימה המקושרת מאוחסן כראש הרשימה המקושרת.
| data | next |
איור 3: רכיב של רשימה מקושרת
איור 4 מתאר רשימה מקושרת עם שלושה אלמנטים. כל אלמנט מאחסן את הנתונים שלו וכל האלמנטים מלבד האחרון מאחסנים הפניה לאלמנט הבא. האלמנט האחרון מחזיק ערך null בשדה הבא שלו. ניתן לגשת לכל רכיב ברשימה על ידי התחלת בראש ומעקב אחר המצביע הבא עד שתפגשו את האלמנט הנדרש.
למרות שהמערכים והרשימות המקושרות דומות במובן זה ששניהם משמשים לאחסון אוסף של אלמנטים, יש להם הבדלים עקב האסטרטגיות שבהן הם משתמשים כדי להקצות זיכרון לאלמנטים שלו. מערכים מקצים זיכרון לכל האלמנטים שלו כבלוק בודד ויש לקבוע את גודל המערך בזמן הריצה. זה יהפוך את המערכים ללא יעילים במצבים שבהם אינך יודע את גודל המערך בזמן ההידור. מכיוון שרשימה מקושרת מקצה זיכרון לרכיבים שלה בנפרד, זה יהיה יעיל מאוד במצבים שבהם אינך יודע את גודל הרשימה בזמן ההידור. הצהרה וגישה לרכיבים ברשימה מקושרת לא יהיו פשוטים בהשוואה לאופן שבו אתה ניגש ישירות לרכיבים במערך באמצעות המדדים שלו.
