רשימה מקושרת

הגדרת רשימה מקושרת ופעולות בסיסיות

הקודים המופיעים מתחת לכל פעולה הם פסאודו-קודים, וכתובים בשפה בעלת דמיון לשפה C.

תכונות הרשימה המקושרת

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

יתרונות

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

חסרונות

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

עוגן

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

רשימה מעגלית

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

רשימה דו-כיוונית

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