شرح هيكل بيانات القوائم المتصلة

القائمة المتصلة (Linked List) هي هيكل بيانات خطي يتم فيه تخزين العناصر كعقد. تحتوي كل عقدة على بيانات ومرجع لعقدة أخرى. على عكس المصفوفات، لا تتطلب القوائم المتصلة تخزين العناصر بجانب بعضها البعض في الذاكرة.

تعد القوائم المتصلة مهمة في هياكل البيانات والخوارزميات لأنها توضح كيفية عمل هياكل البيانات الديناميكية. وهي مفيدة لفهم مراجع الذاكرة، وعمليات الإدراج والحذف والتنقل، وكيفية بناء هياكل أكثر تقدمًا مثل المكدسات (stacks) وقوائم الانتظار (queues) وجداول التجزئة (hash tables) والرسوم البيانية (graphs) وقوائم التجاور (adjacency lists).

مقدمة

في البرمجة، غالبًا ما تُخزّن البيانات في مجموعات. تُعد المصفوفات (Arrays) من أكثر المجموعات شيوعًا لأنها بسيطة وتتيح الوصول السريع بواسطة الفهرس. ومع ذلك، للمصفوفات قيود عندما تكون هناك حاجة إلى عمليات إدراج وحذف متكررة، خاصة في منتصف المجموعة أو بدايتها.

تحل القائمة المتصلة نوعًا مختلفًا من المشكلات. فبدلاً من وضع جميع العناصر في مواقع ذاكرة متجاورة، تخزن كل عنصر داخل عقدة. وتعرف كل عقدة مكان العقدة التالية.

هذا يجعل القوائم المتصلة مرنة. يمكن إنشاء العقد وربطها ديناميكيًا أثناء تشغيل البرنامج. يساعد فهم القوائم المتصلة المطورين على فهم المراجع (references) والمؤشرات (pointers) وتخصيص الذاكرة (memory allocation) والتصميم الداخلي للعديد من هياكل البيانات.

ما هي القائمة المتصلة؟

القائمة المتصلة هي سلسلة من العقد المتصلة ببعضها البعض باستخدام المراجع. تحتوي كل عقدة عادةً على جزأين:

• البيانات (Data): القيمة الفعلية المخزنة في العقدة.

• المرجع التالي (Next reference): مرجع أو مؤشر إلى العقدة التالية في القائمة.

يمكن تمثيل قائمة متصلة بسيطة على هذا النحو:

[10 | next] → [20 | next] → [30 | null]

تحتوي العقدة الأولى على القيمة 10 وتشير إلى العقدة الثانية. تحتوي العقدة الثانية على القيمة 20 وتشير إلى العقدة الثالثة. تحتوي العقدة الثالثة على القيمة 30 وتشير إلى قيمة فارغة (null)، مما يعني أن القائمة تنتهي هنا.

تُسمى العقدة الأولى عادةً رأس القائمة المتصلة (head).

مصطلحات القوائم المتصلة

قبل دراسة عمليات القوائم المتصلة، من المهم فهم المصطلحات الشائعة.

• العقدة (Node): عنصر واحد في القائمة المتصلة.

• الرأس (Head): العقدة الأولى في القائمة المتصلة.

• الذيل (Tail): العقدة الأخيرة في القائمة المتصلة.

• التالي (Next): مرجع من عقدة إلى العقدة التالية.

• السابق (Previous): مرجع إلى العقدة السابقة، ويُستخدم في القوائم المتصلة المزدوجة.

• فارغ (Null): قيمة تشير إلى عدم وجود عقدة تالية.

تظهر هذه المصطلحات في كل تطبيق للقوائم المتصلة تقريبًا.

لماذا تعد القوائم المتصلة مهمة في هياكل البيانات والخوارزميات (DSA)

القوائم المتصلة مهمة لأنها تقدم فكرة ربط البيانات باستخدام المراجع بدلاً من الاعتماد على الفهارس. وهذا يمثل خطوة كبيرة في تعلم هياكل البيانات والخوارزميات.

تساعد القوائم المتصلة المطورين على فهم ما يلي:

• تخصيص الذاكرة الديناميكي.

• المراجع والمؤشرات.

• هياكل البيانات القائمة على العقد.

• الإدراج والحذف الفعالين.

• منطق التنقل.

