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

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

القائمة المترابطة (linked list) بنية بيانات خطية يكون فيها كل عنصر كائن عقدة، وتُربط العقد عبر «المراجع». ويسجّل المرجع عنوان الذاكرة للعقدة التالية، ويمكن من خلاله الوصول من العقدة الحالية إلى العقدة التالية.

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

وبمراقبة الشكل أعلاه، نجد أن الوحدة الأساسية للقائمة المترابطة هي كائن عقدة (node). وتحتوي كل عقدة على معلومتين: «قيمة» العقدة و«مرجع» إلى العقدة التالية.

• تسمى العقدة الأولى في القائمة المترابطة «العقدة الرأسية»، وتسمى العقدة الأخيرة «العقدة الذيلية».
• وتشير العقدة الذيلية إلى «null»، ويُرمز إليها بـ null وnullptr وNone في Java وC++ وPython على التوالي.
• وفي اللغات التي تدعم المؤشرات، مثل C وC++ وGo وRust، ينبغي استبدال «المرجع» المذكور آنفاً بـ«المؤشر».

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

/* بنية عقدة القائمة المترابطة */
type ListNode struct {
    Val  int       // قيمة العقدة
    Next *ListNode // مؤشر إلى العقدة التالية
}

// NewListNode مُنشئ، ينشئ قائمة مترابطة جديدة
func NewListNode(val int) *ListNode {
    return &ListNode{
        Val:  val,
        Next: nil,
    }
}

/* فئة عقدة القائمة المترابطة */
class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;        // قيمة العقدة
        this.next = next === undefined ? null : next;  // مرجع إلى العقدة التالية
    }
}

العمليات الشائعة على القوائم المترابطة

تهيئة قائمة مترابطة

يتضمن بناء قائمة مترابطة خطوتين: أولاً تهيئة كل كائن عقدة؛ وثانياً إنشاء علاقات المرجع بين العقد. وبعد اكتمال التهيئة، يمكننا اجتياز جميع العقد بدءاً من العقدة الرأسية للقائمة المترابطة عبر المرجع next.

/* هيّئ القائمة المترابطة 1 -> 3 -> 2 -> 5 -> 4 */
// هيّئ كل عقدة
n0 := NewListNode(1)
n1 := NewListNode(3)
n2 := NewListNode(2)
n3 := NewListNode(5)
n4 := NewListNode(4)
// أنشئ المراجع بين العقد
n0.Next = n1
n1.Next = n2
n2.Next = n3
n3.Next = n4

/* هيّئ القائمة المترابطة 1 -> 3 -> 2 -> 5 -> 4 */
// هيّئ كل عقدة
const n0 = new ListNode(1);
const n1 = new ListNode(3);
const n2 = new ListNode(2);
const n3 = new ListNode(5);
const n4 = new ListNode(4);
// أنشئ المراجع بين العقد
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;

المصفوفة متغير واحد؛ فمثلاً تحتوي المصفوفة nums على العناصر nums[0] وnums[1] وهكذا. أما القائمة المترابطة فتتكوّن من كائنات عقد مستقلة متعددة. ونستخدم عادةً العقدة الرأسية ممثلاً للقائمة المترابطة بأكملها؛ على سبيل المثال، يمكن الإشارة إلى القائمة المترابطة في الشيفرة أعلاه بالقائمة المترابطة n0.

إدراج عقدة

إدراج عقدة في قائمة مترابطة سهل جداً. وكما يوضح الشكل أدناه، لنفترض أننا نريد إدراج عقدة جديدة P بين عقدتين متجاورتين n0 وn1. لا نحتاج إلا إلى تغيير مرجعَي عقدتين (مؤشرين)، بتعقيد زمني $O(1)$.

وفي المقابل، فإن التعقيد الزمني لإدراج عنصر في مصفوفة هو $O(n)$، وهو غير فعّال عند التعامل مع كميات كبيرة من البيانات.

