دليل شامل: بناء القوائم المتصلة (Linked Lists) في JavaScript خطوة بخطوة

إذا كنت في رحلة تعلم هياكل البيانات، فإن القوائم المتصلة (Linked Lists) تعد إحدى الهياكل الأساسية التي لا غنى عنها. يهدف هذا المقال إلى تبسيط مفهومها، وتسليط الضوء على الفروقات الجوهرية بينها وبين المصفوفات (Arrays)، وتقديم دليل عملي لكيفية تطبيقها في لغة JavaScript. لنبدأ رحلتنا.

ما هي القائمة المتصلة (Linked List)؟

القائمة المتصلة (Linked List) هي هيكل بيانات خطي يشبه إلى حد ما المصفوفة (Array). ومع ذلك، على عكس المصفوفات، لا يتم تخزين العناصر في موقع ذاكرة متجاور أو فهرس محدد. بدلاً من ذلك، كل عنصر هو كائن منفصل يحتوي على مؤشر (pointer) أو رابط (link) للعنصر التالي في القائمة. يُطلق على كل عنصر في القائمة المتصلة اسم ‘عقدة’ (node)، وتحتوي كل عقدة على جزأين رئيسيين: البيانات المخزنة (data) ومؤشر إلى العقدة التالية (next node). يمكن أن تكون البيانات أي نوع بيانات صالح.

يُعرف نقطة الدخول إلى القائمة المتصلة باسم ‘الرأس’ (head). يمثل الرأس مرجعًا للعقدة الأولى في القائمة. تشير العقدة الأخيرة في القائمة دائمًا إلى القيمة null. إذا كانت القائمة فارغة، فإن الرأس يكون مرجعًا لـ null. في JavaScript، يمكن أن تبدو القائمة المتصلة بهذا الشكل:

 const list = {
    head : {
        value : 6,
        next : {
            value : 10,
            next : {
                value : 12,
                next : {
                    value : 3,
                    next : null
                }
            }
        }
    }
 };

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

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

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

• عمليات البحث بطيئة في القوائم المتصلة. على عكس المصفوفات، لا يُسمح بالوصول العشوائي (random access) لعناصر البيانات، حيث يتم الوصول إلى العقد بشكل تسلسلي بدءًا من العقدة الأولى.
• تستهلك ذاكرة أكبر من المصفوفات بسبب الحاجة إلى تخزين المؤشرات (pointers) لكل عقدة.

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

توجد ثلاثة أنواع رئيسية من القوائم المتصلة، تختلف في كيفية تنظيم المؤشرات داخل العقد:

القوائم المتصلة الأحادية (Singly Linked Lists)

في هذا النوع، تحتوي كل عقدة على مؤشر واحد فقط يشير إلى العقدة التالية. هذا هو النوع الذي تناولناه في شرحنا حتى الآن.

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

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

القوائم المتصلة الدائرية (Circular Linked Lists)

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

تطبيق عقدة القائمة (List Node) في JavaScript

كما ذكرنا سابقًا، تحتوي عقدة القائمة (List Node) على عنصرين: البيانات (data) والمؤشر إلى العقدة التالية (next node). يمكننا تطبيق عقدة القائمة في JavaScript على النحو التالي:

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

تطبيق القائمة المتصلة (Linked List) في JavaScript

يوضح الكود التالي تطبيق فئة القائمة المتصلة (LinkedList) مع دالة البناء (constructor). لاحظ أنه إذا لم يتم تمرير عقدة الرأس (head node)، فسيتم تهيئة الرأس إلى null افتراضيًا.

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

تجميع المكونات: بناء قائمة متصلة بسيطة

دعنا الآن ننشئ قائمة متصلة باستخدام الفئة التي قمنا بتعريفها للتو. أولاً، سنقوم بإنشاء عقدتين للقائمة، وهما node1 و node2، ثم نربط العقدة الأولى بالثانية عن طريق مؤشر.

 let node1 = new ListNode(2)
 let node2 = new ListNode(5)
 node1.next = node2

بعد ذلك، سنقوم بإنشاء قائمة متصلة (LinkedList) باستخدام node1 كرأس لها.

 let list = new LinkedList(node1)

لنحاول الآن الوصول إلى البيانات في العقد داخل القائمة التي أنشأناها للتو.

 console.log(list.head.next.data) //returns 5

تطبيق دوال مساعدة (Helper Methods) للقائمة المتصلة

بعد ذلك، سنقوم بتطبيق أربع دوال مساعدة (helper methods) أساسية لفئة القائمة المتصلة لتعزيز وظائفها. هذه الدوال هي:

• size()
• clear()
• getLast()
• getFirst()

1. الدالة size(): حساب عدد العقد

تقوم هذه الدالة بإرجاع العدد الإجمالي للعقد الموجودة حاليًا في القائمة المتصلة.

 size() {
    let count = 0;
    let node = this.head;
    while (node) {
        count++;
        node = node.next
    }
    return count;
 }

2. الدالة clear(): إفراغ القائمة

تقوم هذه الدالة بإفراغ القائمة بالكامل، مما يجعلها فارغة.

 clear() {
    this.head = null;
 }

3. الدالة getLast(): الحصول على العقدة الأخيرة

تُعيد هذه الدالة العقدة الأخيرة في القائمة المتصلة.

 getLast() {
    let lastNode = this.head;
    if (lastNode) {
        while (lastNode.next) {
            lastNode = lastNode.next
        }
    }
    return lastNode
 }

4. الدالة getFirst(): الحصول على العقدة الأولى

تُعيد هذه الدالة العقدة الأولى (الرأس) في القائمة المتصلة.

 getFirst() {
    return this.head;
 }

الخلاصة التقنية

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