• كيف يمكن تنفيذ المكدسات وقوائم الانتظار.

• كيف تعمل قوائم التجاور في الرسوم البيانية.

حتى لو لم يقم المطورون بتنفيذ القوائم المتصلة يدويًا كل يوم، فإن المفاهيم الكامنة وراءها تظهر في العديد من الأنظمة الحقيقية.

القوائم المتصلة مقابل المصفوفات

تُعد المصفوفات والقوائم المتصلة كلاهما هياكل بيانات خطية، لكنهما تخزنان وتديران البيانات بطرق مختلفة.

تُخزّن المصفوفة العناصر في مواقع ذاكرة متجاورة. وهذا يعني أن العناصر توضع بجانب بعضها البعض في الذاكرة، ويمكن الوصول إلى كل عنصر بسرعة باستخدام الفهرس.

Array:
Index:  0   1   2
Value: 10  20  30

تُخزّن القائمة المتصلة العناصر كعقد منفصلة. وتشير كل عقدة إلى العقدة التالية.

Linked List:
[10] → [20] → [30] → null

تشمل الاختلافات الرئيسية ما يلي:

• توفر المصفوفات وصولاً عشوائيًا سريعًا باستخدام الفهارس.

• تتطلب القوائم المتصلة اجتيازًا للوصول إلى موقع معين.

• قد تتطلب المصفوفات إزاحة العناصر أثناء الإدراج أو الحذف.

• يمكن للقوائم المتصلة إدراج أو حذف العقد بكفاءة عندما يكون الموضع معروفًا.

• تستخدم المصفوفات ذاكرة متجاورة.

• تستخدم القوائم المتصلة عقدًا يمكن تخزينها في مواقع ذاكرة مختلفة.

لا يوجد هيكل أفضل دائمًا. يعتمد الخيار الأفضل على المشكلة.

القوائم المتصلة في هياكل البيانات والخوارزميات (DSA) في الذاكرة

إحدى أهم الأفكار وراء القوائم المتصلة هي كيفية تخزينها في الذاكرة.

في المصفوفة، تُخزّن العناصر بجانب بعضها البعض:

Memory:
Address 1000 → 10
Address 1004 → 20
Address 1008 → 30
Address 1012 → 40

نظرًا لأن العناصر متجاورة، يمكن للبرنامج حساب عنوان أي عنصر باستخدام العنوان الأساسي والفهرس.

في القائمة المتصلة، لا تحتاج العقد إلى التخزين بجانب بعضها البعض:

Memory:
Address 2040 → [10 | next: 9000]
Address 9000 → [20 | next: 3050]
Address 3050 → [30 | next: null]

قد تكون العقد موجودة في أي مكان في الذاكرة. تخزن كل عقدة مرجعًا إلى العقدة التالية، بحيث يمكن تتبع القائمة من عقدة إلى أخرى.

لماذا يهم تمثيل الذاكرة

يهم تمثيل الذاكرة لأنه يوضح نقاط القوة والضعف في القوائم المتصلة.

نظرًا لأن العقد متصلة بواسطة مراجع، فإن إدراج عقدة جديدة لا يتطلب إزاحة جميع العناصر مثل المصفوفة. يغير البرنامج المراجع فقط.

على سبيل المثال، لإدراج 15 بين 10 و 20:

Before:
[10] → [20] → [30]

After:
[10] → [15] → [20] → [30]

يمكن إنشاء العقدة الجديدة في أي مكان في الذاكرة. يتم تغيير المرجع من 10 للإشارة إلى 15، وتشير 15 إلى 20.

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

بنية العقدة

العقدة هي اللبنة الأساسية للقائمة المتصلة. في القائمة المتصلة الفردية، تحتوي العقدة على بيانات ومرجع إلى العقدة التالية.

Node:
+------+------+
| data | next |
+------+------+

على سبيل المثال:

+------+------+
|  10  |  →   |
+------+------+

في الكود، يمكن تمثيل العقدة ككائن (object) أو صنف (class).

مثال العقدة في PHP

<?php

class Node
{
    public mixed $data;
    public ?Node $next = null;

    public function __construct(mixed $data)
    {
        $this->data = $data;
    }
}

يمثل صنف PHP هذا عقدة بسيطة. تخزن الخاصية data القيمة، وتخزن الخاصية next مرجعًا إلى العقدة التالية.

