[CPCS 204] الدرس الرابع: Introduction to Linked Lists

[deathpain]

-----------------------------------------------

بسم الله الرحمن الرحيم
السلام عليكم ورحمة الله وبركاته

" إذا لم تحاول أن تفعل شيء أبعد مما قد أتقنته.. فإنك لا تتقدم أبداً " .. رونالد اسبورت

-----------------------------------------------

موضوعنا اليوم يتحدث عن نوع جديد وموضوع شيق وبسيط ويعتبر هو بوابة الانتقال للاحتراف في التعامل مع البيانات أثناء البرمجة بإذن الله ..

ما هي الـ Linked List ؟
هي سلسلة من الـNodes بحيث تكون كل Node متصلة بالـ Node الأخرى التابعة لها.

ماهي الـ Nodes ؟
معنى الـNode عامةً هو نقطة تقاطع أو التقاء طرفين، وهنا نعني بها الأماكن التي نخزن بداخلها القيم التي نحتاجها.

لماذا نستخدم الـLinked List ؟
* لأنها ديناميكية، أي أن حجمها قابل للتمدد أو التقلص ( عكس الاراي فحجمه ثابت )
* الـNodes أو العناصر بداخلها لا تتبع بعضها بعضاً في الذاكرة ( عكس الاراي فبياناته تأتي مرتبة في Indexes متسلسلة.
* إضافة العناصر لها أو حذفها منها سريع وسهل جداً !

هل هناك سلبيات للـLinked List ؟
الجواب: نعم، هنالك سلبية وهي أنه عند البحث عن Node محدد فإننا يجب أن نقوم بعمليات كثيرة حتى نصل إليه لأنها لا تحمل Index محدد كما هو الحال في الاراي.

آنواع الـLinked List:
1- Singly Linked List

2- Doubly Linked List

3- Circular Linked List

4- Multiply Linked List
5- Empty Linked List
6- Linked List with Sentinel Nodes

راح نتطرق في هذه المادة لأول 3 انواع فقط، وفي هذا الدرس لأول نوع فقط.

محتويات الـSingle Linked List:
* الـHead ( وهو مؤشر يشير إلى أول عنصر Node في اللست )
* الـNode وينقسم إلى قسمين:
- البيانات Data وتحتوي على أي نوع من البيانات كان.
- المؤشر Next ويشير إلى العنصر الذي يلي العنصر الحالي.



إذا كيف نمثل هذه المحتويات التي لدينا على شكل كود ؟
لدينا كلاسين الأول خاص بإنشاء القائمة List والثاني خاص بإنشاء العناصر Nodes.

أولاً كلاس العناصر Node Class :

كود PHP:

public class Node {

public int data; // لا يهم النوع هنا استخدمت انتجر للتوضيح فقط.
public Node next; // جميع المؤشرات هي من نوع Node لأننا نشير للعنصر بنفس نوعه.

public Node(int i){
this(i,null);
}

public Node(int i, Node n){
data = i;
next = n;
}

} 


كلاس القائمة List:

كود PHP:

public class SLinkedList{
private Node Head;

public SLinkedList(){
Head = null;
}

public boolean isEmpty(){
return Head == null;
}

// باقي الميثودز نكتبها هنا في هذا الكلاس، مثل طباعة اللنكد لست وحذف واضافة العناصر.
} 


كيف ننشئ عناصر Nodes ؟ ببساطة نقوم بإنشاء أوبجكت من كلاس Node.
لنفرض أن لدينا 3 عناصر A و B و C:

كود PHP:

Node A = new Node(1);
Node B = new Node(2);
Node C = new Node(3); 


كيف نربط هذه العناصر الثلاثة بعضها ببعض حتى تصبح لدينا سلسلة من العناصر وهو الهدف من اللنكد لست ؟

نقوم بتغيير الnext لكل عنصر وندعه يؤشر على العنصر الذي يليه:

كود PHP:

A.next = B;
B.next = C; 


لنقم بطباعة العناصر الآن لنشاهد القيم:
* عند طباعة A.next سيطبع قيمة B وهي 2
* عند طباعة B.next سيطبع قيمة C وهي 3
* عند طباعة C.next سيظهر لدينا Exception لأن المؤشر يشير إلى null حيث أنه آخر عنصر في اللست.

الآن نحن نعلم كيف ننشئ قائمة ولكننا لا نعلم كيفية الوصول إلى العناصر بداخلها لنقوم بطباعتها كاملة مثلاً أو التعديل عليها، لذا سنقوم بإنشاء مؤشر جديد ولنعطه أي اسم مثلا temp او ptr:
وظيفة هذا المؤشر هي الانتقال من Node إلى Node دون حصول خسارة للبيانات لأننا لو استخدمنا الـhead فإننا سنفقد العنصر مباشرة عندما يؤشر الـHead على العنصر الذي يليه.

كود PHP:

Node ptr = null; 


في هذه الحالة ما زال المؤشر لا يمكنه تعديل أو طباعة العناصر إذا كيف نستطيع الوصول إلى العناصر ؟
الجواب: ببساطة نقوم بجعل المؤشر يشير إلى نفس الموقع الذي يشير عليه الـHead وبهذا يمكننا الوصول للعنصر الأول ومن ثم كافة العناصر.

كود PHP:

Node ptr = Head; 


الآن كيف نستطيع الوصول للباقي العناصر ؟
ببساطة نقوم بعمل لوب ونجعل المؤشر ptr يشير إلى الـnext للعنصر الحالي في كل مرة، إذا:

كود PHP:

while (ptr.next !=null {
ptr = ptr.next;
} 


ونفس الطريقة مع العنصر الذي يليه:


لماذا استخدمنا ptr.next != null بدلا من ptr != null ؟
لأن اللوب عندما تصل لآخر عنصر في اللست فإن الـnext له يشير إلى null وعندها سيخرج من اللوب وبهذا لن يحدث Exception ولكن لو لم نستخدم النكست فعندها سيصل اللوب إلى الnull وعندها سيخرج وإذا كنا نقوم بالطباعة فإننا سنقوم باحداث خطأ هنا.

الآن للميثود الخاصة بطباعة اللست، بمجرد قراءتها ستتمكن من فهمها:

كود PHP:

public void printList(){
Node ptr = Head;

while (ptr.next != null){
System.out.println(ptr.data + "" );
ptr = ptr.next;
}

} 


هذا هو مفهوم اللنكد لست ببساطة وبتلخيص شديد.
أعتذر عن التأخر في تنزيل الدروس بسبب ضغط الدراسة والاختبارات ولكن اعدكم بالمزيد في إجازة الحج.

*ملاحظة: قمت بإضافة كافة الأكواد الخاصة باللنكد لست مع الميثودز للحذف والإضافة الخاصة بالنوعين السنقلي والدبلي في المرفقات.

بالتوفيق للجميع