רשימה מקושרת

רשימה מקושרת היא מבנה נתונים הכולל מספר כלשהוא של איברים, כאשר כל איבר מכיל מצביע לאיבר הבא. האיבר האחרון יצביע על NULL כמו-כן מכיל המבנה מצביע לאיבר הראשון.

בדרך כלל מוסיפים לראש הרשימה איבר דמי, כדי להקל על הפעולות. בעזרת איבר זה, אין צורך בשינוי מצביע לראש הרשימה, שכן איבר הדמי ישאר תמיד הראשון. דרך נוספת לשיפור מבנה הנתונים היא ברשימה עם שני מצביעים, מצביע להתחלה ומצביע לסוף.

יש מספר דרכים נוספות לשפר את המבנה, כדוגמת רשימה דו מקושרת, כשכל איבר מצביע גם על האיבר לפניו, או בהחזקת מצביע נוסף / מספר מצביעים נוספים, לאיברים שיש מקום להניח, שהגישה אליהם תהיה בסבירות גבוהה יותר (לקבלת מידע נוסף בחר בקישור המתאים).

הדגמה ויזואלית

פעולות

הפעולות הבסיסיות על רשימה מקושרת הן: יצירת רשימה ריקה, מציאת איבר, הכנסת איבר ומחיקת איבר. לצורך מיון רשימה ניתן להשתמש באלגוריתם Merge-sort.