مثال العقدة في JavaScript

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

يتبع إصدار JavaScript نفس الهيكل. تخزن كل عقدة بيانات ومرجعًا إلى العقدة التالية.

أنواع القوائم المتصلة

هناك عدة أنواع من القوائم المتصلة. يغير كل نوع طريقة توصيل العقد والعمليات التي يسهل إجراؤها.

الأنواع الرئيسية هي:

• القائمة المتصلة الفردية (Singly Linked List).

• القائمة المتصلة المزدوجة (Doubly Linked List).

• القائمة المتصلة الدائرية (Circular Linked List).

• القائمة المتصلة المزدوجة الدائرية (Circular Doubly Linked List).

يساعد فهم هذه الأنواع المطورين على اختيار الهيكل الصحيح للمشكلات المختلفة.

القائمة المتصلة الفردية

القائمة المتصلة الفردية هي أبسط أنواع القوائم المتصلة. تحتوي كل عقدة على بيانات ومرجع إلى العقدة التالية.

[10] → [20] → [30] → null

التنقل ممكن في اتجاه واحد فقط: من الرأس إلى الذيل.

تكون القائمة المتصلة الفردية مفيدة عندما:

• يكون التنقل الأمامي كافيًا.

• يجب أن يكون استخدام الذاكرة أقل من القائمة المتصلة المزدوجة.

• تتم عمليات الإدراج والحذف بشكل رئيسي في البداية.

• هناك حاجة إلى بنية بسيطة قائمة على العقد.

القيود هي أن التحرك للخلف غير ممكن لأن العقد لا تخزن مراجعًا للعقد السابقة.

القائمة المتصلة المزدوجة

تخزن القائمة المتصلة المزدوجة مرجعين في كل عقدة: أحدهما إلى العقدة التالية والآخر إلى العقدة السابقة.

null ← [10] ⇄ [20] ⇄ [30] → null

هذا يسمح بالتنقل في كلا الاتجاهين.

تحتوي العقدة في القائمة المتصلة المزدوجة عادةً على:

• البيانات.

• مرجع التالي.

• مرجع السابق.

تكون القوائم المتصلة المزدوجة مفيدة عندما:

• هناك حاجة إلى التنقل الأمامي والخلفي.

• يجب أن يكون حذف عقدة معروفة فعالاً.

• هناك حاجة إلى سلوك يشبه التنقل.

• يتم تنفيذ أنظمة التراجع والإعادة (Undo and redo).

المقايضة هي أن كل عقدة تتطلب ذاكرة إضافية للمرجع السابق.

القائمة المتصلة الدائرية

القائمة المتصلة الدائرية هي قائمة متصلة تشير فيها العقدة الأخيرة إلى العقدة الأولى بدلاً من الإشارة إلى قيمة فارغة (null).

[10] → [20] → [30]
 ↑              ↓
 └──────────────┘

وهذا ينشئ حلقة.

تكون القوائم المتصلة الدائرية مفيدة عندما:

• تحتاج العملية إلى الدوران بشكل متكرر عبر العناصر.

• هناك حاجة إلى جدولة تناوب الأدوار (Round-robin scheduling).

• هناك حاجة إلى قائمة تشغيل دائرية أو نظام قائم على الأدوار.

• يجب أن يتصل النهاية بشكل طبيعي بالبداية.

التحذير المهم هو أن التنقل يجب أن يحتوي على شرط توقف. وإلا، قد يستمر البرنامج في التكرار إلى الأبد.

القائمة المتصلة المزدوجة الدائرية

تجمع القائمة المتصلة المزدوجة الدائرية بين الفكرتين. تحتوي كل عقدة على مراجع للتالي والسابق، وتتصل العقدة الأخيرة مرة أخرى بالعقدة الأولى بينما تتصل العقدة الأولى مرة أخرى بالعقدة الأخيرة.

┌──────────────────────┐
↓                      ↑
[10] ⇄ [20] ⇄ [30]
↑                      ↓
└──────────────────────┘

يدعم هذا النوع التنقل الدائري الأمامي والخلفي.

وهو مفيد في الأنظمة التي تتطلب التنقل المستمر، مثل المخازن المؤقتة الدائرية (circular buffers)، وقوائم التشغيل المتقدمة، وبعض هياكل البيانات منخفضة المستوى.

