דילוג לתוכן המרכזי

סיכום שרשרת חוליות (רשימה חד-כיוונית)

מדעי המחשב לבגרות · 4 נושאים

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

שרשרת חוליות (רשימה חד-כיוונית)

מערך נבנה בגודל קבוע מראש. שרשרת חוליות גדלה וקטנה תוך כדי ריצה: כל ערך נמצא בחוליה משלו, וכל חוליה "מחזיקה" את החוליה הבאה. כדי להוסיף ערך יוצרים חוליה חדשה ומחברים אותה; כדי למחוק - מדלגים עליה.
במדויק: בתכנית, רשימה ("רשימה מקושרת", ובשאלונים "שרשרת חוליות") מיוצגת רק בעזרת המחלקה Node<T>: משתנה שמפנה לחוליה הראשונה בשרשרת של אפס או יותר חוליות. החוליה האחרונה מפנה ל-null, ושרשרת ריקה היא lst == null. בשאלון 899271 שרשרת חוליות היא אחד ממבני הנתונים של הפרק הראשון, לצד תור ועץ בינרי. רשימה דו-כיוונית ומימוש מבני נתונים אינם במיקוד תשפ"ז.

היתרונות והחסרונות לעומת מערך, כפי שהם בתכנית: בצד היתרונות - הקצאת זיכרון דינמית (השרשרת גדלה לפי הצורך); בצד החסרונות - אין גישה ישירה לאיבר לפי מקום, כמו arr[i], ולכן כדי להגיע לחוליה ה-k עוברים על כל החוליות שלפניה.

1. המחלקה Node: חוליה ושרשרת חוליות

חוליה

חוליה היא עצם קטן עם שני חלקים: ערך, והפניה לחוליה הבאה. כשמחברים כמה חוליות, כל אחת לבאה אחריה, מתקבלת שרשרת.
במדויק: חוליה היא עצם של המחלקה הגנרית Node<T>, שמחזיק ערך מטיפוס T והפניה לחוליה נוספת או ל-null. בשאלה כתוב תמיד הטיפוס: "שרשרת חוליות מטיפוס שלם" היא Node<Integer> ב-Java ו-Node<int> ב-C#. הערך יכול להיות גם תו (Node<Character> / Node<char>) או עצם (Node<Game>). בבחינה מותר להשתמש בפעולות הממשק של חוליה בלי לממש אותן.

משתנה מטיפוס Node<T> מתפרש בשתי דרכים: כהפניה לחוליה אחת, או כהפניה לשרשרת שמתחילה בחוליה הזאת ונגמרת ב-null. לכן אפשר להעביר לפעולה חוליה מאמצע השרשרת, והפעולה תראה בה ראש של שרשרת קצרה יותר. כך פועלת match / Match של 899271 קיץ 2026: היא קוראת ל-eval(pNum, pChar, len) כש-pNum ו-pChar על החוליה ה-k של כל שרשרת. אותו רעיון חוזר בעץ בינרי: כל חוליה בינרית היא שורש של תת-עץ.

הממשק של Node

פעולה ב-Javaב-C#מה עושה
new Node<T>(x)new Node<T>(x)חוליה חדשה עם הערך x, ההפניה לחוליה הבאה null
new Node<T>(x, next)new Node<T>(x, next)חוליה חדשה עם הערך x שמפנה ל-next (מותר null)
getValue()GetValue()ערך החוליה
getNext()GetNext()החוליה הבאה, או null
hasNext()HasNext()האם יש חוליה אחריה
setValue(x)SetValue(x)משנה את ערך החוליה ל-x
setNext(next)SetNext(next)משנה את ההפניה לחוליה הבאה
toString()ToString()ערך החוליה כמחרוזת

כל הפעולות O(1), חוץ מ-toString. פעולה שאינה בטבלה (למשל אורך השרשרת) - כותבים בעצמכם.

תבנית: בניית שרשרת וגישה לחוליות

בונים מהסוף להתחלה: כל חוליה חדשה מפנה לשרשרת שכבר נבנתה, והמשתנה lst מפנה תמיד לראש.

// בניית השרשרת 3 -> 5 -> 2 מהסוף להתחלה
Node<Integer> lst = new Node<Integer>(2);
lst = new Node<Integer>(5, lst);
lst = new Node<Integer>(3, lst);

