هذا المقال لمستوى: مبتدئ. لو لسه بتبدأ في هياكل البيانات وبتسمع كلمتي Array و Linked List من غير ما تعرف الفرق العملي بينهم، ده مكانك.

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

Array ضد Linked List: نفس الفكرة، تكلفة مختلفة تمامًا

المشكلة باختصار

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

المثال البسيط: صف كراسي ملزوقة مقابل عربات قطار

تخيّل عندك صف كراسي ملزوقين في الأرض بالترتيب، ومرقّمين من 1 لـ 100. ده الـ Array. لو عايز تحط كرسي جديد في أول الصف، مفيش مكان فاضي. لازم تشيل كل كرسي وتزقّه خطوة لقدّام علشان تفضّي المكان الأول. لو الصف فيه 100 كرسي، هتحرّك 100 كرسي عشان تضيف واحد بس.

دلوقتي تخيّل قطار. كل عربة مربوطة باللي بعدها بخطّاف. دي الـ Linked List. عايز تضيف عربة في الأول؟ بتربط العربة الجديدة بأول عربة موجودة وخلاص. مش محتاج تحرّك ولا عربة من اللي ورا. عملية واحدة بس، مهما كان طول القطار.

الخلاصة من المثال: الـ Array بيدفع تكلفة كل ما تزقّ العناصر، والـ Linked List بيوصّل عُقدة جديدة من غير ما يلمس الباقي.

الشرح العلمي: ذاكرة متجاورة مقابل عُقد ومؤشرات

الـ Array بيتخزّن في خانات ذاكرة متتالية ومتجاورة (contiguous memory)، زي صناديق البريد المرقّمة في الصورة فوق. ده بيخلّي الوصول لأي عنصر برقمه فوري: العنوان = بداية المصفوفة زائد الرقم مضروب في حجم العنصر. عملية حسابية واحدة، يعني وصول بـ O(1). بس عشان العناصر ملزوقة في الذاكرة، إضافة عنصر في النص أو الأول بتجبر النظام إنه ينقل كل العناصر اللي بعده مكان واحد لقدّام، وده O(n).

الـ Linked List مختلف. كل عنصر اسمه node (عُقدة)، وفيه جزئين: القيمة نفسها، ومؤشر (pointer) بيشاور على العُقدة اللي بعدها. العُقد مش لازم تكون متجاورة في الذاكرة. عشان كده الإضافة في الأول بتعدّل مؤشر واحد بس، يعني O(1). لكن الوصول للعنصر رقم 500 مش فوري؛ لازم تمشي عُقدة عُقدة من البداية، وده O(n).

الكود: قِس الفرق بنفسك

في Python، الـ list هي Array ديناميكي، والـ collections.deque مبنية كـ doubly-linked list. جرّب الكود ده على قائمة فيها 10 مليون عنصر:

from collections import deque
import timeit

ls = list(range(10000000))
dq = deque(range(10000000))

t_list = timeit.timeit(lambda: ls.insert(0, 42), number=1)
t_deque = timeit.timeit(lambda: dq.appendleft(42), number=1)

print(t_list)    # حوالي 1.6 ثانية
print(t_deque)   # حوالي 0.000027 ثانية

نفس الفكرة في JavaScript: الـ Array.prototype.unshift بيزقّ كل العناصر، فبيبقى O(n).

الأرقام والـ trade-offs

على قائمة بـ 10 مليون عنصر، الإضافة في الأول بـ list.insert(0) أخدت حوالي 1.6 ثانية، بينما deque.appendleft أخدت حوالي 0.000027 ثانية — فرق حوالي 60 ألف مرة. بس ده مش معناه إن الـ Linked List أحسن دايمًا. الـ trade-off:

• بتكسب إضافة وحذف في الأطراف بـ O(1) مع الـ deque أو الـ linked list.
• بتخسر الوصول العشوائي السريع: الوصول لعنصر بالنص في linked list بـ O(n)، بينما في Array بـ O(1).
• الـ Array كمان بيستهلك ذاكرة أقل، لأن الـ linked list بيخزّن مؤشر إضافي مع كل عنصر (8 بايت لكل node على نظام 64-bit).

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

متى لا تستخدم Linked List

متستخدمش Linked List لو شغلك الأساسي هو الوصول العشوائي للعناصر برقم الـ index، أو لو بتعمل تكرار (iteration) كتير على البيانات. الـ Array بيستغل الـ CPU cache أحسن بكتير لأن العناصر متجاورة في الذاكرة، فالقراءة المتتالية بتبقى أسرع فعليًا حتى لو الـ Big-O نظريًا متساوي. القاعدة العملية: لو مش محتاج إضافة أو حذف متكرر في الأول، ابدأ بـ Array عادي.

الخطوة التالية

افتح أي مكان في كودك بتعمل فيه list.insert(0, x) أو arr.unshift(x) جوّه حلقة (loop). لو القائمة بتكبر، استبدلها بـ collections.deque في Python أو هيكل مناسب في لغتك، وقِس الفرق بـ timeit زي ما فوق. لو لقيت الزمن نزل بشكل واضح، ده معناه إن دي كانت نقطة الاختناق فعلًا.

المصادر

• توثيق Python الرسمي — collections.deque وصفحة كيف تُنفَّذ القوائم في CPython.
• Python Wiki — TimeComplexity (تعقيد عمليات list و deque).
• MDN — Array.prototype.unshift().
• قياسات زمنية مقارِنة بين list و deque — Python deque vs list (DEV) وList vs Deque (AskPython).
• كتاب CLRS — Introduction to Algorithms، الفصل الخاص بـ Arrays و Linked Lists.
• صور توضيحية من Pexels.