רשימה מקושרת מוסברת בפשטות - Linked List¶
רשימה מקושרת היא אחד המבנים הראשונים שגורמים למתחילים להרגיש טיפשים. מסבירים לכם על "צמתים" ו"מצביעים", אתם מהנהנים כאילו הבנתם, ואז מבקשים מכם לכתוב קוד וזה מתפרק. אז בואו נעצור, ונסביר את זה בלי שום מונח מפחיד, עם תמונה בראש שתישאר אצלכם לתמיד.
תדמיינו שרשרת פתקים¶
תדמיינו שאתם משחקים משחק חיפוש מטמון בילדות. כל פתק אומר לכם שני דברים: איפה נמצא הרמז הבא, ולאן ללכת כדי למצוא את הפתק הבא. אין לכם רשימה מסודרת מראש של כל התחנות. יש לכם רק את הפתק שבידיים, ואת ההוראה איפה למצוא את הבא.
זו בדיוק רשימה מקושרת. במקום שכל המידע יישב זה לצד זה בזיכרון בשורה מסודרת, כמו במערך רגיל, כל פריט מידע - שנקרא "צומת" - מחזיק שני דברים: את הערך עצמו, ואת הכתובת בזיכרון של הצומת הבא. וזהו. זה כל הרעיון.
אז למה בכלל לא פשוט להשתמש במערך¶
כאן זה נהיה מעניין. במערך רגיל, כל האיברים יושבים אחד ליד השני בזיכרון, בבלוק אחד רציף. זה נהדר לגישה מהירה - אם אתם רוצים את האיבר ה-500, המחשב קופץ ישר אליו. אבל זה גרוע כשאתם רוצים להוסיף או להוריד איבר מהאמצע, כי המחשב צריך להזיז את כל האיברים שאחריו כדי לפנות מקום.
ברשימה מקושרת המצב הפוך. כדי להוסיף פריט חדש באמצע, אתם פשוט משנים שני "חצים" - הצומת שלפני מפנה עכשיו לצומת החדש, והצומת החדש מפנה למי שהיה אחריו במקור. שום דבר לא זז בזיכרון. זו פעולה כמעט מיידית, בלי קשר לכמה איברים יש ברשימה.
המחיר: אין לכם דרך "לקפוץ" ישר לאיבר ה-500. כדי להגיע אליו, אתם חייבים ללכת צעד-צעד מההתחלה, כמו במשחק חיפוש המטמון. אין קיצור דרך.
שני סוגים שכדאי להכיר¶
- רשימה מקושרת חד כיוונית - Singly Linked List. כל צומת מצביע רק קדימה, לצומת הבא. אפשר ללכת רק בכיוון אחד.
- רשימה מקושרת דו כיוונית - Doubly Linked List. כל צומת מצביע גם קדימה וגם אחורה. יותר גמישה, אבל תופסת קצת יותר זיכרון כי כל צומת שומרת שני חצים במקום אחד.
רוב השפות ברמה גבוהה, כמו פייתון, מסתירות ממכם את המבנה הזה ונותנות לכם רשימה רגילה שמתנהגת בעיקר כמו מערך. אבל ברגע שאתם עוברים לשפות כמו C או ג'אווה, או פשוט לומדים איך המבנים האלה בנויים מתחת למכסה המנוע, רשימה מקושרת היא אחד הדברים הראשונים שתבנו בעצמכם.
מתי באמת משתמשים ברשימה מקושרת¶
הרשימה המקושרת לא נעלמה, היא פשוט עובדת מאחורי הקלעים במקומות שאתם אולי לא שמים לב אליהם:
- תור הפעלה של תוכנות במערכת ההפעלה.
- מבנה ה-undo/redo בעורכי טקסט, שם כל פעולה מצביעה על הפעולה שלפניה.
- מימוש פנימי של מבנים אחרים, כמו מחסנית ותור, שנבנים לרוב על בסיס רשימה מקושרת.
זה לא מבנה שתשתמשו בו כל יום כמפתחים, אבל הבנה שלו היא בדיוק מה שמלמד אתכם לחשוב על זיכרון, מצביעים וקישורים בין נתונים - יסודות שחוזרים בכל תחום בתכנות, מפיתוח אתרים ועד אבטחת מידע.
איך באמת מבינים את זה¶
הדרך היחידה להפנים רשימה מקושרת היא לבנות אחת בעצמכם מאפס, בלי לגעת בספרייה מוכנה. תכתבו קלאס לצומת, תוסיפו פונקציה שמוסיפה איבר בסוף, פונקציה שמוסיפה בהתחלה, ופונקציה שמוחקת איבר מהאמצע. תוך שעה של תרגול תרגישו שהמונחים "צומת" ו"מצביע" הפכו מאיום למשהו טבעי לגמרי.
בקורס התכנות הבסיסי שלנו יש בדיוק את המדרגות האלה - מהיסודות של פייתון ועד לבניית מבני הנתונים האלה בעצמכם, צעד אחר צעד.
תתחילו את קורס התכנות הבסיסי כאן
לסיכום¶
רשימה מקושרת היא לא יותר מסדרה של פתקים שכל אחד מצביע לבא אחריו. אין שם קסם, יש שם רק רעיון פשוט שפותר בעיה אמיתית - איך להוסיף ולמחוק מידע במהירות בלי להזיז הכל. ברגע שהתמונה הזו נכנסת לראש, כל הקוד סביבה נהיה הרבה יותר הגיוני.
נתקעתם באמצע התרגול? זה בדיוק מה שהדיסקורד שלנו נועד בשבילו.