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

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

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

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

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

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

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

في المراحل الأولى لتطوير لغة ليسب، استُخدمت قوائم الارتباط لحلّ مراجع المتغيرات الحرة في الإجراءات. ^{[ 5 ] [ 6 ]} في هذا التطبيق، من الملائم إضافة عملية إلى قوائم الارتباط، تعكس إضافة زوج مفتاح-قيمة دون الحاجة إلى فحص القائمة بحثًا عن نسخ أخرى من المفتاح نفسه. وبهذه الطريقة، يمكن لقائمة الارتباط أن تعمل كمكدس ، مما يسمح للمتغيرات المحلية بحجب متغيرات أخرى مؤقتًا تحمل الأسماء نفسها، دون إتلاف قيم تلك المتغيرات الأخرى. ^{[ 7 ]}

تحتوي العديد من لغات البرمجة، بما في ذلك Lisp، ^{[ 5 ]} Scheme ، ^{[ 8 ]} OCaml ، ^{[ 9 ]} و Haskell ^{[ 10 ]،} على وظائف للتعامل مع قوائم الارتباط في مكتباتها القياسية .

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