נהגי המוניות של לונדון נדרשים ללמוד מספר גדול של מקומות – ולדעת את הדרך הישירה ביותר ביניהם (להבדיל מנהגי המוניות הישראלים, עמיתיהם הלונדונים נדרשים לעבור מבחן נוקשה של ידע לפני קבלת הרישיון לנהוג באחת המוניות הלונדוניות המפורסמות). אחד המחקרים הראה כי חלק מההיפוקמפוס גדול יותר בקרב נהגים אלו, בהשוואה לציבור הרחב, וכי לנהגי מוניות מנוסים יותר יש היפוקמפוס גדול יותר. ייתכן כי לאנשים שמראש היה להם היפוקמפוס יחסית גדול יותר, היה קל יותר להפוך לנהגי מוניות. כמו כן נראה כי מציאת קיצורי דרך כדרך להתפרנס יכולה לגרום להיפוקמפוס שלנו לגדול. ההיפוקמפוס הוא אחד משני האזורים היחידים במוח שידוע שיש בהם תהליך של נוירוגנזה, צמיחת נוירונים חדשים במוח מפותח. האזור השני הוא פקעת ההרחה.
רשימה מקושרת
רשימה מקושרת (באנגלית: Linked list) היא אחד ממבני הנתונים הבסיסיים ביותר הנמצאים בשימוש במדעי המחשב, כאשר מטרתה היא אחסון נתונים בצורה יעילה. הרשימה המקושרת היא אוסף איברים המפוזרים בזיכרון מחשב, כך שבכל איבר מאוחסן מידע (אחד מאותם נתונים אותם רצינו לאחסן) וכן מצביע לאיבר הבא ברשימה. נקראת גם רשימה משורשרת. לעיתים קוראים לרשימה מקושרת בפשטות "הרשימה" על מנת לקצר.
הגדרת רשימה מקושרת ופעולות בסיסיות.
הקודים המופיעים מתחת לכל פעולה הם פסאודו-קודים, וכתובים בשפה בעלת דמיון לשפה C.
הגדרה.
הרשימה מכילה איברים, באנגלית Nodes. כל איבר מורכב משני אלמנטים:
struct "Node"
data // הנתון הנשמר באיבר
next // מצביע או רפרנט לאיבר הבא ברשימה
בנוסף, שומרים את מיקומו של האיבר הראשון ברשימה. דרך איבר זה ניתן להגיע לכל איברי הרשימה, באמצעות מעבר מכל איבר לאיבר הבא.
struct "List"
"Node" firstNode // מצביע לאיבר הראשון ברשימה
מצביע יכול לקבל את הערך Null, שמשמעותו היא שהמצביע אינו מצביע על מקום תקני בזיכרון. אם שדה ה-next באיבר מסוים מצביע ל-Null, משמעות הדבר שזהו האיבר האחרון ברשימה. אם השדה firstNode מצביע אל עבר Null, משמעות הדבר שהרשימה היא רשימה ריקה (רשימה שאין בה אף איבר).
הוספת איבר.
עלינו לדעת תחילה היכן ברצוננו להכניס את האיבר החדש, כלומר, אחרי איזה איבר יבוא האיבר החדש. לשם הפשטות, נניח שאנו רוצים להכניס איבר שנסמנו ב' בין שני איברים עוקבים שנסמנם א' ו-ג'. כעת תתבצע ההכנסה בשלושה שלבים פשוטים:
insert("Node" node, "Node" newNode)
newNode.next &lt;- node.next
node.next &lt;- newNode
יש לשים לב לכך שסדר הפעולות הוא משמעותי, אם נכוון קודם את מצביע א' אל מצביע ב', נאבד את הקשר בין איבר א' לאיבר ג', ובעצם לכל שאר הרשימה.
כאשר נרצה להכניס את האיבר החדש לתחילת הרשימה (ובכך בעצם להופכו לאיבר הראשון), נצטרך לעדכן את המצביע firstNode, המורה מיהו האיבר הראשון ברשימה. כעת הליך ההכנסה יהיה:
insertBeginning("List" list, "Node" newNode)
newNode.next &lt;- list.firstNode
list.firstNode &lt;- newNode
הסרת איבר.
כאשר ברצוננו להסיר איבר מסוים מהרשימה, נכנה את האיבר הבא אחריו ברשימה "האיבר הבא למוסר" ואת האיבר הקודם לו ברשימה "האיבר הקודם למוסר". כעת הליך ההסרה יתבצע בשני שלבים פשוטים:
מכיוון שרשימה מקושרת היא רשימת איברים שבה כל איבר מצביע לאיבר הבא אחריו, במקרה שקיים איבר שאף אחד לא מצביע אליו, הוא למעשה אינו איבר באותה הרשימה. אין מונח של "חור" ברשימה, כך שמרגע ששינינו את המצביע של האיבר הקודם למוסר, האיבר שרצינו להסיר נעלם מן הרשימה. אם כן, השלב השני בפעולת ההסרה הוא למטרות ניקוי הזיכרון, אך למעשה מרגע שינוי המצביע ההסרה כבר בוצעה בהצלחה.
משום שברשימה מקושרת בגרסתה הקלאסית אין באפשרותנו לחזור אחורה לאיבר הקודם, אין לנו דרך מהירה ויעילה לדעת מיהו האיבר הקודם למוסר. נעדיף להסתכל על ההליך כולו כהסרת איבר הבא אחרי איבר, כלומר, ידוע לנו מראש מיהו האיבר הקודם למוסר וכעת אנו רוצים להסיר את האיבר הבא אחריו. דרך הסתכלות זו איננה מהווה התחמקות מהבעיה, שכן בפעמים רבות באמת ידוע לנו מיהו האיבר הקודם למוסר מראש, אם בשל תכנון נכון של המערכת שבנינו או משום שהאלגוריתם בו אנו משתמשים מספק אותו.
removeAfter("Node" node)
obsoleteNode &lt;- node.next
node.next &lt;- node.next.next
destroy obsoleteNode
במקרה המיוחד בו נרצה למחוק את האיבר הראשון ברשימה, נצטרך לעדכן את המצביע firstNode, המורה מיהו האיבר הראשון ברשימה. כעת הליך ההסרה יהיה:
removeBeginning("List" list)
obsoleteNode &lt;- list.firstNode
list.firstNode &lt;- list.firstNode.next
destroy obsoleteNode
יש להיזהר ממקרה של רשימה ריקה, מקרה בו firstNode מצביע אל עבר Null. כזכור, Null אינו באמת איבר ברשימה אלא רק סימון האומר שמצביע זה אינו מצביע על איבר ברשימה. ניסיון לגשת לשדה next ב-Null יוביל לשגיאה. נהוג להניח שפעולה זו לא נעשית על רשימה ריקה, כלומר, בעת תכנות עלינו לוודא שהרשימה אינה ריקה לפני ביצוע פעולה זו.
חיפוש איבר.
כאשר מדברים על חיפוש איבר ברשימה, הכוונה היא לחיפוש איבר המחזיק ערך מסוים. מה שמעניין הוא הערך ולא האיבר שכן, כפי שצוין קודם, מטרת האיבר היא בסך הכול שמירה על הערך ומתן גישה נוחה אליו. אם כן, בהנחה שאנו מחפשים ערך_מבוקש יתנהל החיפוש בצורה הבאה:
בעת מימוש הפעולה בפועל, יש לשים לב לכמה נקודות:
search("List" list, "DataType" data)
node &lt;- list.firstNode
while node != Null
if node.data == data
return node
node &lt;- node.next
return Null
מעבר סדרתי על איברי הרשימה.
חיפוש איבר נעשה על ידי מעבר על כל האיברים עד אשר נמצא האיבר המתאים או שהגענו לסוף הרשימה. לעיתים לא נרצה להפסיק כאשר הגענו אל איבר מסוים, אלא נרצה להמשיך ולעבור על כל איברי הרשימה עד אשר הגענו לסופה. לרוב, נרצה לבצע פעולות מסוימות על האיברים תוך כדי המעבר. ההליך יראה כך:
function("List" list, ...)
node &lt;- list.firstNode
while node != null
"(do something with node)"
node &lt;- node.next
שימו לב לשלוש הנקודות (...) שהוכנסו לאחר הפרמטר הראשון בפונקציה לעיל, תלוי בפעילות הנדרשת על האיברים, הפונקציה עלולה להזדקק לפרמטרים שונים ואולי לא תזדקק כלל לאף פרמטר נוסף.
לרוב, הפעולה על האיבר תהיה קשורה למידע השמור בו. למרות זאת, זהו לא תמיד המצב ולעיתים אף הנתון כלל לא יעניין אותנו. דוגמה לכך היא הפונקציה הבאה המקבלת רשימה מקושרת והופכת את סדר איבריה.
inverseList("List" list)
node &lt;- list.firstNode
newNext &lt;- Null
while node != Null
tmp &lt;- node.next
node.next &lt;- newNext
newNext &lt;- node
node &lt;- tmp
list.firstNode &lt;- newNext // האיבר הראשון ברשימה הוא מי שקודם לכן היה האחרון
תכונות הרשימה המקושרת.
תכונתה הבולטת של הרשימה המקושרת היא העובדה כי האיברים אינם נמצאים ברצף בזיכרון המחשב, בניגוד למערך למשל. עובדה זו משמשת כחרב פיפיות שכן היא יתרונה וחסרונה הגדול של הרשימה המקושרת.
יתרונות.
יתרונותיה הבולטים של הרשימה המקושרת הם בתחום הוספת איבר והוצאת איבר מן הרשימה.
יתרון גדול של הרשימה המקושרת בא לידי ביטוי דווקא ברשימות מקושרות בהן ישנה חשיבות לסדר האיברים (רשימה מקושרת ממוינת למשל). בעת הכנסת איבר אנו חייבים להכניסו במקום מדויק. עקב המבנה הייחודי של הרשימה המקושרת, כל שנצטרך לעשות יהיה להכניס את האיבר במקום כלשהו בזיכרון המחשב, לכוון את מצביעו אל עבר האיבר שברצוננו שיבוא אחריו ברשימה ולכוון את מצביע האיבר שברצוננו שיבוא לפניו, אל עברו. מדובר בשתי פעולות קבועות שאינן תלויות במספר איברי הרשימה ולכן נאמר שיעילות זמן הריצה היא formula_1.
הוצאת איבר תתבצע בצורה דומה. נכוון את המצביע של האיבר הקודם לזה שאנו מוציאים כך שיצביע על האיבר הבא ואז נמחק את האיבר. שוב מדובר בפעולות קבועות ללא תלות במספר איברי הרשימה המקושרת ולכן גם כאן יעילות זמן הריצה formula_1.
לא נצטרך באף אחד מהמקרים לטפל בשאר איברי הרשימה המקושרת שכן הסדר ביניהם נשמר! לא קיימת תופעה של "חורים" ברשימה המקושרת כיוון שאין חשיבות למיקום אחסונם של האיברים, רק למצביעים.
עובדה זו היא יתרון גדול, בייחוד בהשוואה למבני נתונים כמו המערך בו נצטרך לסדר את האיברים לאחר הוצאת איבר מן האמצע, או לחלופין אם הוספנו יותר איברים ממה שציפינו, להקצות מקום חדש בזיכרון ולהעתיק אליו את כל האיברים הקיימים, פעולות הנמצאות בקשר ליניארי (ישר) עם איברי המערך ולכן יעילות זמן ריצתם formula_3.
חסרונות.
חסרונה הבולט של הרשימה המקושרת הוא בתחום הגישה לאיברים, או יותר נכון בתחום חיפוש האיברים.
עקב פיזור האיברים בכל רחבי זיכרון המחשב, כאשר נחפש איבר כלשהו נצטרך להתחיל מהאיבר הראשון ולהתקדם איבר אחד בכל פעם, עד אשר נגיע לאיבר המבוקש. כלומר, כל חיפוש יצרוך מאיתנו זמן ריצה formula_3. אפילו אם ברשותינו רשימה מקושרת ממוינת, לא נוכל להשתמש באלגוריתמי חיפוש מתוחכמים כמו חיפוש בינארי (ידוע גם כשיטת האריה במדבר). גם אם נדע במדויק את מספרו של האיבר אותו אנו מחפשים, עדיין לא נוכל להתחמק ממעבר על כל האיברים עד איבר זה.