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

1. למה רשימה מקושרת שווה את המאמץ

הדבר שהכי קל לעשות ברשימה מקושרת הוא להכניס חוליה חדשה בתחילת הרשימה - שם כל מה שצריך לעשות זה להחליט שהחוליה החדשה תהיה תחילת הרשימה ולעדכן את המצביעים.

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

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

2. רשימה מקושרת וכתיב פונקציונאלי

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

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

גישה טובה יותר משתמשת במבנה נתונים שנקרא Zipper. במבנה כזה אנחנו שומרים רשימה של שלושה דברים:

1. הראשון הוא רשימת האלמנטים ש"לפני" המקום בו אנחנו נמצאים, אותם נשמור בסדר הפוך.

2. לאחר מכן נשמור את האלמנט עליו אנחנו מסתכלים.

3. ונסיים עם רשימת כל האלמנטים שאחרי המקום עליו אנחנו מסתכלים.

לדוגמא אם ניקח את הרשימה 10, 20, 30, 40, 50 ונרצה להתמקד במקום האמצעי שבה, כלומר המספר 30, נוכל לשמור את מבנה הנתונים הבא:

[(20 10) 30 (40 50)]

שמירת המידע בצורה כזו מאפשרת ביצוע פעולות בצורה יעילה על הרשימה. נקרא לשלושת החלקים במבנה before, current ו after בהתאמה ואז:

1. בשביל "לזוז" ימינה צריך לקחת את האיבר הראשון מהרשימה after ולהפוך אותו ל current, ולהוסיף את ה current הקודם לתחילת הרשימה before. בדוגמא שלנו ניקח את 40 ונהפוך אותו ל current, וניקח את 30 ונשים אותו בתחילת הרשימה before. שתי הפעולות הן מאוד מהירות בשפה פונקציונאלית.

2. בשביל לזוז "שמאלה" צריך לקחת את האיבר הראשון מהרשימה before ולשים אותו באמצע, ואת מה שהיה קודם באמצע להעביר להיות האיבר הראשון ב after. גם כאן מדובר על שתי פעולות שעובדות מאוד מהר בשפה פונקציונאלית.

3. בשביל להוסיף אלמנט מימין לאלמנט עליו מסתכלים צריך רק להוסיף את האלמנט החדש לתחילת הרשימה after. שוב פעולה מאוד מהירה בשפה פונקציונאלית.

4. בשביל למחוק את האלמנט עליו אנו מסתכלים מספיק לקחת את האלמנט הראשון מ before או מ after ולהפוך אותו ל current החדש, ולמחוק אותו מהרשימה בה הוא היה.

מבנה הנתונים Zipper לכן מאפשר לנו לשמור מידע כך שיהיה קל להוסיף אלמנטים חדשים באמצע בלי שנצטרך להעתיק רשימות ארוכות ובלי שנצטרך לעדכן מצביעים, וכך כל המידע שלנו יוכל להמשיך להיות Immutable.

3. מימוש רשימה מקושרת ב Clojure באמצעות Zipper

וכמובן מטרת הבלוג הזה היא לא לקשקש כל מיני רעיונות באוויר אלא לדבר ולהתאמן על קוד אז הלכתי לכתוב את המנגנון בשפת Clojure. התוצאה מאוד ברורה וגם אם אתם לא מכירים קלוז'ר נדמה לי שתוכלו לראות בקלות איך האלגוריתם שתיארתי מתחבר לפונקציות בקוד:

(ns aoc2018.linkedlist)

(defn to-vec
  [[before current after]]

  (vec (concat (reverse before) [current] after)))

(defn make
  [items focus-index]
  [(reverse (take focus-index items)) (get items focus-index) (drop (inc focus-index) items)]
  )

(defn current
  [[before current after]]
  current)

(defn right
  [[before current after]]
  [
   (cons current before)
   (first after)
   (drop 1 after)
   ]
  )

(defn left
  [[before current after]]
  [
   (drop 1 before)
   (first before)
   (cons current after)
   ]
  )

(defn insert-before
  [[before current after] new-item]
  [
   (cons new-item before)
   current
   after
   ]
  )

(defn insert-after
  [[before current after] new-item]
  [
   before
   current
   (cons new-item after)
   ]
  )


(defn remove
  [[before current after]]

  [
   before
   (first after)
   (drop 1 after)
   ]
  )

4. מה עוד חסר

הבעיה היחידה עם Zipper היא שקשה לראות איך לממש רשימה מקושרת מעגלית בתוך המבנה הזה. בשביל להגיע מסוף הרשימה לתחילתה צריך לרוץ על כל רשימת ה before ולהפוך אותה - פעולה שעשויה לקחת זמן אם יש הרבה אלמנטים. אותו דבר אם אנחנו בתחילת הרשימה ורוצים לחזור במעגל לסוף נצטרך לרוץ על כל רשימת after ולהפוך אותה.

בכתיב אימפרטיבי רגיל אין לנו את הבעיה הזאת כי קל להגדיר את מצביע ״הבא״ של האלמנט האחרון ברשימה שיצביע על האלמנט הראשון ולהיפך. אם יש לכם רעיונות איך להוסיף מעגליות לרשימה כזו או מכירים מנגנונים פונקציונאליים אחרים לשמירת רשימה מקושרת מעגלית אשמח לשמוע בתגובות.