פרק 3 – מחלקת Node⟨T⟩ – רשימות מקושרות

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

הקובץ Unit4.dll זמין להורדה כאן

מתחילים בחרוז אחד: המחלקה Bead

כל אובייקט מסוג Bead מייצג חרוז אחד, ובו שני שדות:

• color — צבע החרוז, מטיפוס string.
• nextBead — הפניה לחרוז הבא, מטיפוס Bead. הערך null מציין שאין חרוז אחריו.

השדה nextBead מחזיק הפניה לאובייקט אחר, ולא עותק שלו. כך כמה חרוזים נפרדים יכולים להתחבר לשרשרת אחת.

public class Bead
{
    private string color;
    private Bead nextBead;

    // קונסטרוקטורים
    public Bead(string color) { this.color = color; this.nextBead = null; }
    public Bead(string color, Bead nextBead) { this.color = color; this.nextBead = nextBead; }

    // מתודות Getters
    public string GetColor() { return color; }
    public Bead GetNextBead() { return nextBead; }

    // מתודת Setter
    public void SetNextBead(Bead nextBead) { this.nextBead = nextBead; }

    // מתודת ToString
    public override string ToString() { return color; }

}

הפעולות של Bead

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

במחלקה זו משנים קישור באמצעות SetNextBead, ולא SetNext. הפעולה ToString() מחזירה רק את צבע החרוז הנוכחי; כדי להדפיס את כל השרשרת צריך לעבור בין החרוזים.

מחרוז אחד לשרשרת

ניצור שני חרוזים ונקשר את הראשון לשני:

Bead head = new Bead("Red");
Bead second = new Bead("Blue");
head.SetNextBead(second);

המשתנה head מפנה לחרוז הראשון — ראש השרשרת. גם second וגם הקישור שבחרוז האדום מפנים לאותו חרוז כחול; פעולת הקישור לא יצרה חרוז נוסף.

Console.WriteLine(head.GetColor());               // Red
Console.WriteLine(head.GetNextBead().GetColor()); // Blue
Console.WriteLine(second.GetNextBead() == null);  // True
Console.WriteLine(head);                          // Red

אפשר לבנות אותה שרשרת גם בעזרת הבנאי שמקבל קישור. זו חלופה לשלוש שורות הבנייה הקודמות:

Bead head = new Bead("Red", new Bead("Blue"));

מעבר לאורך השרשרת

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

Bead current = head;
while (current != null)
{
    Console.WriteLine(current.GetColor());
    current = current.GetNextBead();
}

יודפסו Red ואז Blue, כל צבע בשורה נפרדת. ההשמה ל־current רק מקדמת את ההפניה שבעזרתה מטיילים; היא אינה משנה קישור בתוך חרוז. head ממשיך להפנות לחרוז הראשון.

יש הבדל בין שרשרת ריקה, שבה head == null, לבין החרוז האחרון, שבו GetNextBead() == null. בלולאה בודקים שהחרוז הנוכחי קיים לפני שקוראים לפעולה שלו, ולכן מבקרים גם בחרוז האחרון.

תרגול עם Bead

1. יצירת שרשרת של שלושה חרוזים — חברו את החרוזים והחזירו את הראש.
2. יצירת חרוזים ממערך — שמרו על סדר הצבעים במערך.
3. הדפסת שרשרת — עברו בין החרוזים והקפידו על פורמט ההדפסה הנדרש.
4. הוספת חרוז לסוף — אתרו את החרוז האחרון וקשרו אליו חרוז חדש.

משרשרת חרוזים לרשימה מקושרת

השרשרת שבנינו היא רשימה מקושרת: כל חוליה (Node) מחזיקה נתון והפניה לחוליה הבאה. ב־Bead הנתון הוא צבע; בחוליה אחרת הוא יכול להיות מספר או אובייקט מורכב.

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

דיאגרמה – רשימה מקושרת

ג’נריקס – Node⟨T⟩

הורדת Unit4.dll

הקובץ Unit4.dll זמין להורדה כאן

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

ההמלצה שלי לשימוש במחלקה היא להשתמש בהפנייה ל-Unit4.dll. דרך מהירה לכך היא על ידי Git Clone של הפרוייקט Turtle22 בקישור זה. ניתן להוסיף הפניה ל-dll מכל פרוייקט מסוג .netFramework.

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

Unit4.dll

הערת ספרייה: אם אתם כותבים ב-VS הוסיפו בתחילת הקובץ using Unit4.CollectionsLib; (לא נדרש באפליקציה). את Unit4 ניתן להוריד מכאן.

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

    //-----------------------------------
    //constructors
    public Node(T value)
    {
        this.value = value;
        this.next = null;
    }
    public Node(T value, Node<T> next)
    {
        this.value = value;
        this.next = next;
    }
    //-----------------------------------
    //getters
    public T GetValue()
    {
        return this.value;
    }
    public Node<T> GetNext()
    {
        return this.next;
    }
    //-----------------------------------
    //setters
    public void SetValue(T value)
    {
        this.value = value;
    }
    public void SetNext(Node<T> next)
    {
        this.next = next;
    }
    //-----------------------------------
    //return true if this.next is not null, else returns false
    public bool HasNext()
    {
        return (this.next != null);
    }
    //-----------------------------------
    //ToString
    public override string ToString()
    {
        return value + "," + next;
    }
}

שימוש במחלקה

Node<string> head = new Node<string>("Red");
head.SetNext(new Node<string>("Blue"));

Console.WriteLine(head.GetValue());              // Red
Console.WriteLine(head.GetNext().GetValue());    // Blue

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

דיאגרמה – רשימה מקושרת

graph LR
    A([ראש]) --> B[Node< T >: Value1]
    B --> C[Node< T >: Value2]
    C --> D[Node< T >: Value3]
    D --> E([null])

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

דגשים לג’נריקס

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

2. אתם לא נדרשים לכתוב מחלקות גנריות משלכם. מטרת הפרק היא ללמוד להשתמש בהן.

3. שימו לב שקריאה לפעולה דרך הפניה שערכה null תגרום לחריגת NullReferenceException.

תרגול וקישורים

תרגילי שרשרת החרוזים — יצירה, מעבר ושינוי קישורים

פלייליסט

סרטוני שרשרת חוליות ב-YouTube