רשימה מקושרת מדעי המחשב לכיתה י״ב

בנושא הזה 7 שיעורים. כך הם מתחילים:

1. הפניות והממשק Node<T>

   מצביע, הפנייה, חוליה ורשימה: מה קורה בזיכרון כשכותבים new, למה משתנה של עצם הוא בעצם "כתובת", הממשק Node<T> (שני בנאים, getValue, getNext, hasNext, setValue, setNext), ותרשימי חוליות.

2. בנייה, מעבר והדפסה של רשימה

   בניית רשימות (מהסוף, הכנסה בראש, הכנסה בסוף עם מצביע לאחרונה) ומעבר על רשימה עם מצביע עזר p: הדפסה, אורך, סכום, ספירת זוגות סמוכים. ההבדל בין `p != null` ל-`p.hasNext()` ומתי משתמשים בכל אחד.

3. הכנסה ומחיקה

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

4. חיפוש, ספירה והכנסה ממוינת

   חיפוש וספירה ברשימה (indexOf, ערכים שונים ברשימה ממוינת, חוליה עם ערך מינימלי ברשימת עצמים), הכנסה לרשימה ממוינת ובניית רשימה ממוינת, ובניית רשימה מספרות של מספר - בסגנון שאלה 1 בבגרות.

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

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

6. יעילות: רשימה מול מערך

   יעילות פעולות על רשימה (O(1) מול O(n)), רשימה מול מערך, הקצאת זיכרון סטטית ודינמית, שרשרת חוליות BinNode, קריאת המימוש של Node (הכמסה), ומה לא בחומר (רשימה דו-כיוונית, מימוש מבני נתונים).

7. חזרה: רשימה מקושרת

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

→ תורעצים בינאריים ←