// אותה שרשרת בהוראה אחת
Node<Integer> lst2 = new Node<Integer>(3, new Node<Integer>(5, new Node<Integer>(2)));

System.out.println(lst.getValue());                      // 3
System.out.println(lst.getNext().getValue());            // 5
System.out.println(lst.getNext().getNext().getValue());  // 2
System.out.println(lst.getNext().getNext().hasNext());   // false - החוליה האחרונה

מה אומר כל ביטוי

ביטוימה הוא אומר
lst == nullהשרשרת ריקה
lst.getValue()הערך בחוליה הראשונה
lst.getNext()החוליה השנייה, כלומר השרשרת בלי החוליה הראשונה
p.hasNext()יש חוליה אחרי p (כמו p.getNext() != null)
!p.hasNext()p היא החוליה האחרונה
p.getNext().getValue()הערך בחוליה שאחרי p. מותר רק כש-p.hasNext()

דוגמה - חישוב ביטוי משתי שרשרות במקביל

נתונות שתי הפניות לשרשרות של חוליות: numHead - שרשרת של מספרים מטיפוס שלם, ו-charHead - שרשרת מטיפוס תו (char), שבה מיוצגות פעולות החשבון חיבור וחיסור ('+', '-'). כמות החוליות בשרשרת המספרים גדולה ב-1 מכמות החוליות בשרשרת התווים.
התו במיקום 1 בשרשרת התווים הוא הפעולה שלפני המספר במיקום 2, התו במיקום 2 הוא הפעולה שלפני המספר במיקום 3, וכן הלאה. אין פעולת חשבון לפני המספר הראשון.
בדוגמה: numHead: 3 → 5 → 2 → 3 → 7 → null, ו-charHead: + → − → − → + → null. השרשרות מייצגות את 3 + 5 − 2 − 3 + 7.
ממשו את הפעולה:
Java - public static int eval(Node<Integer> numHead, Node<Character> charHead, int len)
C# - public static int Eval(Node<int> numHead, Node<char> charHead, int len)
len הוא כמות המספרים שנרצה לחשב מתחילת שרשרת המספרים. הפעולה תחזיר את תוצאת החישוב של len מספרים ברצף, החל מתחילת שתי השרשרות. הניחו ש-len גדול מ-0. אין לשנות את השרשרות שהתקבלו. אם len גדול מכמות החוליות בשרשרת המספרים, הפעולה תחזיר את תוצאת החישוב של כל המספרים.
בדוגמה: len = 1 - מוחזר 3; len = 3 - מוחזר 6; len = 8 - מוחזר 10.

פתרון
1.המספר הראשון: לפניו אין פעולה, ולכן מתחילים ב-result = numHead.getValue().
2.שתי הפניות במקביל: pNum מתחיל בחוליה השנייה של המספרים, ו-pChar בחוליה הראשונה של התווים - התו שלפני המספר הזה.
3.הלולאה: כל עוד חושבו פחות מ-len מספרים וגם pNum != null. אם התו '+' מוסיפים, אחרת מחסרים, ומקדמים את שתי ההפניות.
4.למה לא בודקים את pChar: יש תו אחד פחות ממספרים, ולכן כשיש עוד מספר, יש גם תו לפניו.
5.השרשרות לא משתנות: רק ההפניות pNum ו-pChar זזות.
public static int eval(Node<Integer> numHead, Node<Character> charHead, int len)
{
    int result = numHead.getValue();      // המספר הראשון - בלי פעולה לפניו
    Node<Integer> pNum = numHead.getNext();
    Node<Character> pChar = charHead;
    int count = 1;                        // כמה מספרים כבר חושבו
    while (count < len && pNum != null)
    {
        if (pChar.getValue() == '+')
            result = result + pNum.getValue();
        else
            result = result - pNum.getValue();
        pNum = pNum.getNext();
        pChar = pChar.getNext();
        count++;
    }
    return result;
}
6.בדיקה על השרשרות שבשאלה, עם len = 8:
מספרים שחושבוהתוהמספרresult
1-33
2+58
3−26
4−33
5+710
עצירה-pNum הוא null10

