ملخص Linked List للمقابلات البرمجية
مقدمة
مثل الـArrays، تُستخدم الـLinked List لتمثيل بيانات متسلسلة. وهي مجموعة خطية من عناصر البيانات لا يُشتق ترتيبها من مواضعها الفيزيائية في الذاكرة، بخلاف الـArrays حيث تُخزن البيانات في كتل ذاكرة متتالية. وبدلاً من ذلك، يحتوي كل عنصر على عنوان العنصر التالي. وهي هيكل بيانات يتكون من مجموعة عقد تمثل معاً تسلسلاً.
في أبسط صورها، تحتوي كل عقدة على: بيانات، ومرجع (بمعنى آخر، رابط) إلى العقدة التالية في التسلسل.
المزايا
إدراج عقدة في القائمة وحذفها (بمعرفة موضعها) هو O(1)، بينما في الـArrays يجب إزاحة العناصر التالية.
العيوب
زمن الوصول خطي لأن الوصول المباشر إلى العناصر حسب موضعها في القائمة غير ممكن (في الـArrays يمكنك كتابة arr[4] مثلاً). عليك الاجتياز من البداية.
مصادر التعلم
- قراءات
- فيديوهات
- Singly-linked lists، University of California San Diego
- Doubly linked lists، University of California San Diego
أنواع الـLinked Lists
الـLinked List الأحادية
Linked List تشير فيها كل عقدة إلى العقدة التالية وتشير العقدة الأخيرة إلى null.
الـLinked List المزدوجة
Linked List تحتوي فيها كل عقدة على مؤشرين، next يشير إلى العقدة التالية وprev يشير إلى العقدة السابقة. ويشير مؤشر prev في العقدة الأولى ومؤشر next في العقدة الأخيرة إلى null.
الـLinked List الدائرية
Linked List أحادية تشير فيها العقدة الأخيرة عائدةً إلى العقدة الأولى. وهناك صيغة Linked List مزدوجة دائرية يشير فيها مؤشر prev في العقدة الأولى إلى العقدة الأخيرة ويشير مؤشر next في العقدة الأخيرة إلى العقدة الأولى.
التطبيقات
من بين اللغات الشائعة، توفر Java وحدها تطبيقاً للقائمة المترابطة. ولحسن الحظ، من السهل كتابة قائمتك المترابطة الخاصة مهما كانت اللغة.
| اللغة | واجهة برمجة التطبيقات |
|---|---|
| C++ | std::list |
| Java | java.util.LinkedList |
| Python | غير متاح |
| JavaScript | غير متاح |
الـtime complexity
| العملية | Big-O | ملاحظة |
|---|---|---|
| الوصول | O(n) | |
| البحث | O(n) | |
| الإدراج | O(1) | بافتراض أنك اجتزت إلى موضع الإدراج |
| الحذف | O(1) | بافتراض أنك اجتزت إلى العقدة المراد حذفها |
إجراءات شائعة
كن على دراية بالإجراءات التالية لأن العديد من أسئلة الـLinked Lists تستخدم واحداً أو أكثر منها في الحل:
- عدّ عدد العقد في الـLinked List
- عكس Linked List في المكان نفسه
- إيجاد العقدة الوسطى في الـLinked List باستخدام مؤشرين (سريع/بطيء)
- دمج قائمتين مترابطتين معاً
الحالات الحدّية
- Linked List فارغة (الرأس
null) - عقدة واحدة
- عقدتان
- Linked List تحتوي دورات. نصيحة: وضّح مسبقاً مع المحاور ما إذا كان يمكن أن توجد دورة في القائمة. عادةً يكون الجواب لا، ولن تحتاج إلى معالجتها في الشيفرة
تقنيات
العقد الوهمية/الحراسة
إضافة عقدة حارسة/وهمية عند الرأس و/أو الذيل قد تساعد على معالجة العديد من الحالات الحدّية حيث يجب إجراء العمليات عند الرأس أو الذيل. فوجود العقد الوهمية يضمن أساساً ألا تُنفذ العمليات على الرأس أو الذيل أبداً، ويزيل بذلك الكثير من عناء كتابة فحوصات شرطية للتعامل مع المؤشرات الفارغة. تأكد من تذكر إزالتها في نهاية العملية.
Two Pointers
أساليب المؤشرين شائعة أيضاً في الـLinked Lists. ويُستخدم هذا الأسلوب في العديد من مسائل الـLinked Lists الكلاسيكية.
- إيجاد العقدة رقم k من النهاية — استخدم مؤشرين حيث يتقدم أحدهما k عقدة عن الآخر. وعندما تصل العقدة المتقدمة إلى النهاية، تكون العقدة الأخرى خلفها بمقدار k عقدة
- كشف الدورات — استخدم مؤشرين حيث يزيد أحدهما بمقدار ضعف الآخر؛ فإذا التقى المؤشران، فهذا يعني وجود دورة
- إيجاد العقدة الوسطى — استخدم مؤشرين حيث يزيد أحدهما بمقدار ضعف الآخر. وعندما تصل العقدة الأسرع إلى نهاية القائمة، تكون العقدة الأبطأ عند المنتصف
استخدام المساحة
يمكن حل العديد من مسائل الـLinked Lists بسهولة بإنشاء Linked List جديدة وإضافة العقد إليها مع النتيجة النهائية. لكن هذا يستهلك مساحة إضافية ويجعل السؤال أقل تحدياً بكثير. وسيطلب منك المحاور عادةً تعديل الـLinked List في مكانها وحل المسألة دون تخزين إضافي. يمكنك استعارة أفكار من مسألة Reverse a Linked List.
عمليات تعديل أنيقة
كما ذُكر سابقاً، تتيح طبيعة الذاكرة غير المتسلسلة في الـLinked List تعديلاً فعالاً لمحتوياتها. وبخلاف الـArrays حيث لا يمكنك إلا تعديل القيمة في موضع معين، يمكنك في الـLinked Lists تعديل مؤشر next بالإضافة إلى value.
فيما يلي بعض العمليات الشائعة وكيفية تحقيقها بسهولة:
- اقتطاع قائمة — اضبط مؤشر
nextإلىnullعند العنصر الأخير - تبديل قيم العقد — تماماً كالـArrays، بدّل قيمة العقدتين فقط؛ لا حاجة لتبديل مؤشر
next - دمج قائمتين — اربط رأس القائمة الثانية بذيل القائمة الأولى
أسئلة أساسية
هذه أسئلة أساسية للتدريب عليها إذا كنت تدرس هذا الموضوع.
أسئلة تدريب موصى بها
هذه أسئلة موصى بالتدريب عليها بعد أن تدرس الموضوع وتتدرب على الأسئلة الأساسية.
المصدر والرخصة
هذه الصفحة منسوخة من Tech Interview Handbook للمؤلف يانغشون تاي (Yangshun Tay)، النسخة المرجعية e1d28e8، وتُستخدم بموجب رخصة MIT — حقوق النشر (c) 2017-Present ليانغشون تاي. نص الرخصة محفوظ محلياً في /licenses/tech-interview-handbook.txt.