المقايضة هي تعقيد تنفيذ أعلى وذاكرة إضافية لكل عقدة.

عمليات القائمة المتصلة

تدعم القوائم المتصلة عدة عمليات مهمة. العمليات الأكثر شيوعًا هي:

• التنقل (Traversal).

• الإدراج في البداية.

• الإدراج في النهاية.

• الإدراج في موقع محدد.

• الحذف من البداية.

• الحذف من النهاية.

• الحذف حسب القيمة.

• البحث.

• التحديث.

• العكس (Reverse).

تعتمد كل عملية على تغيير المراجع بشكل صحيح.

عملية التنقل

التنقل يعني زيارة كل عقدة في القائمة المتصلة من الرأس إلى النهاية.

على سبيل المثال:

[10] → [20] → [30] → null

ترتيب التنقل هو:

10
20
30

يبدأ التنقل من العقدة الرأس ويتبع المراجع التالية حتى يتم الوصول إلى قيمة فارغة (null).

التعليمات البرمجية الزائفة للتنقل

current = head

while current is not null:
    print current.data
    current = current.next

يتحرك المؤشر الحالي عقدة واحدة في كل مرة.

الإدراج في البداية

الإدراج في البداية يعني إضافة عقدة جديدة قبل الرأس الحالي.

لنفترض أن القائمة هي:

[20] → [30] → null

نريد إدراج 10 في البداية.

الخطوات هي:

1. إنشاء عقدة جديدة بقيمة 10.

2. جعل العقدة الجديدة تشير إلى الرأس الحالي.

3. تحديث الرأس ليشير إلى العقدة الجديدة.

النتيجة هي:

[10] → [20] → [30] → null

تعتبر هذه العملية فعالة لأنها لا تتطلب اجتياز القائمة.

الإدراج في النهاية

الإدراج في النهاية يعني إضافة عقدة جديدة بعد العقدة الأخيرة.

لنفترض أن القائمة هي:

[10] → [20] → null

نريد إدراج 30 في النهاية.

الخطوات هي:

1. إنشاء عقدة جديدة بقيمة 30.

2. البدء من الرأس.

3. التحرك حتى يتم الوصول إلى العقدة الأخيرة.

4. جعل العقدة الأخيرة تشير إلى العقدة الجديدة.

النتيجة هي:

[10] → [20] → [30] → null

إذا كانت القائمة تحتفظ بمرجع للذيل، يمكن أن يكون الإدراج في النهاية بتعقيد O(1). بدون مرجع للذيل، يكون بتعقيد O(n) لأنه يتطلب اجتيازًا.

الإدراج في موقع محدد

الإدراج في موقع محدد يعني إضافة عقدة بين العقد الموجودة.

لنفترض أن القائمة هي:

[10] → [30] → null

نريد إدراج 20 بين 10 و 30.

الخطوات هي:

1. إنشاء عقدة جديدة بقيمة 20.

2. إيجاد العقدة التي يجب إدراج العقدة الجديدة بعدها.

3. جعل العقدة الجديدة تشير إلى العقدة التالية.

4. جعل العقدة السابقة تشير إلى العقدة الجديدة.

النتيجة هي:

[10] → [20] → [30] → null

ترتيب تحديثات المراجع مهم. إذا تم تغيير المراجع بشكل غير صحيح، فقد يفقد جزء من القائمة.

الحذف من البداية

الحذف من البداية يزيل عقدة الرأس.

لنفترض أن القائمة هي:

[10] → [20] → [30] → null

لإزالة 10، نقوم بتحديث الرأس للإشارة إلى العقدة التالية.

head = head.next

النتيجة هي:

[20] → [30] → null

تعتبر هذه العملية بتعقيد O(1) لأنه لا يلزم اجتياز.

الحذف من النهاية

الحذف من النهاية يزيل العقدة الأخيرة.

لنفترض أن القائمة هي:

[10] → [20] → [30] → null

لحذف 30 في قائمة متصلة فردية، نحتاج إلى إيجاد العقدة قبل العقدة الأخيرة.

العقدة قبل 30 هي 20. نقوم بتعيين مرجعها التالي إلى قيمة فارغة (null).

[10] → [20] → null