בהרצה: len = 1 החזירה 3, len = 3 החזירה 6, len = 8 החזירה 10, והשרשרות נשארו כמו שהיו.

תשובה

result מתחיל בערך הראשון; כל עוד count < len וגם pNum != null: לפי התו מוסיפים או מחסרים את הערך של pNum, ומקדמים את שתי ההפניות. בדוגמה: len = 1 - 3, len = 3 - 6, len = 8 - 10.

2. סריקת שרשרת: מעבר, ספירה, חיפוש והשוואה

סריקת שרשרת

בשרשרת אין arr[i]: כדי להגיע לחוליה כלשהי מתחילים בראש והולכים חוליה אחר חוליה. כמעט כל שאלה על שרשרת היא סריקה כזאת, עם מונה, צובר, מיקום או דגל.
במדויק: סריקה ("מעבר על רשימה") נעשית בהפניית עזר p שמתחילה ב-lst ומתקדמת ב-p = p.getNext() עד שהיא null. ההפניה שזזה היא p, ולכן השרשרת לא משתנה. חיפוש חוליה נעשה לפי ערך (משווים את p.getValue()) או לפי מקום (סופרים חוליות). סריקה אחת עולה O(n), כש-n הוא מספר החוליות.

זה אותו שלד כמו לולאה על מערך: p = lst במקום i = 0, p != null במקום i < arr.length, p = p.getNext() במקום i++. ההבדל מסריקת תור: בשרשרת לא מוציאים ערכים כדי לקרוא אותם, ולכן אין תור עזר ואין מה להחזיר למקום.

תבנית: סריקה עם הפניית עזר

// כמה ערכים בשרשרת גדולים מ-x
public static int countGreater(Node<Integer> lst, int x)
{
    int count = 0;
    Node<Integer> p = lst;        // הפניית עזר - lst לא זז
    while (p != null)             // עד אחרי החוליה האחרונה
    {
        if (p.getValue() > x)
            count++;
        p = p.getNext();          // קידום לחוליה הבאה
    }
    return count;
}

על השרשרת 4 → 9 → 1 → 12 → 7 → null והערך x = 5 הפעולה מחזירה 3, והשרשרת לא משתנה.

איזה תנאי לולאה

תנאי הלולאהאיפה p בסוףמתי משתמשים
p != nullnull, אחרי החוליה האחרונהעוברים על כל הערכים
p.hasNext()על החוליה האחרונהצריך את החוליה האחרונה, או בודקים בכל סיבוב את החוליה שאחרי p
count < len && p != nullעוצרים מוקדםעד len חוליות, או עד סוף השרשרת אם היא קצרה יותר
return בתוך הלולאה-חיפוש: מחזירים ברגע שנמצא, ואחרי הלולאה מחזירים את התשובה של "לא נמצא"
דרך הפתרון

סריקה של שרשרת

1.הפניית עזר: Node<Integer> p = lst;. את lst לא מזיזים.
2.מה זוכרים: מונה, צובר, דגל, או מקום (pos++ בכל סיבוב) כשהשאלה מדברת על מיקומים.
3.תנאי הלולאה לפי הטבלה. בשתי שרשרות במקביל - תנאי שעוצר לפני שאחת מההפניות היא null.
4.גוף הלולאה: קוראים את p.getValue() (בשרשרת של עצמים: p.getValue().getPrice()), ובסוף הסיבוב p = p.getNext().
5.אחרי הלולאה: מחזירים את התשובה. בחיפוש - את הערך של "לא נמצא" (למשל -1 או false).
שים לב

"חובה לשמור על השרשרת" / "אין לשנות את השרשרות שהתקבלו": סריקה ב-p = p.getNext() לא משנה דבר. שרשרת משתנה רק ב-setNext וב-setValue.

שים לב

לפני p.getNext() או p.getValue() בודקים ש-p אינו null. ב-match של קיץ 2026 לחוליה האחרונה בשרשרת המספרים אין תו באותו מיקום, ולכן מקדמים את pChar רק אם pChar != null; אחרת הקריאה ל-getNext() על null זורקת חריגה.

שים לב

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

שים לב

פעולה שעוברת על השרשרת וקוראת בכל חוליה לפעולה שסורקת את כל השרשרת היא O(n²): longest / Longest של קיץ 2024 קוראת ל-width (O(n)) בעבור כל אחת מ-n החוליות.

