C# – מה זה Linked List

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

• לכל פריט ב-LinkedList יש חיבור ישיר לפריט שלפניו(ברשימה מקושרת כפולה גם לזה שמאחוריו).
• במידה והרשימה ריקה, המאפיינים Last ו-Next יקבלו את הערך-Null.
• כל Node בתוך מופע של LinkedList הוא מהטייפ של LinkedList.
• הפריט הראשון ברשימה יקבל את המצביע – Head.
• כל Node מכיל 2 חלקים:
  • Data – כל Node של רשימה מקושרת יכול להכיל Data.
  • Adress – כל Node של רשימה מקושרת מכיל כתובת\מצביע ל-Node הבא אשר נקרא Next

Singly Linked List

כפי שהוסבר, רשימה מקושרת מכילה – Data ו-Adress, המצביע של ה-Node האחרון יצביע ל-null.
שימו לב לתרשים הזרימה הבא ומיד נבאר את הנושא:

כפי שניתן לראות, הפריט הראשון (Head) ברשימה מקושרת זו אשר מכיל את הנתון 10 מקושר אל הבא אחריו בתור אשר מכיל את הנתון 20,
בהתאם לכך זה שמכיל את הנתון 20 – מקושר לזה שאחריו אשר מכיל את הנתון 30.
כאשר הגענו אל הפריט האחרון ברשימה (Last), ה-Next שלו יצביע ל-null.

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

public abstract class BillHandler
{
    protected BillHandler? next;
    protected int data;
    public void SetNext(BillHandler? next)
    {
        this.next = next;
    }
    public abstract void HandleRequest(int amount);
}

למחלקה זו ניצור 4 יורשים : BillHandler200, BillHandler100, BillHandler50, BillHandler20.
ניתן להבין שהרשימה המקושרת שלנו תנוהל דרך המחלקה האבסטרקטית,
כאשר את המחלקות היורשות נוכל לממש כך:

public class BillHandler200 : BillHandler
{
    public BillHandler200()
    {
        data = 200;
    }
    public override void HandleRequest(int amount)
    {
        int newAmount = amount / data;
        if (amount >= data)
        {
            Console.WriteLine($"Giving {data} * {newAmount}");
        }
        if (amount % data = 0)
        {
            if (next != null)
            {
                amount -= newAmount * data;
                next.HandleRequest(amount);
            }
        }
    }
}

בכל אחד מהיורשים נזין את ה-data המתאים, למשל במחלקת BillHandler50 נזין את הערך 50.
במחלקה שמנהלת שטרות של 20 שהיא גם החוליה האחרונה ברשימה המקושרת (Last) נאלץ להוסיף תנאי שיציג למשתמש הודעה שהסכום שהוא מבקש לא תיקני במידה והוא קטן מ-20:

public class BillHandler20 : BillHandler
{
    public BillHandler20()
    {
        data = 20;
    }
    public override void HandleRequest(int amount)
    {
        int newAmount = amount / data;
        if (amount >= data)
        {
            Console.WriteLine($"Giving {data} * {newAmount}");
        }
        if (amount % data = 0)
        {
            if (next != null)
            {
                amount -= newAmount * data;
                next.HandleRequest(amount);
            }
            if(amount < data)
            {
                Console.WriteLine("no bills in the machine to give " + amount);
            }
        }
    }
}

כעת, בפונקציה הראשית של התוכנית נייצר מופעים של המחלקות הרלוונטיות וננסה לבצע 2 משיכות,
אחת של 770 ואחת של 210:

static void Main(string[] args)
{
    BillHandler bh200 = new BillHandler200();
    BillHandler bh100 = new BillHandler100();
    BillHandler bh50 = new BillHandler50();
    BillHandler bh20 = new BillHandler20();

    bh200.SetNext(bh100);
    bh100.SetNext(bh50);
    bh50.SetNext(bh20);
    bh20.SetNext(null);

    Console.WriteLine("Withdrawing 770:\n");
    bh200.HandleRequest(770);
    Console.WriteLine("\nWithdrawing 210:\n");
    bh200.HandleRequest(210);
}

ולאחר שנריץ את התוכנית נקבל את הפלט הבא:

שימו לב כי כאשר מה שנותר לכספומט לתת זה שטר שאינו מנוהל\קיים הוא יציג למשתמש הודעת שגיאה.
התוכנית המלאה בגיטהאב: https://github.com/yehonatan604/LinkedList

Sequenced Singly Linked List

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

במקרה כזה תרשים הזרימה שלנו יראה כך:

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

Doubly Linked List

ברשימה מקושרת כפולה, כל  Node מכיל 2 לינקים(חיבורים ל-Nodes אחרים – Next ו-Prev), הראשון מצביע לקודם בתור והשני מצביע אל הבא בתור. בדומה לרשימה מקושרת רגילה, גם כאן ה-Next של ה-Node האחרון יצביע ל-Null, כך גם ה-Prev של ה-Node הראשון:

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

Sequenced Doubly Linked List

ברשימה מקושרת כפולה מחזורית ה-Next של ה-Node האחרון יצביע ל-Node הראשון,
וה-Prev של ה-Node הראשון יצביע אל ה-Node האחרון:

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

לקריאה מורחבת על רשימות מקושרות באתר של מייקרוסופט יש ללחוץ כאן.