قائمة مرتبطة

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

يوضح الكود التالي المكتوب بلغة C كيفية إضافة عقدة جديدة بالقيمة "value" إلى نهاية قائمة مرتبطة أحادية:

#include <stdlib.h>// كل عقدة في القائمة المتصلة هي بنية. العقدة الرئيسية هي العقدة الأولى في القائمة.typedef struct Node {قيمة عددية صحيحة ؛struct Node * next ;} عقدة ؛Node * addNodeToTail ( Node * head , int value ) {// قم بتعريف مؤشر العقدة وتهيئته ليشير إلى العقدة الجديدة (أي أنه سيحتوي على عنوان ذاكرة العقدة الجديدة) التي ستتم إضافتها إلى نهاية القائمة.Node * temp = ( Node * ) malloc ( sizeof * temp ); /// 'malloc' in stdlib.temp -> value = value ; // أضف البيانات إلى حقل القيمة الخاص بالعقدة الجديدة.temp -> next = NULL ; // تهيئة الروابط غير الصالحة إلى قيمة فارغة.إذا لم يكن الرأس موجودًا {head = temp ; // إذا كانت القائمة المرتبطة فارغة (أي أن مؤشر عقدة الرأس هو مؤشر فارغ)، فاجعل مؤشر عقدة الرأس يشير إلى العقدة الجديدة.} آخر {Node * p = head ; // قم بتعيين مؤشر العقدة الرئيسية إلى مؤشر العقدة 'p'.بينما ( p -> التالي ) {p = p -> next ; // اجتياز القائمة حتى تصبح p هي العقدة الأخيرة. تشير العقدة الأخيرة دائمًا إلى NULL.}p -> next = temp ; // اجعل العقدة الأخيرة السابقة تشير إلى العقدة الجديدة.}return head ; // إرجاع مؤشر عقدة الرأس.}

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

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

Many modern operating systems use doubly linked lists to maintain references to active processes, threads, and other dynamic objects.^[4] A common strategy for rootkits to evade detection is to unlink themselves from these lists.^[5]

In a 'multiply linked list', each node contains two or more link fields, each field being used to connect the same set of data arranged in a different order (e.g., by name, by department, by date of birth, etc.). While a doubly linked list can be seen as a special case of multiply linked list, the fact that the two and more orders are opposite to each other leads to simpler and more efficient algorithms, so they are usually treated as a separate case.

In the last node of a linked list, the link field often contains a null reference, a special value used to indicate the lack of further nodes. A less common convention is to make it point to the first node of the list; in that case, the list is said to be 'circular' or 'circularly linked'; otherwise, it is said to be 'open' or 'linear'. It is a list where the last node pointer points to the first node (i.e., the "link to next node" pointer of the last node has the memory address of the first node).

In the case of a circular doubly linked list, the first node also points to the last node of the list.

In some implementations an extra 'sentinel' or 'dummy' node may be added before the first data record or after the last one. This convention simplifies and accelerates some list-handling algorithms, by ensuring that all links can be safely dereferenced and that every list (even one that contains no data elements) always has a "first" and "last" node.

An empty list is a list that contains no data records. This is usually the same as saying that it has zero nodes. If sentinel nodes are being used, the list is usually said to be empty when it has only sentinel nodes.

The link fields need not be physically part of the nodes. If the data records are stored in an array and referenced by their indices, the link field may be stored in a separate array with the same indices as the data records.

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

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

المصفوفة الديناميكية هي بنية بيانات تُخصص جميع عناصرها بشكل متجاور في الذاكرة، وتحتفظ بعدد العناصر الحالي. إذا تجاوزت المساحة المحجوزة للمصفوفة الديناميكية، يُعاد تخصيصها (وربما تُنسخ)، وهي عملية مكلفة.

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

علاوة على ذلك، يمكن إدراج عدد غير محدود من العناصر في قائمة مرتبطة، ولا يحدّها سوى إجمالي الذاكرة المتاحة؛ بينما ستمتلئ بنية بيانات المصفوفة الديناميكية في نهاية المطاف، مما يستدعي إعادة تخصيصها - وهي عملية مكلفة، قد لا تكون ممكنة أصلاً في حال تجزئة الذاكرة، مع العلم أنه يمكن حساب متوسط ​​تكلفة إعادة التخصيص على عمليات الإدراج، وستظل تكلفة الإدراج الناتجة عن إعادة التخصيص ثابتة عند O(1). يُسهّل هذا الأمر إضافة العناصر إلى نهاية المصفوفة، لكن الإدراج في (أو الإزالة من) المواضع الوسطى لا يزال مكلفًا للغاية بسبب نقل البيانات للحفاظ على تسلسلها. كما قد يتطلب الأمر تغيير حجم المصفوفة التي أُزيلت منها عناصر كثيرة لتجنب إهدار مساحة كبيرة.

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