דוגמה - אורך תת-סדרה נגדית בשרשרת

"תת-סדרה נגדית" היא רצף של מספרים שמתחיל במספר כלשהו ומסתיים במספר הנגדי לו (חיובי ושלילי עם אותו ערך מוחלט, באחד משני הסדרים).
נתונה שרשרת חוליות lst מטיפוס שלם, ובה מספרים חיוביים ושליליים שאינם 0, וכולם שונים זה מזה.
א. כתבו פעולה ששמה width בשפת Java או Width בשפת C#, המקבלת את השרשרת lst ומספר שלם num המופיע בשרשרת. הפעולה תחזיר את אורך התת-סדרה הנגדית שהמספר num מתחיל או מסיים (כולל המספרים בקצוות). אם המספר הנגדי ל-num אינו מופיע בשרשרת, הפעולה תחזיר -1. חובה לשמור על השרשרת lst. אין להשתמש במערך.
בעבור השרשרת -9 → -1 → 1 → 22 → 10 → -2 → 9 → -10 → 4 → null: בעבור num = 9 הפעולה תחזיר 7 (התת-סדרה -9 עד 9); בעבור num = -1 תחזיר 2; בעבור num = 22 תחזיר -1.
ב. כתבו פעולה ששמה longest בשפת Java או Longest בשפת C#, המקבלת את השרשרת lst, ומחזירה את אורך התת-סדרה הנגדית הגדולה ביותר, או -1 אם אין אף אחת. אפשר להשתמש בפעולה מסעיף א. אין להשתמש במערך. בעבור השרשרת שלעיל הפעולה תחזיר 7.

פתרון
1.א - מה מחפשים: כל המספרים שונים, ולכן num מופיע פעם אחת, ו--num לכל היותר פעם אחת. האורך הוא ההפרש בין המקומות שלהם ועוד 1, ולא משנה מי מופיע קודם: Math.abs(posNum - posOpp) + 1.
2.א - הסריקה: הפניית עזר p ומונה pos. אם הערך num - שומרים posNum = pos; אם הוא -num - שומרים posOpp = pos.
3.א - לא נמצא: אם בסוף posOpp == 0, מחזירים -1.
4.ב: כל תת-סדרה נגדית מתחילה באחד המספרים בשרשרת. לכן עוברים על כל ערך v, מחשבים width(lst, v) ושומרים את הגדול ביותר. מתחילים ב-max = -1, ואם אין אף תת-סדרה נגדית נשאר -1.
public static int width(Node<Integer> lst, int num)
{
    int pos = 0;            // מקום החוליה הנוכחית
    int posNum = 0;         // המקום של num
    int posOpp = 0;         // המקום של -num (0 = לא נמצא)
    Node<Integer> p = lst;
    while (p != null)
    {
        pos++;
        if (p.getValue() == num)
            posNum = pos;
        else if (p.getValue() == -num)
            posOpp = pos;
        p = p.getNext();
    }
    if (posOpp == 0)
        return -1;
    return Math.abs(posNum - posOpp) + 1;
}

public static int longest(Node<Integer> lst)
{
    int max = -1;
    Node<Integer> p = lst;
    while (p != null)
    {
        int w = width(lst, p.getValue());   // תת-סדרה נגדית שמתחילה או מסתיימת בערך זה
        if (w > max)
            max = w;
        p = p.getNext();
    }
    return max;
}
5.בדיקה על השרשרת שבשאלה:
הערך numמקום numמקום המספר הנגדיwidth
9717
-1232
224לא נמצא-1
10584

בהרצה: width החזירה 7, 2, -1, 4; longest החזירה 7, והשרשרת לא השתנתה.

6.סיבוכיות: width - מעבר אחד, O(n). longest - n קריאות ל-width, O(n²).
תשובה

א. מעבר אחד עם מונה מקום: posNum הוא המקום של num, ו-posOpp המקום של -num. אם -num לא נמצא - מחזירים -1, אחרת |posNum − posOpp| + 1 (בדוגמה: 7, 2, -1).
ב. max = -1; לכל ערך v בשרשרת מחשבים width(lst, v) ומעדכנים את max. מחזירים את max (בדוגמה: 7).