تعتبر هذه العملية بتعقيد O(n) في قائمة متصلة فردية لأنه يجب علينا اجتياز القائمة لإيجاد العقدة قبل الأخيرة.

الحذف حسب القيمة

الحذف حسب القيمة يعني إزالة أول عقدة تحتوي على قيمة محددة.

لنفترض أن القائمة هي:

[10] → [20] → [30] → null

نريد حذف 20.

تبحث الخوارزمية عن العقدة التي تحتوي على 20 وتتتبع العقدة السابقة. ثم تقوم بتغيير مرجع العقدة السابقة التالي.

Before:
[10] → [20] → [30] → null

After:
[10] → [30] → null

إذا وجدت القيمة في الرأس، يجب تحديث الرأس.

عملية البحث

البحث يعني إيجاد ما إذا كانت قيمة موجودة في القائمة المتصلة.

نظرًا لأن القوائم المتصلة لا تدعم الوصول المباشر بالفهرس مثل المصفوفات، فإن البحث يتطلب اجتيازًا.

[10] → [20] → [30] → null

للبحث عن 30، تتحقق الخوارزمية مما يلي:

10 → not found
20 → not found
30 → found

التعقيد الزمني للبحث هو O(n) لأنه في أسوأ الحالات قد تحتاج الخوارزمية إلى فحص كل عقدة.

عملية التحديث

التحديث يعني تغيير قيمة عقدة.

على سبيل المثال:

[10] → [20] → [30] → null

إذا أردنا تحديث 20 إلى 25، فإننا نبحث أولاً عن 20، ثم نغير بياناتها.

[10] → [25] → [30] → null

يستغرق جزء البحث O(n)، بينما يكون التحديث الفعلي O(1) بمجرد العثور على العقدة.

عملية العكس

عكس القائمة المتصلة يعني تغيير اتجاه جميع مراجع التالي.

قبل العكس:

[10] → [20] → [30] → null

بعد العكس:

[30] → [20] → [10] → null

هذه مشكلة شائعة في المقابلات والخوارزميات لأنها تختبر فهم المراجع.

يستخدم الحل التكراري النموذجي ثلاثة مؤشرات:

• السابق (previous): العقدة السابقة.

• الحالي (current): العقدة الحالية.

• التالي (next): العقدة التالية المحفوظة قبل تغيير الرابط.

تشغيل يدوي لعمليات القائمة المتصلة

دعنا نقم بتشغيل هذا التسلسل يدويًا:

insertFirst(20)
insertFirst(10)
insertLast(30)
search(20)
delete(20)
insertLast(40)

ابدأ بقائمة فارغة:

head = null

بعد insertFirst(20):

[20] → null

بعد insertFirst(10):

[10] → [20] → null

بعد insertLast(30):

[10] → [20] → [30] → null

الآن ابحث عن 20:

Check 10 → not found
Check 20 → found

الآن احذف 20:

[10] → [30] → null

الآن أدرج 40 في النهاية:

[10] → [30] → [40] → null

يوضح هذا التشغيل اليدوي كيف تعتمد عمليات القائمة المتصلة على تغيير مراجع العقد.

تنفيذ القائمة المتصلة الفردية في PHP

فيما يلي تنفيذ PHP نظيف لقائمة متصلة فردية مع عمليات شائعة.

<?php

class ListNode
{
    public mixed $data;
    public ?ListNode $next = null;

    public function __construct(mixed $data)
    {
        $this->data = $data;
    }
}

class LinkedList
{
    private ?ListNode $head = null;

    public function insertFirst(mixed $data): void
    {
        $newNode = new ListNode($data);
        $newNode->next = $this->head;
        $this->head = $newNode;
    }

    public function insertLast(mixed $data): void
    {
        $newNode = new ListNode($data);

        if ($this->head === null) {
            $this->head = $newNode;
            return;
        }

        $current = $this->head;

        while ($current->next !== null) {
            $current = $current->next;
        }

        $current->next = $newNode;
    }

    public function search(mixed $target): bool
    {
        $current = $this->head;

        while ($current !== null) {
            if ($current->data === $target) {
                return true;
            }

            $current = $current->next;
        }

        return false;
    }

    public function delete(mixed $target): bool
    {
        if ($this->head === null) {
            return false;
        }

        if ($this->head->data === $target) {
            $this->head = $this->head->next;
            return true;
        }

        $current = $this->head;

        while ($current->next !== null) {
            if ($current->next->data === $target) {
                $current->next = $current->next->next;
                return true;
            }

            $current = $current->next;
        }

        return false;
    }

