שרשרת חוליות (רשימה חד-כיוונית)
מערך נבנה בגודל קבוע מראש. שרשרת חוליות גדלה וקטנה תוך כדי ריצה: כל ערך נמצא בחוליה משלו, וכל חוליה "מחזיקה" את החוליה הבאה. כדי להוסיף ערך יוצרים חוליה חדשה ומחברים אותה; כדי למחוק - מדלגים עליה.
במדויק: בתכנית, רשימה ("רשימה מקושרת", ובשאלונים "שרשרת חוליות") מיוצגת רק בעזרת המחלקה 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.
result = numHead.getValue().pNum != null. אם התו '+' מוסיפים, אחרת מחסרים, ומקדמים את שתי ההפניות.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;
}| מספרים שחושבו | התו | המספר | result |
|---|---|---|---|
| 1 | - | 3 | 3 |
| 2 | + | 5 | 8 |
| 3 | − | 2 | 6 |
| 4 | − | 3 | 3 |
| 5 | + | 7 | 10 |
| עצירה | - | pNum הוא null | 10 |
בהרצה: 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 != null | null, אחרי החוליה האחרונה | עוברים על כל הערכים |
p.hasNext() | על החוליה האחרונה | צריך את החוליה האחרונה, או בודקים בכל סיבוב את החוליה שאחרי p |
count < len && p != null | עוצרים מוקדם | עד len חוליות, או עד סוף השרשרת אם היא קצרה יותר |
return בתוך הלולאה | - | חיפוש: מחזירים ברגע שנמצא, ואחרי הלולאה מחזירים את התשובה של "לא נמצא" |
סריקה של שרשרת
Node<Integer> p = lst;. את lst לא מזיזים.pos++ בכל סיבוב) כשהשאלה מדברת על מיקומים.p.getValue() (בשרשרת של עצמים: p.getValue().getPrice()), ובסוף הסיבוב p = p.getNext().-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.
-num לכל היותר פעם אחת. האורך הוא ההפרש בין המקומות שלהם ועוד 1, ולא משנה מי מופיע קודם: Math.abs(posNum - posOpp) + 1.posNum = pos; אם הוא -num - שומרים posOpp = pos.posOpp == 0, מחזירים -1.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;
}| הערך num | מקום num | מקום המספר הנגדי | width |
|---|---|---|---|
| 9 | 7 | 1 | 7 |
-1 | 2 | 3 | 2 |
| 22 | 4 | לא נמצא | -1 |
| 10 | 5 | 8 | 4 |
בהרצה: width החזירה 7, 2, -1, 4; longest החזירה 7, והשרשרת לא השתנתה.
א. מעבר אחד עם מונה מקום: 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 את שרשרת הקווים.
מחיקת חוליות לפי תנאי
lst != null והחוליה הראשונה צריכה להימחק - lst = lst.getNext(). לולאה ולא if: גם החוליה הבאה יכולה להתאים.pos = lst, וכל עוד pos.hasNext() בודקים את pos.getNext(). אם צריך למחוק אותה - pos.setNext(pos.getNext().getNext()), ו-pos לא מתקדם. אחרת - pos = pos.getNext().אחרי מחיקה לא מקדמים את 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.
lst = lst.getNext() כל עוד המחיר pr ו-count < n. lst היא תכונה, ולכן השינוי נשמר בעצם.setNext ומוסיפים 1 ל-count, ו-pos נשאר; אחרת pos מתקדם.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;
}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, והשרשרת לא השתנתה.מוחקים מתחילת השרשרת כל עוד 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.
מעקב אחר רקורסיה על שרשרת
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? נמקו את תשובתכם.
| קריאה על החוליה | temp | הערך הוא 1? | מוחזר |
|---|---|---|---|
| null | - | - | null |
| 4 | null | לא | 4 |
| 9 | 4 | לא | 9 → 4 |
| 1 (החמישית) | 9 → 4 | כן | 9 → 4 |
| 3 (הרביעית) | 9 → 4 | לא | 3 → 9 → 4 |
| 5 | 3 → 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.
what(lst.getNext(), x) מחזירה את ההמשך בלי ערכי x, הקריאה הנוכחית מוותרת על החוליה אם ערכה x, ואחרת מחברת אותה להמשך. בהרצה נוספת, what(lst, 3) על אותה שרשרת החזירה 1 → 5 → 1 → 9 → 4.(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? נמקו את תשובתכם.
what(lst.getNext(), lst.getValue()) מוחקת מההמשך את כל החוליות עם הערך של החוליה הנוכחית. החוליה הנוכחית מתחברת להמשך הנקי, ו-guess ממשיכה לחוליה הבאה.| קריאה על החוליה | מה נמחק מההמשך | 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 מופעלת רק על ההמשך שלה.
(1) בסיום הפעולה: lst = 1 → 3 → 5 → 9 → 4 → null.
(2) הפעולה מוחקת מהשרשרת את הכפילויות: מכל ערך נשארת רק ההופעה הראשונה שלו (סדר ההופעות הראשונות נשמר).
(3) O(n²), כש-n הוא מספר החוליות: לכל חוליה מופעלת what על ההמשך שלה, שאורכו n − 1, n − 2, …, 0. הסכום הוא n(n − 1)/2.