פרק 11 - צמתים מקושרים (Node)

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

1. מה זה Node?

Node (צומת) הוא אובייקט קטן שמחזיק שני דברים בלבד: ערך (value), ו הפניה לצומת הבא בשרשרת (next). אם אין צומת הבא - ה-next שווה ל-null. שרשרת שלמה נבנית פשוט מכך שכל צומת "מצביע" על הצומת שאחריו.

2. מחלקת Node - החתימה הסטנדרטית

זו מחלקה גנרית (Node<T>) - היא יכולה להחזיק ערך מכל טיפוס. חשוב לזכור את שמות המתודות בדיוק כפי שהן, כי בשאלון משתמשים בהן ישירות בלי להגדיר אותן מחדש:

public class Node<T> {
    private T value;
    private Node<T> next;

    public Node(T value) { ... }
    public Node(T value, Node<T> next) { ... }

    public T GetValue() { ... }
    public Node<T> GetNext() { ... }
    public bool HasNext() { ... }      // true אם יש צומת אחרי זה

    public void SetValue(T value) { ... }
    public void SetNext(Node<T> next) { ... }
}
            

3. בניית שרשרת

בונים שרשרת "מהסוף להתחלה" - קודם יוצרים את הצומת האחרון (בלי next), ואז כל צומת שנוצר לפניו מקבל אותו כפרמטר השני:

Node<string> third = new Node<string>("גורי");            // אין next - הצומת האחרון
Node<string> second = new Node<string>("שרה", third);     // מצביע על third
Node<string> first = new Node<string>("דני", second);     // מצביע על second

// first הוא "ראש" השרשרת - הדרך היחידה להגיע לכל השאר
            

  first                    second                   third
[ "דני"  | next ●] ──► [ "שרה"  | next ●] ──► [ "גורי" | next X ]

כל תא בתרשים הוא צומת Node אחד: משבצת ה-value מחזיקה את הערך, ומשבצת ה-next היא חץ לצומת הבא - חוץ מהצומת האחרון, שם ה-next הוא null (מסומן כ-X בתרשים). first הוא לא צומת בפני עצמו - הוא סתם השם שנתנו למשתנה שמצביע על הצומת הראשון.

4. מעבר על השרשרת (Traversal)

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

Node<string> current = first;
while (current.HasNext()) {
    Console.WriteLine(current.GetValue());
    current = current.GetNext();
}
Console.WriteLine(current.GetValue());   // הצומת האחרון - עדיין צריך להדפיס אותו!
            

5. טעויות נפוצות

6. תרגול

Node<string> third = new Node<string>("גורי");
Node<string> second = new Node<string>("שרה", third);
Node<string> first = new Node<string>("דני", second);

Node<string> current = first.GetNext();
Console.WriteLine(current.GetValue());

Node<string> a = new Node<string>("א");
Node<string> b = new Node<string>("ב");
a.SetNext(b);

Node<string> c = new Node<string>("ג");
b.SetNext(c);

Console.WriteLine(a.GetNext().GetNext().GetValue());