    public function toArray(): array
    {
        $items = [];
        $current = $this->head;

        while ($current !== null) {
            $items[] = $current->data;
            $current = $current->next;
        }

        return $items;
    }
}

$list = new LinkedList();

$list->insertFirst(20);
$list->insertFirst(10);
$list->insertLast(30);

print_r($list->toArray());

var_dump($list->search(20));

$list->delete(20);

print_r($list->toArray());

يتضمن هذا التنفيذ الإدراج في البداية، والإدراج في النهاية، والبحث، والحذف، والتحويل إلى مصفوفة للعرض.

تنفيذ القائمة المتصلة الفردية في JavaScript

فيما يلي تنفيذ JavaScript لقائمة متصلة فردية.

class ListNode {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
    }

    insertFirst(data) {
        const newNode = new ListNode(data);
        newNode.next = this.head;
        this.head = newNode;
    }

    insertLast(data) {
        const newNode = new ListNode(data);

        if (this.head === null) {
            this.head = newNode;
            return;
        }

        let current = this.head;

        while (current.next !== null) {
            current = current.next;
        }

        current.next = newNode;
    }

    search(target) {
        let current = this.head;

        while (current !== null) {
            if (current.data === target) {
                return true;
            }

            current = current.next;
        }

        return false;
    }

    delete(target) {
        if (this.head === null) {
            return false;
        }

        if (this.head.data === target) {
            this.head = this.head.next;
            return true;
        }

        let current = this.head;

        while (current.next !== null) {
            if (current.next.data === target) {
                current.next = current.next.next;
                return true;
            }

            current = current.next;
        }

        return false;
    }

    toArray() {
        const items = [];
        let current = this.head;

        while (current !== null) {
            items.push(current.data);
            current = current.next;
        }

        return items;
    }
}

const list = new LinkedList();

list.insertFirst(20);
list.insertFirst(10);
list.insertLast(30);

console.log(list.toArray());
console.log(list.search(20));

list.delete(20);

console.log(list.toArray());

يتبع إصدار JavaScript نفس منطق إصدار PHP. يتم بناء القائمة المتصلة من العقد، وتشير كل عقدة إلى العقدة التالية.

عكس قائمة متصلة في JavaScript

عكس القائمة المتصلة هو أحد أهم مشاكل القوائم المتصلة.

reverse() {
    let previous = null;
    let current = this.head;

    while (current !== null) {
        const nextNode = current.next;
        current.next = previous;
        previous = current;
        current = nextNode;
    }

    this.head = previous;
}

الفكرة هي عكس كل رابط واحدًا تلو الآخر. قبل تغيير current.next، نقوم بحفظ العقدة التالية حتى لا تفقد بقية القائمة.

التعقيد الزمني لعمليات القائمة المتصلة

يصف التعقيد الزمني كيفية نمو وقت تشغيل العملية مع زيادة عدد العقد.

بالنسبة للقائمة المتصلة الفردية، التعقيدات الشائعة هي:

• الوصول بواسطة الفهرس: O(n)

• البحث: O(n)

• التنقل: O(n)

• الإدراج في البداية: O(1)

• الحذف من البداية: O(1)

• الإدراج في النهاية بدون ذيل: O(n)

• الإدراج في النهاية مع ذيل: O(1)

• الحذف من النهاية: O(n)

• حذف عقدة معروفة بعد العقدة السابقة: O(1)

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

التعقيد المكاني للقوائم المتصلة

التعقيد المكاني للقائمة المتصلة هو O(n)، حيث n هو عدد العقد.

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

للقائمة المتصلة الفردية:

Node = data + next reference

للقائمة المتصلة المزدوجة:

Node = previous reference + data + next reference

توفر القوائم المتصلة المزدوجة مرونة أكبر ولكنها تتطلب ذاكرة أكبر.

مزايا القوائم المتصلة

للقوائم المتصلة عدة مزايا.

• يمكنها النمو والتقلص ديناميكيًا.

• الإدراج في البداية بتعقيد O(1).

• الحذف من البداية بتعقيد O(1).

• لا تتطلب ذاكرة متجاورة.

