القوائم المرتبطة LinkedList

القوائم المرتبطة LinkedList

ما هي القوائم المرتبطة linkedList..؟! وما فوائد استخدام القوائم المرتبطة LinkedList في البرمجة ..؟! وما هي أنواع القوائم المرتبطة LinkedList ..؟!وماهي والعمليات الأساسية على LinkedList..؟! وكيف يتم تنفيذ LinkedList بواسطة تعليمات C# ..؟!!

تستخدم القوائم المرتبطة LinkedList في العديد من التطبيقات، مثل تنفيذ قوائم التشغيل وقوائم الترجمة وقوائم العمليات في نظام التشغيل. وهي تستخدم أيضًا في تنفيذ بعض الخوارزميات المهمة في العديد من المجالات. في هذا المقال سنتعرف على القوائم المرتبطة LinkedList لنبدأ…

في هذا المقال سنتعرف على :

• ما هي القوائم المرتبطة linkedList ؟
• القوائم المرتبطة LinkedLists والمصفوفات Arrays.
• فوائد استخدام القوائم المرتبطة LinkedList.
• أنواع القوائم المرتبطة LinkedList.
• تنفيذ القوائم المرتبطة LinkedList.
• تنفيذ LinkedList بلغة C# والعمليات الأساسية.
• LinkedList Class in C# .
• خلاصة مقال القوائم المرتبطة LinkedList.

ما هي القوائم المرتبطة LinkedList؟

القائمة المرتبطة LinkedList هي ثاني أكثر هياكل بيانات Data Structure استخدامًا بعد المصفوفات Array. و تُعَرف القائمة المرتبطة LinkedList على أنها نوع من أنواع الـ Data Structure التي تتكون من مجموعة من العناصر المتسلسلة والمرتبطة مع بعضها البعض بروابط.

وتُعُرف عناصر القوائم المرتبطة LinkedLists بالعُقد Nodes حيث تتكون كل عقدة node (عنصر) منها من حقلين حقل البيانات Data الذي هو قيمة للعنصر وحقل المؤشر Pointer . ويُعرف حقل المؤشر بـ Next أو Link ويشير للعنصر التالي LinkedList ويمكن تصور القائمة المرتبطة كسلسلة من العقد ، حيث تشير كل عقدة إلى العقدة التالية. ويوضح الشكل التالي القائمة المرتبطة LinkedList :

وتسمى العقدة الأولى في القائمة المرتبطة LinkedList بـ رأس القائمة header . وإذا كانت القائمة LinkedList فارغة ، فإن قيمة header تشير إلى NULL .

القوائم المرتبطة LinkedLists و المصفوفات Array

المصفوفات Arrays هي قوائم مرتبة ومفهرسة لكن العمليات على المصفوفات Arrays بطيئة جدًا للاستخدام العملي لهذا يمكن استخدام القائمة المرتبطة LinkedList كبديل. حيث يمكن استخدام القائمة المرتبطة في كل حالات المصفوفات تقريبًا، إلا إذا كنا بحاجة إلى وصول عشوائي إلى العناصر الموجودة في القائمة، عندها تكون المصفوفة هي الخيار الأفضل على الأرجح.

الاختلاف الرئيسي بين المصفوفة والقائمة المرتبطة في أنه في الـ Array تتم الإشارة إلى العناصر حسب الفهرسة (Indexing) ، وبينما تتم الإشارة إلى عناصر LinkedList من خلال علاقتها بالعناصر الأخرى.

فوائد استخدام القوائم المرتبطة LinkedList

يوجد العديد من الفوائد الرئيسية لاستخدام LinkedList في البرمجة، ومن أهمها:

• إمكانية إضافة وحذف العناصر بكفاءة: يمكن لـ LinkedList إضافة وحذف العناصر بكفاءة عندما يتم تنفيذ العمليات على الأعلى والأسفل من القائمة، حيث يتم تحديث المؤشرات فقط دون الحاجة إلى نسخ كامل للقائمة. ويعني ذلك أن LinkedList يستخدم الذاكرة بكفاءة أكبر من الهياكل الأخرى مثل المصفوفات.
• تنفيذ العمليات بسرعة: يتم تنفيذ العمليات على LinkedList بسرعة، حيث يتم الوصول إلى العناصر بسهولة باستخدام الحلقات والمؤشرات. ويسمح ذلك بتنفيذ العديد من العمليات بكفاءة أكبر مثل البحث والفرز والإدخال والحذف.
• توفير الوقت والجهد في البرمجة: يمكن لـ LinkedList توفير الوقت والجهد في البرمجة، حيث يتم توفير العديد من الوظائف المساعدة مثل البحث والفرز والإدخال والحذف من خلال المكتبات القياسية المتاحة في معظم لغات البرمجة.
• إمكانية توسيع الحجم بسهولة: يمكن لـ LinkedList أن تكون غير محدودة في الحجم، حيث يمكن إضافة عناصر جديدة بسهولة دون الحاجة إلى توسيع الذاكرة بشكل مسبق. وهذا يجعل LinkedList مناسبًا للاستخدام في الحالات التي تتطلب تخزين عدد كبير من العناصر.
• إمكانية تنفيذ الخوارزميات المعقدة: يمكن تنفيذ العديد من الخوارزميات المعقدة باستخدام LinkedList، مثل البحث الثنائي والجزئي والفرز السريع والدمج، ويمكن تحسين أداء هذه الخوارزميات باستخدام LinkedList.

وبشكل عام، توفر LinkedList العديد من المزايا في البرمجة، وتعد خيارًا جيدًا لتخزين البيانات وتنفيذ العمليات الأساسية عليها.

أنواع القوائم المرتبطة LinkedList

تعدد أنواع للقوائم المترابطة LinkedList وأهم أنواعها ثلاثة وهي :

• القائمة المرتبطة البسيطة أو المفردة Singly LinkedList.
• القائمة المرتبطة المزدوجة Doubly LinkedList.
• القائمة المرتبطة الدائرية Circular LinkedList.

القائمة المرتبطة البسيطة أو المفردة Singly LinkedList:

في هذا النوع من LinkedList ، يمكن التنقل بين عناصر LinkedList أو اجتيازها في اتجاه واحد فقط. حيث يشير المؤشر لكل عقدة إلى العقد التالية فقط المؤشر للعقدة الأخيرة يشير إلى NULL . ولهذا تسمى " القائمة المرتبطة المنفردة Singly LinkedList ".وهذا النوع ما سنقوم بمناقشة العمليات الأساسية عليها فيما يلي . و ويوضح الشكل التالي شكل القائمة المرتبطة المنفردة :

القائمة المرتبطة المزدوجة Doubly LinkedList:

في هذا النوع من LinkedList ، يمكن التنقل بين عناصر LinkedList أو اجتيازها في كلا الاتجاهين (إلى الأمام والخلف) . فالعقدة هنا تحتوي على مؤشرين ، أحدهما يشير إلى العقدة السابقة والآخر يشير إلى العقدة التالية. وتتضح من خلال الشكل التالي:

القائمة المرتبطة الدائرية Circular LinkedList:

قد يصنف هذا النوع كنوع منفصل من أنواع الـ Data Structure و باسم Circular Lists لأن في هذا النوع من تشير العقدة الأخيرة من القائمة إلى العقدة الأولى ( header) وبهذا تعطي شكل الدائرة وليس القائمة.ولكن يبقى تركيب العنصر في القائمة المرتبطة LinkedList نفسه في Circular Lists , كما يتضح في الشكل التالي:

تنفيذ القوائم المرتبطة LinkedList

يمكن تنفيذ LinkedList باستخدام العديد من لغات البرمجة المختلفة، وتتوفر LinkedList بشكل عام في جميع لغات البرمجة الرئيسية. وتتوفر أيضًا العديد من المكتبات القياسية التي تسهل استخدام LinkedList في البرمجة.يمكن استخدام LinkedList في معظم لغات البرمجة الشائعة، مثل:

• لغات البرمجة المنصَّبة على الحاسوب مثل C، C++ ، و Java.
• لغات البرمجة الديناميكية مثل Python و Ruby.
• لغات البرمجة الوظيفية مثل Lisp و Scheme.
• لغات البرمجة النصية مثل JavaScript.

