מבנה נתונים מסוג linked list (רשימה מקושרת) הוא אחד ממבני הנתונים הבסיסים שלומדים במדעי המחשב. בפוסט הזה אדגים איך מממשים בקלות רשימה מקושרת באמצעות פייתון. שנצלול?
ראשית ננסה להבין מהי רשימה מקושרת ומתי היא טובה לנו לשימוש.
רשימה מקושרת היא למעשה מבני נתונים שבו יש לנו איברים ברשימה (אנחנו נקרא לאיברים Nodes) כשכל איבר מצביע על האיבר הבא ברשימה.
רשימה מקושרת היא מבנה נתונים מסודר על פי סדר ההכנסה (עוד על זה בהמשך).
כל איבר ברשימה המקושרת מצביע על האיבר הבא או על None. ברגע שהוא מצביע על None זה אומר שהגענו לסוף הרשימה המקושרת (אנחנו מדברים כאן על רשומה מקושרת הכי בסיסית שיש).
כדי לממש את ה Nodes נממש מחלקה פשוטה שכוללת את המידע של ה Node ואת הערך שאליו ה Node מצביע (כלומר מה ה Node הבא):
בקצרה כל מה שיש לנו כאן זו מחלקה שכוללת את המידע (הערך) של ה node בתוך משתנה מחלקה בשם data ועוד משתנה של next שערכו כפי שנראה בהמשך יהיה למעשה ה node הבא.
פונקצית ה __repr__ היא רק כדי שנקבל יצוג ברור לעין של ה node כשנעשה print לאובייקט.
נממש מחלקה נוספת, linkedList שהיא למעשה תספק לנו את נקודת הכניסה (תצביע על ה node הראשון) ואת הפונקציונליות השונה שנצטרך כמו הוספה, הסרה, ריצה על האיברים השונים וכו׳.
נתחיל עם המימוש הכי בסיסי:
התבוננו בהן, וענו לעצמכם על השאלות הבאות: למה נדרשו שתי פונקציות שונות? נסו לממש הוספה באמצע הרשימה. ובעיקר נסו לחשוב על הסיבוכיות ריצה של השליפות וההכנסות השונות:
שמים לב לצורה המוזרה שבה add_last עובדת? אנחנו רצים על כל הרשימה רק כדי לקבל את האיבר הנכון לנו (שהוא האיבר האחרון). חשבו על הסיבוכיות במקרה הזה.
נממש גם פונקציה pop - הוצאה של איבר (מחיקה מהרשימה המקושרת) והחזרתו: דומה ל pop שאנחנו מכירים מ list פייתוני סטנדרטי:
נסו לבצע אופטימיזציה לפונקציה הזו (יש אחת שדי זועקת והשארתי במכוון).
שימו לב שאנחנו מבצעים איטרציה על self ובזכות המימוש שלנו של __iter__ המשמעות היא למעשה ריצה על כלל ה nodes שלנו.
והנה מימוש של שליפת node מסוים מהרשימה:
אין תגובות:
הוסף רשומת תגובה