• مفيدة لتنفيذ المكدسات وقوائم الانتظار.

• تساعد على فهم المراجع والهياكل الديناميكية.

هذه المزايا تجعل القوائم المتصلة مفيدة في المشكلات التي تتغير فيها البيانات بشكل متكرر.

عيوب القوائم المتصلة

للقوائم المتصلة أيضًا عيوب مهمة.

• لا تدعم الوصول العشوائي السريع.

• البحث يستغرق O(n).

• الوصول إلى عنصر بواسطة الفهرس يستغرق O(n).

• تستخدم ذاكرة إضافية للمراجع.

• قد تكون أكثر صعوبة في التنفيذ بشكل صحيح من المصفوفات.

• التعامل السيئ مع المراجع يمكن أن يكسر القائمة.

بسبب هذه العيوب، غالبًا ما تكون المصفوفات أفضل عندما تكون هناك حاجة إلى فهرسة سريعة.

القوائم المتصلة في مشاريع البرمجيات الحقيقية

في تطوير الويب عالي المستوى، قد لا يقوم المطورون بتنفيذ القوائم المتصلة يدويًا غالبًا. توفر اللغات والأطر عادةً مصفوفات وقوائم ومجموعات وقوائم انتظار وخرائط مدمجة.

ومع ذلك، تظهر أفكار القوائم المتصلة في العديد من الأماكن:

• المكدسات وقوائم الانتظار.

• أنظمة التراجع والإعادة.

• التنقل في سجل المتصفح.

• قوائم تشغيل الموسيقى.

• إدارة الذاكرة.

• قوائم التجاور في الرسوم البيانية.

• معالجة التصادمات في جداول التجزئة في بعض التطبيقات.

• جدولة نظام التشغيل.

يُسهّل فهم القوائم المتصلة فهم كيفية تصميم هذه الأنظمة داخليًا.

الأخطاء الشائعة عند تعلم القوائم المتصلة

غالبًا ما يرتكب المبتدئون أخطاء لأن القوائم المتصلة تتطلب إدارة دقيقة للمراجع.

تشمل الأخطاء الشائعة ما يلي:

• نسيان تحديث الرأس بعد الإدراج أو الحذف.

• فقدان بقية القائمة أثناء تغيير المراجع.

• عدم التعامل مع قائمة فارغة.

• عدم التعامل مع حذف العقدة الأولى.

• إنشاء حلقة لا نهائية في القوائم المتصلة الدائرية.

• الخلط بين بيانات العقدة ومرجع العقدة.

• محاولة الوصول إلى عناصر القائمة المتصلة مثل فهارس المصفوفات.

النهج الأكثر أمانًا هو رسم العقد والمراجع قبل كتابة الكود.

قائمة تحقق عملية لفهم القوائم المتصلة

قبل الانتقال إلى هياكل البيانات المتقدمة، يجب أن يكون المطورون قادرين على الإجابة على هذه الأسئلة:

• ما هي العقدة؟

• ما هو رأس القائمة المتصلة؟

• لماذا لا يلزم أن تكون عقد القائمة المتصلة متجاورة في الذاكرة؟

• ما الفرق بين القائمة المتصلة الفردية والمزدوجة؟

• كيف يعمل الإدراج في البداية؟

• كيف يعمل الحذف حسب القيمة؟

• لماذا يكون البحث O(n)؟

• لماذا يكون الإدراج في البداية O(1)؟

• ماذا يحدث إذا تم تحديث المراجع بترتيب خاطئ؟

• كيف يمكن عكس القائمة المتصلة؟

إذا كانت هذه الأسئلة واضحة، فإن المطور يفهم المنطق الحقيقي للقوائم المتصلة.

الخاتمة

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

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

تشمل الأنواع الرئيسية القوائم المتصلة الفردية، والقوائم المتصلة المزدوجة، والقوائم المتصلة الدائرية، والقوائم المتصلة المزدوجة الدائرية. لكل نوع نقاط قوة ومقايضات مختلفة.

تشمل عمليات القائمة المتصلة التنقل، والإدراج، والحذف، والبحث، والتحديث، والعكس. يمكن أن تكون عمليات الإدراج والحذف فعالة عندما يكون الموضع معروفًا، ولكن البحث والوصول العشوائي يتطلبان وقتًا O(n).

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