3. שינוי שרשרת: הוספה ומחיקה של חוליות

הוספה ומחיקה של חוליות

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

כשהראש משתנה, מי שמחזיק את השרשרת צריך לקבל את הראש החדש: בפעולה פנימית משנים את התכונה (כמו lst במחלקה Store של קיץ 2025), ובפעולה חיצונית מחזירים את הראש החדש (כמו what / What של קיץ 2024, בשיעור על פעולות רקורסיביות).

תבנית: הוספה ומחיקה בקוד

// הוספה בראש השרשרת - O(1)
lst = new Node<Integer>(x, lst);

// הוספה אחרי החוליה p - O(1)
p.setNext(new Node<Integer>(x, p.getNext()));

// הוספה בסוף השרשרת (lst אינה ריקה) - O(n)
Node<Integer> last = lst;
while (last.hasNext())
    last = last.getNext();
last.setNext(new Node<Integer>(x));

// מחיקת החוליה הראשונה - O(1)
lst = lst.getNext();

// מחיקת החוליה שאחרי p (בתנאי ש-p.hasNext()) - O(1)
p.setNext(p.getNext().getNext());

בהרצה על 3 → 5 → 2 → null, עם x = 8 ו-p על החוליה 5: אחרי שלוש ההוספות מתקבל 8 → 3 → 5 → 8 → 2 → 8 → null, ואחרי שתי המחיקות 3 → 5 → 2 → 8 → null.

הסיבוכיות של הוספה ומחיקה

פעולהסיבוכיותלמה
הוספה בראש, מחיקת הראשO(1)משנים הפניה אחת
הוספה או מחיקה אחרי חוליה p שכבר בידינוO(1)משנים הפניה אחת
הוספה בסוףO(n)צריך קודם להגיע לחוליה האחרונה
מחיקה לפי ערך או לפי מקוםO(n)צריך קודם למצוא את החוליה שלפני
שים לב

כשבונים שרשרת חדשה והשאלה אומרת "אין חשיבות לסדר", מוסיפים כל ערך לראש: מתחילים ב-result = null, ובכל הוספה result = new Node<T>(x, result). כל הוספה O(1), ואין צורך להגיע לסוף השרשרת. כך בונה allStations / AllStations של קיץ 2024 את שרשרת הקווים.

דרך הפתרון

מחיקת חוליות לפי תנאי

1.ראש השרשרת: כל עוד lst != null והחוליה הראשונה צריכה להימחק - lst = lst.getNext(). לולאה ולא if: גם החוליה הבאה יכולה להתאים.
2.התרוקנה? אם lst נעשה null - מסיימים.
3.שאר השרשרת: pos = lst, וכל עוד pos.hasNext() בודקים את pos.getNext(). אם צריך למחוק אותה - pos.setNext(pos.getNext().getNext()), ו-pos לא מתקדם. אחרת - pos = pos.getNext().
4.מגבלה על מספר המחיקות: מונה, ותנאי עליו בשתי הלולאות.
שים לב

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

שים לב

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

דוגמה - מחיקת n המשחקים הראשונים במחיר נתון

נתונה המחלקה Game - משחק מחשב, ולה שתי תכונות: name - שם המשחק (מחרוזת), ו-price - מחיר המשחק (שלם, גדול מ-0). יש פעולות get/Get ו-set/Set לתכונות.
נתונה המחלקה Store - חנות, ולה תכונה אחת: lst - הפניה לשרשרת חוליות שאינה ריקה, מטיפוס Game. המשחקים אינם מסודרים, וכל משחק מופיע פעם אחת.
ממשו את הפעולה של המחלקה Store:
Java - public int remove(int n, int pr)
C# - public int Remove(int n, int pr)
הפעולה תמחק מהשרשרת n משחקים שמחיר כל אחד מהם pr. אם יש יותר מ-n כאלה - יימחקו n הראשונים מביניהם; אם יש פחות - רק הם יימחקו. הפעולה תחזיר את כמות המשחקים שנמחקו. שאר המשחקים יישארו באותו הסדר; אם אין משחק במחיר pr, השרשרת לא תשתנה והפעולה תחזיר 0.
בדוגמה, השרשרת (שם:מחיר): a:30 → g:30 → b:27 → v:99 → k:30 → c:25 → p:30 → null. בעבור pr = 30 ו-n = 3 הפעולה תחזיר 3, והשרשרת תהיה b:27 → v:99 → c:25 → p:30. בעבור pr = 30 ו-n = 5 הפעולה תחזיר 4, והשרשרת תהיה b:27 → v:99 → c:25.