/* أدرج العقدة P بعد العقدة n0 في القائمة المترابطة */
function insert(n0: ListNode, P: ListNode): void {
    const n1 = n0.next;
    P.next = n1;
    n0.next = P;
}

حذف عقدة

وكما يوضح الشكل أدناه، فإن حذف عقدة في قائمة مترابطة مريح جداً أيضاً. لا نحتاج إلا إلى تغيير مرجع عقدة واحدة (مؤشرها).

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

/* احذف العقدة الأولى بعد العقدة n0 في القائمة المترابطة */
function remove(n0: ListNode): void {
    if (!n0.next) {
        return;
    }
    // n0 -> P -> n1
    const P = n0.next;
    const n1 = P.next;
    n0.next = n1;
}

الوصول إلى عقدة

الوصول إلى العقد في القائمة المترابطة أقل كفاءة. وكما ذُكر في القسم السابق، يمكننا الوصول إلى أي عنصر في مصفوفة في زمن $O(1)$. أما القوائم المترابطة فليس الأمر كذلك فيها. إذ يحتاج البرنامج إلى البدء من العقدة الرأسية والاجتياز واحداً واحداً حتى العثور على العقدة الهدف. أي إن الوصول إلى العقدة رقم $i$ في قائمة مترابطة يتطلب $i - 1$ تكرار، بتعقيد زمني $O(n)$.

/* اوصل إلى العقدة عند الفهرس index في القائمة المترابطة */
func access(head *ListNode, index int) *ListNode {
	for i := 0; i < index; i++ {
		if head == nil {
			return nil
		}
		head = head.Next
	}
	return head
}

/* اوصل إلى العقدة عند الفهرس index في القائمة المترابطة */
function access(head: ListNode | null, index: number): ListNode | null {
    for (let i = 0; i < index; i++) {
        if (!head) {
            return null;
        }
        head = head.next;
    }
    return head;
}

البحث عن عقدة

اجتَز القائمة المترابطة للعثور على عقدة قيمتها target، وأخرج فهرس تلك العقدة في القائمة المترابطة. وهذه العملية بحث خطي أيضاً. وتُعرض الشيفرة أدناه:

/* ابحث عن أول عقدة قيمتها target في القائمة المترابطة */
function find(head: ListNode | null, target: number): number {
    let index = 0;
    while (head !== null) {
        if (head.val === target) {
            return index;
        }
        head = head.next;
        index += 1;
    }
    return -1;
}

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

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

جدول   مقارنة كفاءة المصفوفة والقائمة المترابطة

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

وكما يوضح الشكل أدناه، هناك ثلاثة أنواع شائعة للقوائم المترابطة:

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

/* بنية عقدة القائمة المترابطة المزدوجة */
type DoublyListNode struct {
    Val  int             // قيمة العقدة
    Next *DoublyListNode // مؤشر إلى العقدة اللاحقة
    Prev *DoublyListNode // مؤشر إلى العقدة السابقة
}

// NewDoublyListNode التهيئة
func NewDoublyListNode(val int) *DoublyListNode {
    return &DoublyListNode{
        Val:  val,
        Next: nil,
        Prev: nil,
    }
}

/* فئة عقدة القائمة المترابطة المزدوجة */
class ListNode {
    val: number;
    next: ListNode | null;
    prev: ListNode | null;
    constructor(val?: number, next?: ListNode | null, prev?: ListNode | null) {
        this.val = val  ===  undefined ? 0 : val;        // قيمة العقدة
        this.next = next  ===  undefined ? null : next;  // مرجع إلى العقدة اللاحقة
        this.prev = prev  ===  undefined ? null : prev;  // مرجع إلى العقدة السابقة
    }
}

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

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

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

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

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

تُستخدم القوائم المترابطة الدائرية عادةً في الحالات التي تتطلب عمليات دورية، مثل جدولة موارد نظام التشغيل.

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