סיכום רשימות מקושרות

ראש הרשימה ומצביע עזר

בדוגמאות, lst מצביע על ראש רשימת החוליות ו־pos הוא מצביע עזר לסריקה. ברשימה ריקה, הערך של lst הוא null.

Node<int> pos = lst;

סריקת כל החוליות

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

while (pos != null)
{
    // כאן בודקים את החוליה הנוכחית
    pos = pos.GetNext();
}

הוספת חוליה לראש הרשימה

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

Node<int> addPos = new Node<int>(value);
addPos.SetNext(lst);
lst = addPos;

הוספת חוליה אחרי חוליה קיימת

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

addPos.SetNext(pos.GetNext());
pos.SetNext(addPos);

הסדר חשוב: אם מעדכנים קודם את הקישור של pos, הקריאה pos.GetNext() כבר מחזירה את החוליה החדשה. בלי ששמרנו את הקישור הקודם, מאבדים את הגישה להמשך הרשימה דרך pos.

הוספה לסוף הרשימה

ברשימה שאינה ריקה, עוצרים בחוליה האחרונה, כאשר pos.GetNext() מחזיר null. החוליה החדשה היא האחרונה ולכן הקישור שלה נשאר null. אם הרשימה ריקה, משתמשים בהוספה לראש.

Node<int> addPos = new Node<int>(value);
if (lst == null)
{
    lst = addPos;
}
else
{
    Node<int> pos = lst;
    while (pos.GetNext() != null)
    {
        pos = pos.GetNext();
    }
    pos.SetNext(addPos);
}

הוספה לפני חוליה לפי תנאי

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

Node<int> pos = lst;
if (lst != null && lst.GetValue() % 2 == 0)
{
    Node<int> addPos = new Node<int>(lst.GetValue() - 1);
    addPos.SetNext(lst);
    lst = addPos;
}

לפני בדיקת הראש שומרים ב־pos את החוליה הראשונה המקורית. כך הסריקה מתחילה ממנה גם אם הוספנו לפניה חוליה חדשה. בסריקה מתקדמים לחוליה המקורית שנבדקה, כך שלא בודקים אותה שוב אחרי ההוספה.

while (pos != null && pos.GetNext() != null)
{
    Node<int> next = pos.GetNext();
    if (next.GetValue() % 2 == 0)
    {
        Node<int> addPos = new Node<int>(next.GetValue() - 1);
        addPos.SetNext(next);
        pos.SetNext(addPos);
    }
    pos = next;
}

הוספה אחרי חוליה לפי תנאי

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

Node<int> pos = lst;
while (pos != null)
{
    Node<int> next = pos.GetNext();
    if (pos.GetValue() % 2 == 0)
    {
        Node<int> addPos = new Node<int>(pos.GetValue() - 1);
        addPos.SetNext(next);
        pos.SetNext(addPos);
    }
    pos = next;
}

הסרת חוליות מראש הרשימה

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

while (lst != null && ShouldRemove(lst.GetValue()))
{
    lst = lst.GetNext();
}

כאן החוליה שהוסרה כבר אינה נגישה דרך ראש הרשימה. אם רוצים גם לנתק את הקישור שלה לבאה, שומרים אותה במשתנה עזר, מקדמים את lst ורק אז מבצעים removed.SetNext(null).

הסרת חוליות מאמצע הרשימה או מסופה

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

Node<int> pos = lst;
while (pos != null && pos.GetNext() != null)
{
    Node<int> next = pos.GetNext();
    if (ShouldRemove(next.GetValue()))
    {
        pos.SetNext(next.GetNext());
    }
    else
    {
        pos = next;
    }
}

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