פתרון
1.הראש: בדוגמה שני המשחקים הראשונים עולים 30, ולכן מוחקים מהראש בלולאה: lst = lst.getNext() כל עוד המחיר pr ו-count < n. lst היא תכונה, ולכן השינוי נשמר בעצם.
2.שרשרת ריקה: אם כל המשחקים נמחקו - מחזירים את count.
3.שאר השרשרת: pos מתחיל ב-lst, ובכל סיבוב בודקים את החוליה שאחרי pos. מחיר pr - מדלגים עליה ב-setNext ומוסיפים 1 ל-count, ו-pos נשאר; אחרת pos מתקדם.
4.עצירה: כש-count מגיע ל-n, או בסוף השרשרת.
public int remove(int n, int pr)
{
    int count = 0;
    // מחיקה מתחילת השרשרת - כל עוד החוליה הראשונה מכילה משחק במחיר pr
    while (lst != null && count < n && lst.getValue().getPrice() == pr)
    {
        lst = lst.getNext();
        count++;
    }
    if (lst == null)
        return count;
    // מחיקה מאמצע השרשרת ומסופה - בודקים תמיד את החוליה שאחרי pos
    Node<Game> pos = lst;
    while (pos.hasNext() && count < n)
    {
        if (pos.getNext().getValue().getPrice() == pr)
        {
            pos.setNext(pos.getNext().getNext());   // pos לא מתקדם
            count++;
        }
        else
        {
            pos = pos.getNext();
        }
    }
    return count;
}
5.בדיקה (בהרצה):
•remove(3, 30) החזירה 3, והשרשרת b:27 → v:99 → c:25 → p:30: נמחקו a ו-g מהראש ו-k מהאמצע; p נשאר כי count הגיע ל-3.
•remove(5, 30) החזירה 4, והשרשרת b:27 → v:99 → c:25: נמחק גם p מהסוף.
•remove(2, 50) החזירה 0, והשרשרת לא השתנתה.
6.סיבוכיות: כל חוליה נבדקת פעם אחת לכל היותר - O(L), כש-L הוא מספר החוליות.
תשובה

מוחקים מתחילת השרשרת כל עוד lst מכיל משחק במחיר pr (ו-count < n), ואז עם pos בודקים את pos.getNext(): אם מחירו pr - pos.setNext(pos.getNext().getNext()) ו-count++, אחרת pos מתקדם. מחזירים count (בדוגמה: 3, ובעבור n = 5: 4). סיבוכיות O(L).

4. פעולות רקורסיביות על שרשרת חוליות

פעולה רקורסיבית על שרשרת

שרשרת בנויה בעצמה באופן רקורסיבי: חוליה ראשונה, ואחריה שוב שרשרת, קצרה יותר. לכן פעולה על שרשרת נכתבת בקלות כרקורסיה: מטפלים בחוליה הראשונה, ומשאירים לקריאה הרקורסיבית את ההמשך.
במדויק: מקרה הבסיס הוא בדרך כלל השרשרת הריקה, lst == null. הצעד הוא קריאה על lst.getNext(), השרשרת הקצרה יותר, וצירוף התוצאה לחוליה הנוכחית. בבחינה שואלים על פעולה רקורסיבית נתונה: "עקבו... והציגו את השרשרת שהפעולה מחזירה", "מה עושה הפעולה" ו"מהי סיבוכיות הפעולה".

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

תבנית: מחזירה ערך, מחזירה שרשרת

// מחזירה ערך: סכום הערכים בשרשרת
public static int sum(Node<Integer> lst)
{
    if (lst == null)                         // מקרה בסיס: שרשרת ריקה
        return 0;
    return lst.getValue() + sum(lst.getNext());
}

