יחידה 9: מבני נתונים מקושרים

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

מבנה הצומת (Node) – אבן הבניין של הרשימה המקושרת

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

הגדרת מבנה צומת ב-C

מבנה צומת טיפוסי מוגדר באמצעות struct. חשוב להשתמש ב-typedef כדי לפשט את הכתיבה.

typedef struct Node {
    int data;          // שדה הנתונים של הצומת
    struct Node *next; // מצביע לצומת הבא ברשימה
} Node;

// עבור רשימה דו-כיוונית:
typedef struct DNode {
    int data;
    struct DNode *next; // מצביע לצומת הבא
    struct DNode *prev; // מצביע לצומת הקודם
} DNode;

סוגי רשימות מקושרות והטמעתן ב-C

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

פעולות נפוצות ברשימות מקושרות

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

הוספת צומת (Node Insertion)

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

מחיקת צומת (Node Deletion)

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

מעבר על הרשימה (List Traversal)

מעבר על הרשימה מתבצע באמצעות מצביע עזר (לדוגמה, current) שמתחיל בראש הרשימה ומתקדם מצומת לצומת באמצעות current = current->next, עד שמגיע ל-NULL (או חוזר לראש הרשימה במעגלית).

יתרונות וחסרונות של רשימות מקושרות

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

שאלות לדיון

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

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

• הבחירה בין רשימות תלויה בצרכים: חד-כיוונית חסכונית בזיכרון ופשוטה יותר, אך איטית יותר בגישה אחורה או מחיקה מהסוף. דו-כיוונית מהירה יותר בפעולות אלו אך צורכת יותר זיכרון.
• רשימה מעגלית: הצומת האחרון מצביע לראשון. יתרונות: גישה קלה לראש הרשימה מהסוף, שימוש בתורים מעגליים. חסרונות: מורכבות בבדיקת סיום מעבר, קושי בזיהוי רשימה ריקה ללא מצביע נוסף.
• מחיקת צומת: יש למצוא את הצומת ואת קודמו. עדכון מצביעים: prev->next = current->next; ו-current->next->prev = prev; (אם קיים). יש לטפל במקרה של מחיקת ראש הרשימה או צומת יחיד. לבסוף, free(current).
• סיכונים: דליפות זיכרון (אי-שחרור זיכרון), מצביעים תלויים (dangling pointers), גישה לזיכרון לא חוקי. מזעור: הקפדה על malloc ו-free, אתחול מצביעים ל-NULL, בדיקת NULL לפני גישה למצביעים, סדר פעולות נכון בעדכון קישורים.