من عيوب القوائم المتصلة الأخرى الحاجة إلى مساحة تخزين إضافية للمراجع، مما يجعلها غير عملية في كثير من الأحيان لقوائم البيانات الصغيرة كالأحرف أو القيم المنطقية ، لأن حجم التخزين اللازم للروابط قد يتجاوز حجم البيانات بمرتين أو أكثر. في المقابل، لا تتطلب المصفوفة الديناميكية سوى مساحة البيانات نفسها (وكمية ضئيلة جدًا من بيانات التحكم). ^{[ ملاحظة 1 ]} كما أن تخصيص الذاكرة بشكل منفصل لكل عنصر جديد قد يكون بطيئًا، بل ومُهدرًا للذاكرة مع مُخصِّص بسيط، وهي مشكلة تُحل عادةً باستخدام مجمعات الذاكرة .

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

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

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

تتشابه أنماط الوصول إلى الذاكرة واستهلاك المساحة في الشجرة المتوازنة مع القائمة المرتبطة، مع توفير فهرسة أكثر كفاءة، حيث تستغرق وقتًا قدره O(log n) بدلًا من O(n) للوصول العشوائي. مع ذلك، تُعدّ عمليات الإضافة والحذف أكثر تكلفةً نظرًا لتكلفة عمليات معالجة الشجرة للحفاظ على توازنها. توجد آلياتٌ تُمكّن الأشجار من الحفاظ على توازنها تلقائيًا، مثل أشجار AVL أو الأشجار الحمراء والسوداء .

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

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

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

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

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

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

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

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

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

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

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

قد تُسهّل عقدة الحارس بعض عمليات القوائم، بضمان وجود العقدة التالية أو السابقة لكل عنصر، وأن تحتوي القوائم الفارغة على عقدة واحدة على الأقل. كما يُمكن استخدام عقدة حارس في نهاية القائمة، مع حقل بيانات مناسب، لتجنب بعض اختبارات نهاية القائمة. على سبيل المثال، عند مسح القائمة بحثًا عن عقدة بقيمة معينة x ، فإن تعيين حقل بيانات الحارس إلى x يُغني عن اختبار نهاية القائمة داخل الحلقة. مثال آخر هو دمج قائمتين مُرتبتين: إذا كانت حقول بيانات الحارس فيهما مُعيّنة إلى +∞، فإن اختيار عقدة الإخراج التالية لا يتطلب معالجة خاصة للقوائم الفارغة.

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

مع ذلك، إذا استُخدمت القائمة الدائرية لمجرد محاكاة قائمة خطية، يُمكن تجنُّب بعض هذا التعقيد بإضافة عقدة مراقبة واحدة إلى كل قائمة، بين آخر عقدة بيانات وأولها. وفقًا لهذا الاصطلاح، تتكون القائمة الفارغة من عقدة المراقبة وحدها، وتشير إلى نفسها عبر رابط العقدة التالية. يجب أن يكون مُعرِّف القائمة مؤشرًا إلى آخر عقدة بيانات، قبل عقدة المراقبة، إذا لم تكن القائمة فارغة؛ أو إلى عقدة المراقبة نفسها، إذا كانت القائمة فارغة.

يمكن استخدام الحيلة نفسها لتبسيط التعامل مع قائمة خطية مرتبطة ثنائياً، وذلك بتحويلها إلى قائمة دائرية مرتبطة ثنائياً بعقدة حارس واحدة. مع ذلك، في هذه الحالة، يجب أن يكون المؤشر عبارة عن مؤشر واحد إلى العقدة الوهمية نفسها. ^{[ 8 ]}

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

يمكن أن تكون القوائم المرتبطة بشكل دائري إما مرتبطة بشكل فردي أو مزدوج.

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

دالة iterate(someNode) إذا كانت someNode ≠ null node := someNode يفعل قم بتنفيذ شيء ما باستخدام قيمة العقدة. node := node.next بينما node ≠ someNode

دالة insertAfter( Node node, Node newNode) إذا كان node = null // نفترض أن القائمة فارغة newNode.next := newNode آخر newNode.next := node.next node.next := newNode قم بتحديث متغير lastNode إذا لزم الأمر.

insertAfter(L, newNode) L := newNode

أدخل العقدة الجديدة بعد العقدة L إذا كانت L تساوي null، ثم اجعل L تساوي العقدة الجديدة.

دالة insertBefore( Node node, newVal) إذا كان node = null // نفترض أن القائمة فارغة newNode := new Node(data:=newVal, next:=newNode) else newNode := new Node(data:=node.data, next:=node.next) node.data := newVal node.next := newNode قم بتحديث متغير العقدة الأولى إذا لزم الأمر.

دالة remove( Node node) إذا كان node ≠ null وكان حجم القائمة > 1 removedData := node.data node.data := node.next.data node.next = node.next.next إرجاع البيانات المحذوفة

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

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