// מחזירה שרשרת: מוחקת את החוליות שערכן שלילי ומחזירה את הראש החדש
public static Node<Integer> removeNeg(Node<Integer> lst)
{
    if (lst == null)
        return null;
    Node<Integer> rest = removeNeg(lst.getNext());   // ההמשך, כבר בלי שליליים
    if (lst.getValue() < 0)
        return rest;                         // מדלגים על החוליה
    lst.setNext(rest);                       // מחברים את החוליה להמשך
    return lst;
}

בהרצה על 3 → -1 → 4 → -5 → -2 → 6 → null: sum מחזירה 5, ו-removeNeg מחזירה 3 → 4 → 6 → null. על שרשרת שכל ערכיה שליליים removeNeg מחזירה null.

דרך הפתרון

מעקב אחר רקורסיה על שרשרת

1.מתי מטפלים בחוליה: אם הקריאה הרקורסיבית באה לפני הטיפול בחוליה, הקריאות יורדות עד null, והטיפול קורה בדרך חזרה - מהחוליה האחרונה לראשונה.
2.טבלה: שורה לכל קריאה, בסדר החזרה: על איזו חוליה, מה החזירה הקריאה הרקורסיבית, ומה מחזירה הקריאה הזאת.
3.השרשרת המוחזרת: התשובה היא מה שמחזירה הקריאה הראשונה, לא מה ש-lst מפנה אליו.
4.מה הפעולה עושה: מניחים שהקריאה על lst.getNext() כבר עשתה את העבודה על ההמשך, ושואלים מה הקריאה מוסיפה בחוליה הנוכחית.
שים לב

כשפעולה מחזירה שרשרת, משתמשים בערך המוחזר. אחרי what(lst, 1) של קיץ 2024 המשתנה lst עדיין מפנה לחוליה הראשונה, שערכה 1 והיא נמחקה. בהרצה, הסריקה מ-lst הראתה 1 → 3 → 5 → 3 → 9 → 4, והשרשרת המוחזרת היא 3 → 5 → 3 → 9 → 4.

שים לב

קריאה רקורסיבית אחת לכל חוליה ועבודה קבועה בכל קריאה - O(n): יש n + 1 קריאות, כולל הקריאה על null. אם בכל קריאה יש גם סריקה של ההמשך, הסכום הוא (n − 1) + (n − 2) + … + 1 + 0, כלומר O(n²).

דוגמה א - מעקב, מטרה וסיבוכיות של מחיקה רקורסיבית

נתונה הפעולה what בשפת Java או What בשפת C#:

public static Node<Integer> what(Node<Integer> lst, int x)
{
    if (lst == null)
        return null;
    Node<Integer> temp = what(lst.getNext(), x);
    if (lst.getValue() == x)
        return temp;
    lst.setNext(temp);
    return lst;
}

נתונה שרשרת חוליות lst מטיפוס שלם: 1 → 3 → 5 → 3 → 1 → 9 → 4 → null.
(1) עקבו אחר הפעולה what(lst, 1), והציגו את השרשרת שהפעולה מחזירה.
(2) מה עושה הפעולה what? הסבירו את תשובתכם.
(3) מהי סיבוכיות הפעולה what? נמקו את תשובתכם.

פתרון
1.הסדר: הקריאה הרקורסיבית באה לפני הטיפול בחוליה. הקריאות יורדות עד null, והחוליות מטופלות בדרך חזרה, מהאחרונה לראשונה. כל קריאה מקבלת ב-temp את ההמשך שכבר "נוקה": אם ערך החוליה הוא x - מחזירה את temp ומדלגת על החוליה; אחרת - מחברת את החוליה ל-temp ומחזירה אותה.
2.מעקב (בסדר החזרה):
קריאה על החוליהtempהערך הוא 1?מוחזר
null--null
4nullלא4
94לא9 → 4
1 (החמישית)9 → 4כן9 → 4
3 (הרביעית)9 → 4לא3 → 9 → 4
53 → 9 → 4לא5 → 3 → 9 → 4
3 (השנייה)5 → 3 → 9 → 4לא3 → 5 → 3 → 9 → 4
1 (הראשונה)3 → 5 → 3 → 9 → 4כן3 → 5 → 3 → 9 → 4

בהרצה הוחזרה השרשרת 3 → 5 → 3 → 9 → 4 → null.

