רשימות מקושרות ב-#C

זוכרים מהי רשימה מקושרת?
היום נלמד על רשימות מקושרות ב-#C.

רשימות מקושרות | Linked List

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

הוכחה 1:

        static void Main(string[] args)
        {
            int[] arr1 = new int[5];
            int[] arr2 = new int[5];
            arr2 = arr1;
            arr2[0] = 19;
            Console.WriteLine(arr1[0]); // arr2 ידפיס 19, למרות שביצענו את השינויים על
        }

הוכחה 2:

    class MyClass
    {
        public int x;
    }
    class Program
    {
        static void Main(string[] args)
        {
            MyClass c1 = new MyClass();
            c1.x = 20;
            MyClass c2 = new MyClass();
            c2 = c1;
            c2.x = 25;
            Console.WriteLine(c1.x); // c2 ידפיס 25, למרות שביצענו את השינויים על
        }

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

(לפעמים תכונה זו של #C תפריע לנו, על כך נלמד בהמשך)









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

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


קוד:

    class Node // "המחלקה "צומת
    {
        private int info;
        private Node next; // מכיל את כתובת האיבר הבא ברשימה next האובייקט 
 
 
        // פונקציה בונה שמקבלת רק פרמטר אחד
        public Node(int info)
        {
            this.info = info;
            this.next = null;
        }
 
        // פונקציה בונה שמקבלת שני פרמטרים
        public Node(int info, Node next)
        {
            this.info = info;
            this.next = next;
        }
 
 
 
        // Set -ו Get  פונקציות
 
 
        public int GetInfo()
        {
            return info;
        }
        public Node GetNext()
        {
            return next;
        }
        public void SetInfo(int info)
        {
            this.info = info;
        }
        public void SetNext(Node next)
        {
            this.next = next;
        }
    }
 
    class Program
    {
        // פונקציה ליצירת רשימה מקושרת חדשה על סמך המשתמש
        public static Node CreateList()
        {
            Node head = null, tail = null, p;
            int x;
            while (true)
            {
                Console.WriteLine("Enter info , (-1 to finish): ");
                x = int.Parse(Console.ReadLine());
                //x = Convert.ToInt32(Console.ReadLine()); // אגב אפשר להמיר מחרוזת למספר גם באמצעות פונקציה זו
 
 
                if (x == -1)
                    break;
 
                p = new Node(x);
 
                if (head == null)
                    head = tail = p;
                else
                {
                    tail.SetNext(p);
                    tail = p;
                }
            }
            return head;
        }
 
        // פונקציה להמרת רשימה מקושרת רגילה לרשימה מקושרת מעגלית
        public static Node ConvertToCircularLinkedList(Node head)
        {
            if (head == null) return null; //אם הרשימה מכילה 0 איברים
            if (head.GetNext() == null)    //אם הרשימה מכילה 1 איברים
            {
                head.SetNext(head);
                return head;
            }
 
 
            Node p;
            for (p = head; p.GetNext() != null; p = p.GetNext()) ; // עד שמגיע לאיבר האחרון ברשימה p מזיז את
            p.SetNext(head);
            return head;
        }
 
        // להציג רשימה מקושרת רגילה
        public static void ShowList(Node head)
        {
            Node p = head;
            while (p != null)
            {
                Console.WriteLine(p.GetInfo());
                p = p.GetNext();
            }
        }
 
        // להציג רשימה מקושרת מעגלית
        public static void ShowCircularLinkedList(Node head)
        {
            Node p = head;
            p = head;
            do
            {
                Console.WriteLine(p.GetInfo());
                p = p.GetNext();
            } while (p != head);
        }
        
        static void Main(string[] args)
        {
            Node head = CreateList();
            ShowList(head);
            head = ConvertToCircularLinkedList(head);
            ShowCircularLinkedList(head);
        }

אגב, נוכל להשתמש בספרייה using System.Collections.Generic שבה כבר כתובות שלל פונקציות של רשימות מקושרות.
(אך לא קיימת בה תכונה של "רשימה מקושרת מעגלית")

שימוש בסיסי:

        static void Main(string[] args)
        {
            // יצירה של רשימה חדשה של מחרוזות
            LinkedList<string> linked = new LinkedList<string>();
 
            // להוספת צומת (איבר) לסוף הרשימה AddLast שימוש בפונקציה 
            linked.AddLast("cat");
            linked.AddLast("dog");
            linked.AddLast("man");
 
            // להוספת צומת (איבר) לתחילת הרשימה AddFirst שימוש בפונקציה
            linked.AddFirst("first");
 
            // הדפסה של כל הרשימה
            foreach (var item in linked)
            {
                Console.WriteLine(item);
            }
 
 
            // אפשר לכתוב את ההדפסה גם בהתאם לסוג הרשימה
            foreach (String item in linked)
            {
                Console.WriteLine(item);
            }
        }

(הטייפ "var" הוא טייפ שהקומפיילר מחליף אוטומטית עם מה שהכי הגיוני שיהיה שם.
במקרה שלנו הוא החליף אותו ב: String )




שימושים נוספים:

        static void Main(string[] args)
        {
            LinkedList<string> linked = new LinkedList<string>();
 
            linked.AddLast("one");
            linked.AddLast("two");
            linked.AddLast("three");
            //
            // בתוכנית אנחנו נכניס איבר חדש בין האיבר הראשון לשני
            //
 
            // LinkedListNode כדי להצביע לאיבר מסויים ברשימה משתמשים ב
            LinkedListNode<string> node = linked.Find("one");
 
            // "one" מכיל את כתובת האיבר ברשימה שבו המחרוזת היא LinkedListNode כעת האובייקט 
 
 
            // node ומוסיף אותו אחרי האיבר שמצביע עליו ,"inserted" יוצר איבר חדש שמכיל
            linked.AddAfter(node, "inserted");
 
 
            foreach (var value in linked)
            {
                Console.WriteLine(value);
            }
        }

השוואה בין היכולות של list לשל LinkedList:
(רואים שההבדל קטן מאוד. לא מצופה מכם כרגע להבין את הקוד...)

    class Program
    {
        const int _max = 100000;
        static void Main(string[] args)
        {
            List<string> list = new List<string>();
            LinkedList<string> link = new LinkedList<string>();
            
            for (int i = 0; i < 1000; i++)
            {
                list.Add("OK");
                link.AddLast("OK");
            }
 
            var s1 = Stopwatch.StartNew();
            for (int i = 0; i < _max; i++)
            {
                foreach (string v in list)
                {
                    if (v.Length != 2)
                    {
                        throw new Exception();
                    }
                }
            }
            s1.Stop();
            var s2 = Stopwatch.StartNew();
            for (int i = 0; i < _max; i++)
            {
                foreach (string v in link)
                {
                    if (v.Length != 2)
                    {
                        throw new Exception();
                    }
                }
            }
            s2.Stop();
            Console.WriteLine(((double)(s1.Elapsed.TotalMilliseconds * 1000000) /
                _max).ToString("0.00 ns"));
            Console.WriteLine(((double)(s2.Elapsed.TotalMilliseconds * 1000000) /
                _max).ToString("0.00 ns"));
            Console.Read();
        }
    }

מקור LinkedList:
https://www.dotnetperls.com/linkedlist

כל היכולות של LinkedList:
https://msdn.microsoft.com/en-us/library/he2s3bh7(v=vs.110).aspx


בהצלחה!