يمكن تنفيذ LinkedList باستخدام هذه اللغات، وتتوفر أيضًا العديد من المكتبات والإطارات التي تسهل استخدام LinkedList في البرمجة، مثل Standard Template Library (STL) في C++ و java.util.LinkedList في Java و linkedlist في Python.

تنفيذ LinkedList بلغة C# والعمليات الأساسية

توفر C# كلاً من LinkedList Class و LinkedListNode Class للتنفيذ linkedList كما يمكن بناء LinkedList بواسطة تعليمات C# سنرى كيف يتم بناء الـ Classes الخاصة بـ LinkedList من الصفر. ولكي يتم تنفيذ LinkedList في C# نحتاج الى :

• بناء Class خاص للعقد Node حيث يتم عمل Object منه لكل عقدة في Linkedlist.
• بناء Class خاص بالخصائص والعمليات التي تتم على LinkedList.

وهذا مثال على طريقة بناء الـ Node Class :

class The_Node {
	public object data;
	public The_Node link;
	public The_Node() {
		data = null;
		link = null;
	}
	public The_Node (object o){
		data = o;
		link = null;
	}
    public The_Node(object o , The_Node n){
        data = o;
        link = n; 
    }
    // Node Methods 
    public The_Node getNextNode (){
        return link; 
    }
    public object getData (){
         return data;
    }
    public void SetNextNode ( The_Node n ){
         link = n;  
    }
    public void SetData (object d)
    { 
        data = d;
    }
}

العمليات الأساسية على LinkedList

ذكرنا أنه عند تنفيذ LinkedList في C# علينا بناء Class خاص بالعمليات التي تتم على LinkedList. بما أن يحتوي الـ LinkedList Class على العمليات الأساسية على LinkedList سوف نرى فيما يلي تنفيذ العمليات ويمكن الكود لكامل الـ class على الرابط هنا .

العمليات الأساسية على LinkedList هي:

• الإدراج Inserting. .
• الحذف Remov.
• عملية البحث Search.
• عملية الطباعة Print.

الإدراج Inserting

عملية الإدراج Insert هي أن نقوم باضافة عقدة جديد القائمة Linkedlist وتتم بإنشاء عقدة جديد ومن ثم تغير المؤشرات في LinkedList لتشير إلى العقدة الجديدة وهو مايحدد ترتيب العقدة في القائمة ويوضح الشكل التالي عملية الإدراج :

وهنا مثال: على الكود الخاص بدالة الإدراج Insert :

//To insert a new node after an existing node, we have to first find the “after” node.
    public The_Node Find(Object item){
        The_Node current = new The_Node();
        current = header;
        while(current.data != item){
            current = current.link;
        }
        return current; 
    }
 public void Insert ( object newItem , object after){
        The_Node current = new The_Node();
        The_Node newNode = new The_Node(newItem);
        current = Find(after);
        newNode.link = current.link;
        current.link = newNode;        
    }

الحذف Remove

وهي ان نقوم بحذف عقدة من LinkedList ويكون هذا بتغيير المؤشر ليتجاهل القعدة المراد حذفها . كما يوضح الشكل التالي:

وهنا مثال على الكود الخاص بدالة الحذف Remove:

// for removing node we need to find the node before the node we want to remove
    private The_Node FindPrevious(object o){
        The_Node current = header;
        while(!(current.link == null) && (current.link.data != o))
            current = current.link;
        return current;
    }
    public void Remove (object o ){
        The_Node p = FindPrevious(o);
        if (!(p.link == null))
            p.link = p.link.link;
    }

عملية البحث Search

وتستخدم للبحث عن قيمة معينة في القائمة المرتبطة linkedList وهنا مثال عن كيفية القيام بعملية البحث :

public The_Node Find(Object item){
        The_Node current = new The_Node();
        current = header;
        while(current.data != item){
            current = current.link;
        }
        return current; 
    }

عملية الطباعة Print

وهي عملية طباعة عناصر LinkedList وتتم بواسطة الكود التالي:

