שיעור 10: רשימות מקושרות

דמיין/י ציד אוצר: כל פתק מחזיק ערך ורמז לפתק הבא, וכדי להגיע לחמישי חייבים לעבור אחד-אחד. זו 'רשימה מקושרת' (linked list) — שרשרת של 'צמתים' (nodes). היתרון: הוספה/מחיקה באמצע היא O(1), רק משנים לאן מצביע הרמז. החיסרון: הגעה למיקום מסוים איטית, O(n), כי הולכים רמז-רמז.

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

מחלקה (class): תבנית לקופסה קטנה עם שדות. class Node מגדירה קופסה עם שני שדות: val (הערך) ו-‎next (מצביע לצומת הבא)‎. Node(1) יוצרת קופסה כזו, ו-self הוא פשוט "הקופסה הנוכחית".
רשימה מקושרת: מבנה נתונים של צמתים שכל אחד מחזיק ערך ומצביע next לצומת הבא; הוספה/מחיקה ליד צומת ידוע ב-O(1), אך גישה לפי מיקום ב-O(n).
צומת (node): יחידת הבניין של רשימה מקושרת: אובייקט קטן שמחזיק ערך (val) ומצביע (next) לצומת הבא, או None בסוף.
מקומיות מטמון (cache locality): המידה שבה נתונים שמשתמשים בהם יחד שמורים קרוב בזיכרון; מערך רציף ידידותי ל-cache, ואילו צמתי רשימה מקושרת מפוזרים ופחות ידידותיים.