אתם לא משתמשים ברשימות מקושרות. אבל הן מריצות מחצית מהתוכנה שלכם.

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

אתם לא צריכים ללמוד רשימות מקושרות כדי לממש אותן. אתם לומדים אותן כדי להבין את הכלים שבהם אתם משתמשים מדי יום.

הן נמצאות בכל מקום: • כפתורי "אחורה" ו"קדימה" בדפדפן. • היסטוריית ה-undo בעורכי טקסט. • LRU caches בשרתי אינטרנט ובמסדי נתונים. • פקודות list ב-Redis. • מתזמן התהליכים (process scheduler) של ליבת ה-Linux.

הן אינן שרידים מעבר. הן תשתית.

הסיבה האמיתית לכך שרשימות מקושרות מתקשות היא cache locality (מקומיות המטמון). המעבד (CPU) שלכם לא קורא מה-RAM בייטים בודדים בכל פעם. הוא שואב גוש של 64 בתים הנקרא cache line.

מערכים הם מהירים כי הם יושבים יחד בזיכרון. המעבד קורא את האיבר הראשון ומקבל את 15 הבאים בחינם.

רשימות מקושרות הורסות את זה. כל צומת (node) יושב בנקודה שונה בזיכרון. מעקב אחר מצביע (pointer) מאלץ את המעבד לקפוץ לכתובת חדשה. זה מפעיל שליפה חדשה מה-RAM. זה עולה מאות מחזורי מעבד (CPU cycles).

בחומרה מודרנית, מעבר על מערך (array traversal) יכול להיות מהיר פי 10 עד 100 ממעבר על רשימה מקושרת. סימון Big-O מתעלם מהעלות הקבועה הזו.

אז מתי משתמשים בהן?

השתמשו ברשימה מקושרת חד-כיוונית (singly linked list) עבור מחסניות (stacks) או תורי משימות פשוטים שבהם אתם רק מוסיפים או מסירים מקצה אחד.

השתמשו ברשימה מקושרת דו-כיוונית (doubly linked list) כשאתם זקוקים למחיקה בסיבוכיות O(1) עם הפניה ישירה לצומת. זה הסוד של ה-LRU cache.

LRU cache זקוק ל:

  • חיפוש (lookup) בסיבוכיות O(1).
  • הכנסה (insertion) בסיבוכיות O(1).
  • הוצאה (eviction) בסיבוכיות O(1).
  • קידום (promotion) בסיבוכיות O(1).

מערך לא יכול לעשות זאת מכיוון שהזזת פריטים דורשת להזיז את כל שאר הפריטים. hash map לבדו לא יכול לעשות זאת כי אין לו סדר.

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

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

מקור: https://dev.to/islamhafez0/you-dont-use-linked-lists-but-theyre-running-half-your-software-4b37