מירירשימה מקושרת חוליות ומצביעים
רשימה מקושרת היא שרשרת של חוליות. בכל חוליה יש ערך, ומצביע לחוליה הבאה. כדי להגיע לחוליה השלישית הולכים לאורך השרשרת, צעד אחרי צעד. כאן מוסיפים ומוחקים חוליות, ורואים בדיוק אילו חיצים משתנים. החוליה היא עצם, אז כדאי לחזור קודם על מחלקות ועצמים. אחר כך אפשר להמשיך לעצים בינאריים, שם לכל חוליה יש שני מצביעים.
הרעיון
class Node:
def __init__(self, value):
self.value = value
self.next = None
head = Node(4)
head.next = Node(7) # 4 -> 7 -> None
חוליה ו-head
לכל חוליה יש value ו-next. המשתנה head מצביע על החוליה הראשונה. ב-next של האחרונה יש None: כאן השרשרת נגמרת.
מעבר על השרשרת
מתחילים ב-head, ובכל צעד עוברים ל-node.next, עד שמגיעים ל-None. אין קפיצה ישירה לחוליה מספר 5.
הוספה ומחיקה
מוסיפים חוליה בשינוי של שני חיצים, ומוחקים בשינוי של חץ אחד: מדלגים מעליה. אין צורך להזיז את כל שאר הערכים.
| פעולה | רשימה של פייתון | רשימה מקושרת |
|---|---|---|
| להגיע לערך במקום k | מיד: a[k] | הולכים k צעדים מ-head |
| להוסיף בהתחלה | כל הערכים זזים מקום אחד | מיד: שני חיצים |
| למחוק מהאמצע, כשכבר עומדים שם | כל הערכים שאחריו זזים | מיד: חץ אחד |
מעבדה: מזיזים חיצים
בהתחלה השרשרת היא 4 → 7 → 9. בחרו פעולה, ערך ומקום. לחצו "שורה הבאה" וראו את החוליות והחיצים משתנים. שמות המשתנים מופיעים מעל החוליה שהם מצביעים עליה.
נסו את אלה:
הריצו בעצמכם
אפשר לשנות את הקוד ולהריץ פייתון אמיתי. בפעם הראשונה הטעינה לוקחת כמה שניות.
טעויות שכולם עושים
הסדר בהוספה
אם קודם מכוונים את cur.next לחוליה החדשה, כבר אין דרך להגיע לחוליה שהייתה אחריו.
✗ ההמשך אבד
cur.next = new
new.next = cur.next✓ קודם מחברים
new.next = cur.next
cur.next = newהולכים מעבר לסוף
אחרי החוליה האחרונה מגיעים ל-None. ל-None אין next, ומקבלים AttributeError.
✗ AttributeError
while True:
node = node.next✓ עוצרים ב-None
while node is not None:
node = node.nextמאבדים את head
אם עוברים על השרשרת עם head עצמו, בסוף head הוא None, וכל השרשרת אבדה. משתמשים במשתנה עזר.
✗ head נהרס
while head is not None:
head = head.next✓ משתנה עזר
node = head
while node is not None:
node = node.nextמחיקת החוליה הראשונה
לחוליה הראשונה אין חוליה לפניה. כדי למחוק אותה מזיזים את head עצמו.
✗ מוחק את השנייה
head.next = head.next.next✓ מוחק את הראשונה
head = head.nextדוגמה פתורה: בונים מההתחלה וסוכמים
מכניסים את 3, 8, 5 לשרשרת, כל אחד בהתחלה. אחר כך עוברים על השרשרת וסוכמים. שימו לב לסדר שיוצא: הוספה בהתחלה הופכת את הסדר.
תרגול
שאלות שכולם שואלים
מה זו רשימה מקושרת?
מבנה נתונים שבנוי משרשרת של חוליות. בכל חוליה יש ערך ומצביע לחוליה הבאה, ובחוליה האחרונה המצביע הוא None. המשתנה head מצביע על החוליה הראשונה. נסו במעבדה.
מה ההבדל בין רשימה מקושרת לרשימה רגילה בפייתון?
ברשימה של פייתון מגיעים מיד לכל מקום לפי אינדקס, אבל הוספה בהתחלה מזיזה את כל הערכים. ברשימה מקושרת הוספה ומחיקה הן רק שינוי של חיצים, אבל כדי להגיע לחוליה צריך ללכת אליה מ-head.
למה מקבלים AttributeError: 'NoneType' object has no attribute 'next'?
כי הלכתם צעד אחד יותר מדי. אחרי החוליה האחרונה המשתנה הוא None, ול-None אין next. בדקו את התנאי של הלולאה, או כמה צעדים אתם הולכים. תרגלו למטה.