سجل الإدخال { عدد صحيح next; // فهرس الإدخال التالي في المصفوفة عدد صحيح prev; // الإدخال السابق (إذا كان مرتبطًا برابط مزدوج) سلسلة نصية name; عدد حقيقي balance; }

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

قائمة الأعداد الصحيحة ، رأس المدخلات، السجلات[1000]

يتم إنشاء الروابط بين العناصر عن طريق وضع فهرس المصفوفة للخلية التالية (أو السابقة) في حقل "التالي" أو "السابق" داخل عنصر معين. على سبيل المثال:

في المثال أعلاه، ListHeadسيتم تعيين قيمة المتغير إلى 2، وهو موقع أول عنصر في القائمة. لاحظ أن العناصر من 3 إلى 7 ليست جزءًا من القائمة. هذه الخلايا متاحة لإضافة أي عناصر جديدة إلى القائمة. من خلال إنشاء ListFreeمتغير عددي، يمكن إنشاء قائمة فارغة لتتبع الخلايا المتاحة. إذا كانت جميع العناصر مستخدمة، فسيتعين زيادة حجم المصفوفة أو حذف بعض العناصر قبل إضافة عناصر جديدة إلى القائمة.

سيقوم الكود التالي باستعراض القائمة وعرض الأسماء ورصيد الحساب:

i := listHead while i ≥ 0 // تكرار عبر القائمة print i, Records[i].name, Records[i].balance // طباعة المدخل i := Records[i].next

عند مواجهة خيار، تشمل مزايا هذا النهج ما يلي:

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

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

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

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

لإنشاء قائمة مرتبطة بالعائلات وأفرادها، باستخدام وحدة التخزين الداخلية، قد يبدو الهيكل كما يلي:

سجل العضو { // عضو من عائلة العضو التالي؛ سلسلة الاسم الأول؛ عدد صحيح العمر؛ } سجل العائلة { // العائلة نفسها family next; string lastName; string address; member members // رأس قائمة أعضاء هذه العائلة }

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

aFamily := Families // ابدأ من رأس قائمة العائلات while aFamily ≠ null // قم بالتكرار عبر قائمة العائلات معلومات مطبوعة عن العائلة aMember := aFamily.members // الحصول على أول عضو في قائمة أعضاء هذه العائلة while aMember ≠ null // المرور على قائمة الأعضاء اطبع معلومات عن العضو aMember := aMember.next aFamily := aFamily.next

باستخدام وحدة تخزين خارجية، يمكن إنشاء الهياكل التالية:

عقدة السجل { // بنية ارتباط عامة للعقدة التالية؛ مؤشر البيانات // مؤشر عام للبيانات في العقدة } سجل العضو { // بنية لعضو العائلة سلسلة الاسم الأول؛ عدد صحيح العمر } سجل العائلة { // بنية العائلة string lastName; string address; node members // رأس قائمة أعضاء هذه العائلة }

لطباعة قائمة كاملة بالعائلات وأفرادها باستخدام وحدة تخزين خارجية، اكتب ما يلي:

famNode := Families // ابدأ من رأس قائمة العائلات while famNode ≠ null // تكرار عبر قائمة العائلات aFamily := (family) famNode.data // استخراج العائلة من العقدة معلومات مطبوعة عن العائلة memNode := aFamily.members // الحصول على قائمة بأفراد العائلة while memNode ≠ null // المرور على قائمة الأفراد aMember := (member)memNode.data // استخراج العضو من العقدة اطبع معلومات عن العضو memNode := memNode.next famNode := famNode.next

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

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

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

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

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

قائمة الوصول العشوائي هي قائمة تدعم الوصول العشوائي السريع لقراءة أو تعديل أي عنصر فيها. ^{[ 9 ]} أحد التطبيقات الممكنة هو قائمة الوصول العشوائي الثنائية المائلة باستخدام نظام الأعداد الثنائية المائلة ، والذي يتضمن قائمة من الأشجار ذات خصائص مميزة؛ مما يسمح بعمليات رأس/خاتمة ذات زمن ثابت في أسوأ الحالات، والوصول العشوائي إلى عنصر بواسطة فهرسه بزمن لوغاريتمي في أسوأ الحالات. ^{[ 9 ]} يمكن تنفيذ قوائم الوصول العشوائي كهياكل بيانات مستمرة . ^{[ 9 ]}

يمكن اعتبار قوائم الوصول العشوائي بمثابة قوائم مرتبطة غير قابلة للتغيير، حيث إنها تدعم بنفس القدر عمليات الرأس والذيل O(1). ^{[ 9 ]}

يُعدّ امتداد القائمة الدنيا امتدادًا بسيطًا لقوائم الوصول العشوائي ، حيث يوفر عملية إضافية تُنتج أصغر عنصر في القائمة بأكملها في وقت ثابت (بدون تعقيدات الطفرة). ^{[ 9 ]}