أنت لا تستخدم القوائم المرتبطة (Linked Lists)، لكنها تُدير نصف برمجياتك.

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

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

إنها موجودة في كل مكان: • أزرار الرجوع والتقدم في المتصفح. • سجل التراجع (undo history) في محررات النصوص. • مخبئات LRU في خوادم الويب وقواعد البيانات. • أوامر القوائم في Redis. • مجدول العمليات في نواة Linux.

إنها ليست آثارًا من الماضي، بل هي بنية تحتية.

السبب الحقيقي وراء ضعف أداء القوائم المرتبطة هو "محلية الذاكرة المخبئية" (cache locality). فالمعالج (CPU) لا يقرأ ذاكرة الوصول العشوائي (RAM) بايتًا تلو الآخر، بل يسحب كتلة بحجم 64 بايت تُسمى "سطر الذاكرة المخبئية" (cache line).

المصفوفات سريعة لأن عناصرها تقع متجاورة في الذاكرة. يقرأ المعالج العنصر الأول ويحصل على الـ 15 عنصرًا التالية مجانًا.

أما القوائم المرتبطة فتدمر هذا المبدأ؛ حيث تقع كل عقدة (node) في مكان مختلف في الذاكرة. تتبع المؤشر (pointer) يجبر المعالج على القفز إلى عنوان جديد، مما يستدعي عملية جلب جديدة من الذاكرة (RAM fetch)، وهذا يكلف مئات الدورات من دورات المعالج (CPU cycles).

في الأجهزة الحديثة، يمكن أن يكون التنقل عبر المصفوفات أسرع بـ 10 إلى 100 مرة من التنقل عبر القوائم المرتبطة. وتتجاهل تدوين Big-O هذه التكلفة الثابتة.

إذًا، متى تستخدمها؟

استخدم القائمة المرتبطة الأحادية (singly linked list) للمكدسات (stacks) أو طوابير المهام البسيطة حيث تضيف أو تحذف من طرف واحد فقط.

استخدم القائمة المرتبطة المزدوجة (doubly linked list) عندما تحتاج إلى حذف بتعقيد O(1) باستخدام مرجع مباشر للعقدة. هذا هو سر مخبأ LRU.

يحتاج مخبأ LRU إلى:

  • بحث (lookup) بتعقيد O(1).
  • إدراج (insertion) بتعقيد O(1).
  • إخراج (eviction) بتعقيد O(1).
  • ترقية (promotion) بتعقيد O(1).

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

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

توقف عن تعلم هياكل البيانات لمجرد اجتياز المقابلات؛ تعلمها لتفهم كيف تتفاعل البرمجيات مع الأجهزة.

المصدر: https://dev.to/islamhafez0/you-dont-use-linked-lists-but-theyre-running-half-your-software-4b37