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