מבנה נתונים - רשימה מקושרת (linked list)

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

רשימה מקושרת חד צדדית

 

כאן מתוארת רשימה מקושרת עם 3 חוליות. המונח המקצועי לחוליה הראשונה ברשימה זה ראש ( head) והחוליה האחרונה ברשימה נקראית הזנב (tail).

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

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

 

מימוש חוליה מקושרת

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

שימו לב, שאני משמיט הרבה פרטים כדי לשמור על פשטות הקוד (לדוגמא אני לא מוודא פרמטרים).

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

 

גישה לחוליה ברשימה

כדי לגשת לאיבר בחוליה, כל מה שעלנו לעשות הוא לדלג בין כל החוליות עד לאיבר הרצוי. סיבוכיות זמן ריצה - O(n).

הוספת איבר לרשימה

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

סיבוכיות זמן ריצה של אלגוריתם הזה הוא  O(n).

מחיקת איבר מהרשימה

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

הערה

אם אתם רוצים להשתמש ברשימה מקושרת בפרויקט שאתם כותבים, עדיף לכם להשתמש במימוש שמגיעה עם השפה. פשוט מאוד, המימוש שאני מביא כאן הוא מאוד מופשט ולא כולל בתוכו הרבה פרטים כמו בדיקת קלט ומקרי קצה. ב #C קיימת מחלקה כזאת - System.Collections.Generic.LinkedList ולרוב השפות יש גם מימוש דומה משלהם.

 

תרגילים

  1. ממש את מבנה הנתונים רשימה מקושרת בשפה לבחירתך.לא חייב בצורה גנרית, אפשר מספר במקום. שים לב שהדוגמאות קוד שהבאתי נועדו להעביר רעיון כללי ולא לשמש כמימוש יעיל. בתרגיל יש לוודא קלט מהמשתמש, ולוודא מקרי קצה (לדוגמא עם מנסים למחוק את החוליה הראשונה הקוד יקרוס).
  2. קבל 10 מספרים מהמשתמש, שמור אותו ברשימה מקושרת והדפס את הקלט בסדר הפוך.
  3. צור פונקציה שמקבלת רשימה מקושרת ומחזירה את אורכה.
  4. צור פונקציה שמקבלת מספר מסוים ומחפשת אותו ברשימה מקושרת,  ומחזירה את החוליה הראשונה שמחזיקה את הערך הזה. החזר null אם הערך לא קיים.
  5. צור פונקציה שמקבלת מספר ורשימה מקושרת ומחזירה רשימה מקושרת חדשה שמכילה את כל המספרים שקטנים מהמספר שהיא קיבלה. לדוגמא:

         עבור קלט מספר = 4 ורשימה = 1->2->3->4->5 יצופה פלט של 1->2->3