רשימה מקושרת (Linked List)

רשימה מקושרת (Linked List): צלילה עמוקה לקורס 20465

בקורס "מעבדה בתכנות מערכות" (20465) באוניברסיטה הפתוחה, רשימות מקושרות הן קונספט ליבה שמופיע באופן תדיר במבחנים, לרוב בשאלות כמו "question1" ו-"question3". סגנון הבחינה נוטה להתמקד ביישום מעשי של רשימות מקושרות בשפת C/C++, תוך דגש על הבנה עמוקה של ניהול זיכרון (הקצאה ושחרור), טיפול נכון במצביעים (כולל מצביעים למצביעים), ומקרי קצה (רשימה ריקה, צומת יחיד). המבחנים בוחנים לא רק את היכולת לכתוב קוד פונקציונלי, אלא גם את היכולת לזהות ולתקן שגיאות נפוצות כמו דליפות זיכרון או גישה למצביעי NULL. הבקיאות במימוש פעולות בסיסיות ומורכבות כאחד היא קריטית להצלחה.

מהי רשימה מקושרת?

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

למה רשימה מקושרת חשובה?

• גמישות בגודל: בניגוד למערכים סטטיים, רשימה מקושרת יכולה לגדול או לקטון באופן דינמי בזמן ריצה, ללא צורך בהקצאה מחדש של בלוק זיכרון גדול.
• הוספה ומחיקה יעילות: הוספה או מחיקה של צמתים באמצע הרשימה דורשת שינוי של מספר קטן של מצביעים בלבד (מורכבות זמן O(1) אם מיקום הצומת הקודם ידוע, או O(n) אם יש לחפש אותו), בניגוד למערך שבו יש להזיז את כל האלמנטים הבאים.
• שימוש יעיל בזיכרון: הזיכרון מוקצה רק לצמתים הקיימים בפועל, ללא בזבוז של מקום עבור קיבולת שאינה בשימוש.

סוגי רשימות מקושרות נפוצים

פעולות בסיסיות

• הוספה (Insertion): הוספת צומת חדש לתחילת, אמצע או סוף הרשימה.
• מחיקה (Deletion): הסרת צומת מהרשימה ושחרור זיכרונו.
• חיפוש (Search): מציאת צומת המכיל ערך מסוים.
• מעבר (Traversal): ביקור בכל צומת ברשימה, בדרך כלל מהראש ועד הסוף.

מורכבות זמן (Time Complexity)

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