Arrays وLinked Lists: الاختيار حسب نمط الاستخدام
قارن بين الذاكرة والوصول والإدراج، وافهم لماذا لا توجد بنية أفضل دائمًا خارج سياق المشكلة.
المصفوفة: ترتيب متجاور ووصول سريع
تخزن المصفوفة العناصر في ترتيب يسمح بحساب موقع العنصر من فهرسه، لذلك الوصول إلى items[i] يكون O(1) تقريبيًا. كما أن قرب العناصر في الذاكرة يساعد المعالج على جلب كتل متتابعة بكفاءة، وهو سبب عملي يجعل المصفوفة أسرع من بنى تبدو متساوية في Big-O.
الإضافة في النهاية غالبًا O(1) في المتوسط عندما تستخدم المصفوفة الديناميكية مساحة احتياطية، لكنها قد تحتاج أحيانًا إلى تخصيص مساحة أكبر ونسخ العناصر. الإدراج في البداية أو الوسط يتطلب تحريك العناصر اللاحقة ويصبح O(n).
القائمة المرتبطة: عقد وروابط
كل عقدة تحمل قيمة ورابطًا إلى التالية، وربما رابطًا إلى السابقة في القائمة المزدوجة. لا يمكنك القفز مباشرة إلى العنصر رقم 500؛ يجب المرور من البداية أو من نقطة معروفة، ولذلك الوصول حسب الفهرس O(n).
إذا كنت تملك مرجع العقدة نفسها، يمكن إدراج عقدة بعدها أو حذف التالية بتعديل عدد ثابت من الروابط. لكن إذا احتجت أولًا إلى البحث عن القيمة، تصبح العملية الكاملة O(n). هذه التفاصيل هي التي تضيع عندما نحفظ جملة «الإدراج في linked list هو O(1)» بلا شروط.
type ListNode<T> = {
value: T;
next: ListNode<T> | null;
};
function insertAfter<T>(node: ListNode<T>, value: T) {
node.next = { value, next: node.next };
}جدول قرار سريع
اختر المصفوفة عندما تحتاج قراءة حسب الفهرس، أو مرورًا متتابعًا سريعًا، أو عندما يهم تقليل overhead لكل عنصر. اختر القائمة عندما تتعامل مع سلسلة عقد تتغير كثيرًا ولديك مراجع مباشرة إلى مواضع التغيير، مثل تنفيذ بعض أشكال LRU cache بالاشتراك مع Map.
في JavaScript لا توجد linked list مدمجة، والمصفوفة محسنة جدًا في المحركات. لا تبن قائمة مرتبطة لمجرد سؤال دراسي ثم تفترض أنها أسرع في التطبيق. قِس على بيئة العمل الفعلية وفكر في بساطة الصيانة.
- •قراءة متكررة حسب الفهرس: Array.
- •إضافة وحذف في النهاية: Array غالبًا كافية.
- •نقل عقد معروفة داخل ترتيب متغير: Linked list قد تناسب.
- •بحث متكرر بالمفتاح: فكر في Map، وليس أيًا منهما وحده.
تمرين يثبت الفهم
نفذ قائمة انتظار Queue مرة بمصفوفة تستخدم shift، ومرة بمؤشر head يزداد دون حذف العنصر الأول كل مرة. قارن الزمن على عدد كبير من العمليات. ستلاحظ أن تغيير طريقة استخدام المصفوفة يمكن أن يزيل تحريك العناصر ويمنحك تصميمًا بسيطًا دون بناء عقد.
بعد ذلك صمم LRU cache. ستحتاج Map للوصول O(1) وقائمة مزدوجة لنقل العنصر المستخدم إلى المقدمة. هذا المثال يوضح أن البنى غالبًا تتعاون؛ السؤال ليس أي بنية تفوز، بل أي تركيب يخدم العمليات المطلوبة.
المراجع ومزيد من القراءة
عن المؤلف
يراجع أسامة زيدان محتوى كود هاب بهدف تقديم شرح عربي واضح يربط المفاهيم البرمجية بالقرارات التي يواجهها المتعلم أثناء التطبيق.
صفحة المؤلف