//Display the LinkedList 
public void PrintList (){
        The_Node current = new The_Node();
        current = header;
        while(!(current.link == null))
        {
            Console.WriteLine(current.link.data);
            current = current.link;
        }
    }

LinkedList Class in C#

في C# عندما نريد العمل مع Linkedlist من خلال collection Namespace نرى أن LinkedList Class يوفر انا جملة من الـ Properties والـ Methods التي تسهل علينا العمل مع Linked List فيما يلي شرح موجز لأهم الخصائص Properties و الدوال Methods المتوفرة في Linkedlist Class لنرى معاً:

• الخصائص Properties في LinkedList Class.
• دوال إدراج العناصر في Linkedlist Class.
• دوال الحذف في LinkedList Class.
• دوال البحث في LinkedList Class.
• دوال حسابيةMath Methods في LinkedList Class.
• الدالة Clear() .

الخصائص Properties في LinkedList Class

يوضح الشكل التالي أهم الخصائص Properties للـ LinkedList Class في C#

First	وترجع قيمة العقدة الأولى في القائمة LinkedList.
Last	وترجع قيمة العقدة الأخير في القائمة LinkedList.
Count	تقوم هذه الخاصية بارجع عدد عناصر الـقائمة LinkedList ( عدد العقد).

دوال إدراج العناصر في LinkedList Class

يوضح الشكل التالي أهم الدوال التي يوفرها LinkedList Class لإضافة العناصر إلى LinkedList

وهنـا مثـال :

using System.Collections.ObjectModel;
using System;
    class Program
    {
        public static void Main(string[] args)
        {
            LinkedList<int> list = new LinkedList<int>();
            LinkedListNode<int> node0 = new LinkedListNode<int>(4);
            LinkedListNode<int> node1 = new LinkedListNode<int>(5);
            list.AddFirst(1);   // 1
            list.AddFirst(node0);    // 4 1
            list.AddLast(2);    // 4 1 2
            list.AddBefore(node0, 3); // 3 4 1 2 
            list.AddAfter(node0, node1); // 3 4 5 1 2
            //print the LinkedList
            foreach (int i in list)
            {
                Console.Write(i +" ");
            }       
        }

    }

لتكـن النتيجـة

---

3 4 5 1 2

---

دوال الحذف في LinkedList Class

يوضح الشكل التالي أهم دوال حذف العناصر من LinkedList المتوفره في LinkedList Class

وهنـا مثـال :

...........
//Romve methods the list is : 3 4 5 1 2 
           list.RemoveFirst();  //4 5 1 2 
           list.Remove(1); // 4 5 2 
           list.RemoveLast(); // 4 5 
...........

دوال البحث في LinkedList Class

يوضح الشكل التالي أهم دوال البحث التي يوفرها LinkedList Class في C#

وهنـا مثـال :

...........
        Console.WriteLine(list.Find(1).Value);
            Console.WriteLine(list.FindLast(1).Value);
            Console.WriteLine(list.Contains(1)) ;
...........

دوال حسابية Math Methods في LinkedList Class

يوضح الشكل التالي أهم الدوال الحسابية المتوفره في LinkedList Class

وهنـا مثـال :

...........
        Console.WriteLine(list.Sum());
            Console.WriteLine(list.Average());
            Console.WriteLine(list.Max());
            Console.WriteLine(list.Min());;
...........

الدالة Clear()

ولحذف LinkedList بأكلملها يوفر LinkedList Class الدالة Clear() :

...........
list.Clear();
...........

خلاصة مقال LinkedList

يقدم هذا الفيديو ملخصًا لمقال LinkedList ويعرض مفهوم القائمة المرتبطة LinkedList وأنواعها والعمليات الأساسية التي يمكن تنفيذها عليها

إلى هنا ينتهي هذا المقال الذي تكلم عن القوائم المرتبطة LinkedLists تعرفنا فيه على مفهوم القوائم المرتبطة LinkedList وفوائد استخدام القوائم المرتبطة LinkedList في البرمجة. وشرحنا أنواع القوائم المرتبطة LinkedList وأهم العمليات عليها وطريقة تنفيذها من خلال تعليمات لغة C# .