3.מה עושה: אם what(lst.getNext(), x) מחזירה את ההמשך בלי ערכי x, הקריאה הנוכחית מוותרת על החוליה אם ערכה x, ואחרת מחברת אותה להמשך. בהרצה נוספת, what(lst, 3) על אותה שרשרת החזירה 1 → 5 → 1 → 9 → 4.
4.סיבוכיות: כל קריאה מבצעת קריאה רקורסיבית אחת, על החוליה הבאה, ועוד מספר קבוע של הוראות. יש n + 1 קריאות.
תשובה

(1) הפעולה מחזירה את השרשרת 3 → 5 → 3 → 9 → 4 → null (שתי החוליות עם הערך 1 הוסרו).
(2) הפעולה מוחקת מהשרשרת lst את כל החוליות שערכן שווה ל-x (סדר שאר החוליות נשמר), ומחזירה הפניה לראש השרשרת החדשה (null אם לא נשארו חוליות).
(3) O(n), כש-n הוא מספר החוליות בשרשרת: קריאה רקורסיבית אחת לכל חוליה (ועוד אחת על null), ובכל קריאה עבודה קבועה.

דוגמה ב - פעולה רקורסיבית שקוראת לפעולה מסעיף קודם

נתונה הפעולה guess בשפת Java או Guess בשפת C#, שמשתמשת בפעולה what מהדוגמה הקודמת:

public static void guess(Node<Integer> lst)
{
    if (lst != null)
    {
        Node<Integer> temp = what(lst.getNext(), lst.getValue());
        lst.setNext(temp);
        guess(lst.getNext());
    }
}

נתונה אותה שרשרת חוליות lst: 1 → 3 → 5 → 3 → 1 → 9 → 4 → null.
(1) עקבו אחר הפעולה guess(lst), והציגו את השרשרת lst בסיום הפעולה. אין צורך לעקוב אחר הפעולה what.
(2) מה עושה הפעולה guess? הסבירו את תשובתכם.
(3) מהי סיבוכיות הפעולה guess? נמקו את תשובתכם.

פתרון
1.לא עוקבים אחרי what: משתמשים במה שכבר ידוע עליה - what(lst.getNext(), lst.getValue()) מוחקת מההמשך את כל החוליות עם הערך של החוליה הנוכחית. החוליה הנוכחית מתחברת להמשך הנקי, ו-guess ממשיכה לחוליה הבאה.
2.מעקב:
קריאה על החוליהמה נמחק מההמשךlst אחרי הצעד
1ה-1 שבמקום החמישי1 → 3 → 5 → 3 → 9 → 4
3ה-3 שבמקום הרביעי1 → 3 → 5 → 9 → 4
5אין1 → 3 → 5 → 9 → 4
9אין1 → 3 → 5 → 9 → 4
4ההמשך ריק1 → 3 → 5 → 9 → 4
nullהפעולה מסתיימת

בהרצה: lst בסוף הוא 1 → 3 → 5 → 9 → 4 → null. כאן lst עצמו מתאים לתוצאה: החוליה הראשונה אף פעם לא נמחקת, כי what מופעלת רק על ההמשך שלה.

3.מה עושה: כשמגיעים לחוליה, כבר נמחקו ממנה ומההמשך כל הערכים שהופיעו לפניה, ולכן היא ההופעה הראשונה של הערך שלה. בהרצה נוספת, 4 → 4 → 2 → 4 → 2 → 7 → 2 נעשתה 4 → 2 → 7.
4.סיבוכיות: המקרה הגרוע - כל הערכים שונים, ושום חוליה לא נמחקת. לחוליה הראשונה what עוברת על n − 1 חוליות, לשנייה על n − 2, וכן הלאה עד 0.
תשובה

(1) בסיום הפעולה: lst = 1 → 3 → 5 → 9 → 4 → null.
(2) הפעולה מוחקת מהשרשרת את הכפילויות: מכל ערך נשארת רק ההופעה הראשונה שלו (סדר ההופעות הראשונות נשמר).
(3) O(n²), כש-n הוא מספר החוליות: לכל חוליה מופעלת what על ההמשך שלה, שאורכו n − 1, n − 2, …, 0. הסכום הוא n(n − 1)/2.

כל האתר במבט אחד

קיצורי דרך לכל הכלים, הבגרויות והקורסים

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