יחידה 10: רשימות מקושרות

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

מבוא לרשימות מקושרות

רשימה מקושרת היא אוסף לינארי של אלמנטים, כאשר הסדר אינו נקבע על ידי מיקום פיזי רציף בזיכרון (כמו במערך), אלא על ידי הפניות (references/pointers) בין האלמנטים. כל אלמנט ברשימה, הנקרא "צומת", מכיל שני חלקים עיקריים: את הנתון עצמו והפניה לצומת הבא ברצף.

השוואה למערכים

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

סוגי רשימות מקושרות

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

פעולות יסוד וניתוח סיבוכיות

הבנת הפעולות הבסיסיות וניתוח סיבוכיותן חיונית לתכנון יעיל ולפתרון בעיות במבחן.

פעולות נפוצות:

• הוספה (Insertion):
  • בראש הרשימה: O(1). יוצרים צומת חדש, מצביעים מראש הרשימה אליו, והצומת החדש מצביע לצומת שהיה קודם ראש הרשימה.
  • בסוף הרשימה: O(n) ברשימה חד-כיוונית ללא הפניה ל-tail (יש לעבור על כולה). O(1) אם יש הפניה ל-tail.
  • באמצע הרשימה: O(n) למציאת המיקום, O(1) לשינוי ההפניות.
• מחיקה (Deletion):
  • בראש הרשימה: O(1). מזיזים את הפניית ה-head לצומת הבא.
  • בסוף הרשימה: O(n) ברשימה חד-כיוונית (יש למצוא את הצומת שלפני האחרון). O(1) ברשימה דו-כיוונית עם tail.
  • באמצע הרשימה: O(n) למציאת הצומת והצומת הקודם לו, O(1) לשינוי ההפניות.
• חיפוש (Search): O(n). יש לעבור על הרשימה צומת אחר צומת עד למציאת האלמנט או הגעה לסוף הרשימה.
• מעבר (Traversal): O(n). ביקור בכל צומת ברשימה, בדרך כלל מה-head ועד ל-null (או חזרה ל-head במעגלית).

היבטים קריטיים וטעויות נפוצות

הבנה מעמיקה של נקודות אלו תמנע באגים נפוצים ותשפר את הקוד שלכם, במיוחד בהקשר למבחנים.

טיפול בהפניות (Pointer Manipulation)

הטיפול הנכון בהפניות הוא לב ליבה של עבודה עם רשימות מקושרות. טעות נפוצה היא לאבד הפניה לצומת, מה שמוביל לאובדן נתונים או ל"דליפת זיכרון" (memory leak) אם אין יותר הפניות לאותו אובייקט.

רקורסיה ברשימות מקושרות

רבות מהפעולות על רשימות מקושרות (כמו הדפסה, היפוך, או חיפוש) ניתנות למימוש אלגנטי באמצעות רקורסיה, במיוחד ברשימות חד-כיווניות. עם זאת, יש לשים לב לעלות של קריאות רקורסיביות (stack space) ולמנוע StackOverflowError ברשימות ארוכות מאוד.

מקרי קצה (Edge Cases)

תמיד בדקו את הקוד שלכם עבור המקרים הבאים, שכן הם מהווים מלכודות נפוצות:

• רשימה ריקה (head == null).
• רשימה עם צומת אחד.
• הוספה/מחיקה של הצומת הראשון.
• הוספה/מחיקה של הצומת האחרון.

שאלות לדיון

• באילו תרחישים רשימה מקושרת תהיה עדיפה על מערך, ומתי מערך יהיה עדיף? נמקו והביאו דוגמאות.
• כיצד תשפיע טעות בטיפול בהפניות (aliasing) על תקינות רשימה מקושרת? תארו דוגמה ספציפית.
• הסבירו את היתרונות והחסרונות של רשימה מקושרת דו-כיוונית לעומת חד-כיוונית. מתי נבחר בכל אחת מהן?
• תארו אלגוריתם רקורסיבי להיפוך רשימה מקושרת חד-כיוונית. מהי סיבוכיות הזמן והמקום שלו?
• כיצד ניתן לממש תור (Queue) באמצעות רשימה מקושרת, ומהי סיבוכיות הפעולות enqueue ו-dequeue במימוש זה?

נקודות לתשובת מודל

• השוואה למערכים:
  • רשימה מקושרת עדיפה: גודל דינמי, הכנסה/מחיקה יעילה באמצע (O(1) לאחר מציאת המיקום). דוגמאות: תור, מחסנית, רשימת השמעה.
  • מערך עדיף: גישה ישירה לפי אינדקס (O(1)), ניצול זיכרון נמוך יותר (אין צורך בהפניות). דוגמאות: אוסף בגודל קבוע, גישה תכופה לאיברים לפי אינדקס.
• השפעת Aliasing:
  • אם שתי הפניות מצביעות לאותו צומת, שינוי דרך אחת ישפיע על השנייה.
  • דוגמה: אם current.next = temp; ובטעות temp הוא צומת קיים ברשימה במקום צומת חדש, הדבר יכול ליצור לולאה אינסופית או לנתק חלקים מהרשימה.
• יתרונות/חסרונות דו-כיוונית מול חד-כיוונית:
  • דו-כיוונית:
    • יתרונות: מעבר בשני הכיוונים, מחיקה יעילה יותר (O(1) לאחר מציאת הצומת) ללא צורך בצומת הקודם, הוספה בסוף ב-O(1) גם ללא tail (אם עוברים מה-tail).
    • חסרונות: דורשת יותר זיכרון (הפניה נוספת), מ
      מצאתם טעות או שחסר משהו? ✏️ הציעו תיקון או תוספת