هياكل البيانات السريعة مع أمثلة. الجزء الأول: قائمة مرتبطة

مقدمة

أي من مطوري iOS لم يحلم بالعمل في مكان مرموق مثل Yandex أو Avito. لسوء الحظ ، يسأل hr فقط عن الأحلام في المقابلات ، ولكن يقوم القائمون بمقابلة مطور البرامج بطرح أسئلة ذات طبيعة مختلفة قليلاً. ما هو الفرق بين نوع المرجع ونوع القيمة أو الحدود من الإطار؟ أسئلة سمعها كل منا أكثر من مرة في المقابلات. إذا بدأت مقابلتك بسؤال حول الاختلافات بين الأنواع المهمة والمرجعية أو بروح "أخبرنا عن SOLID" ، فأنت على الطريق الصحيح لإيجاد وظيفة في So-so-Perspectives LLC.

في شركة محترمة لن يُطلب منك مثل هذا الهراء. احصل على استعداد لأسئلة حول الإرسال والطاولة الجانبية وقائمة الانتظار الأساسية. إن معرفة مثل هذه الفروق الدقيقة بأي حال من الأحوال سوف يساعد على تحقيق 60 إطارًا في الثانية عند التمرير وتحميلها بعناصر خلية ولن تجعلك مطورًا فخريًا لروسيا. سيساعدون في التعرف عليك شخصًا لم يغير ثابت xib منذ 4 سنوات ويعتبر الآن نفسه مطورًا أقدم لنظام iOS ، ولكنه مهتم حقًا بالمنصة. سيبقى دائمًا لغزًا بالنسبة لي عند النقطة التي يقرر فيها الشخص أنه قد وصل إلى المستوى المتوسط ​​أو الأعلى. ربما تشارك في جميع المسابقات الروسية ، حيث تمنح ROS-GOS-iOS فئات وعناوين للوفاء بالمعايير والجوائز.

العودة إلى المقابلات. لن يقتصر الأمر على صاحب العمل المرموق بطرح أسئلة صعبة حول المنصة ، ولكنه سيسأل بالتأكيد عن الهندسة المعمارية. انتظر السؤال: "لماذا استخدمت VIPER بدلاً من MVVM في المكان الأخير؟". قد تتساءل: "ما هو MVC السيئ؟". حسنًا ، آخر مسمار في غطاء التابوت سيكون خوارزميات. حتى لو كنت على دراية رائعة بنظام iOS وبنية تطبيقات الهاتف المحمول ، لكنك لا تعرف نقاط الضعف في المصفوفات ولا يمكنك تحسين البحث عن عنصر ، ثم بعد المقابلة ، انتظر الرد عبر البريد الإلكتروني:


على مساحات الإنترنت باللغة الروسية مليئة بمقالات حول الخوارزميات وهياكل البيانات. العيب الوحيد الذي يمكن أن يحجب الدراسة هو ندرة الأمثلة والتطبيقات على سويفت. من الصعب للغاية فهم هذا الموضوع عندما تحصل على الكثير من الكلمات الغامضة وحتى أمثلة C ++ الغامضة.

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

قائمة مرتبطة

سوف تساعد ويكيبيديا في هذه النظرية . لنبدأ بإنشاء العقدة نفسها .


_{* تأكد من تغيير نظام ألوان Xcode إلى الظلام وإلا فلن ترى العمل في البريد}

يجب على القارئ اليقظ أن يسأل: "لماذا قرر مطور Momkin تنفيذ العقدة كصف وليس بنية؟ المقال يدور حول هياكل البيانات! " أقترح مناقشة هذا القرار في التعليقات. دعنا ننتقل إلى القائمة الأكثر ارتباطا. سيبدو التنفيذ الأولي كما يلي:



سوف يلاحظ كل خبير محترم ذاتي أن WeakReference هو نوع غير معروف وسيحتاج إلى تنفيذ له ما يبرره.



أضف إلى أساليب التنفيذ المسؤولة عن ملء قائمتنا:




_{* التعقيد O (1) صالح فقط إذا لم تكن هناك حاجة لنسخ الهيكل. خلاف ذلك ، سيكون لدينا O (ن) التعقيد. وهذا ينطبق على جميع أساليب التحور.}

أضف الطرق المسؤولة عن الإزالة من القائمة:




_{* @ discardableResult سينقذنا من الاضطرار إلى الكتابة "_ =" قبل استدعاء الوظيفة عندما تكون قيمة الإرجاع غير مهمة بالنسبة لنا}

حرفة لدينا بالفعل تبدو وكأنها قائمة مرتبطة العمل. دعنا نحاول جعله موجهًا إلى أقصى حد ممكن. للقيام بذلك ، نحتاج فقط إلى تنفيذ شيئين: بروتوكول BidirectionalCollection وأسلوب النسخ عند الكتابة . لنبدأ بالبروتوكول. هناك عدد قليل جدًا من الأساليب ، والأمر الأكثر صعوبة هو فهم الفهرس وتطبيقه.




! رائع الآن جميع مجموعات مجموعاتنا متاحة لقائمتنا. يمكننا تطبيق الخريطة ، وضغط الخريطة ، والتصفية ، والميزات ، وما إلى ذلك. كان دور النسخ على الكتابة. نحن نطبق طريقة copyIfNeeded () بسبب نقص المترجم الذي يلمح الآن إلى أن الكود لم يكتبه D'Artagnan:



أولئك الذين يرغبون في طرح سؤال ذكي أو الإشارة إلى العيوب ينتظرون في التعليقات.
ملاحظة: أشكر ivlevAstef للمساعدة في إصلاح الخلل. لم يقترح أحد تنفيذًا عمليًا بدون أغلفة ضعيفة.

كود جيثب