Structures de données rapides avec des exemples. Première partie: liste chaînée

Préface

Lequel des développeurs iOS n'a pas rêvé de travailler dans un lieu prestigieux comme Yandex ou Avito. Malheureusement, seulement h pose des questions sur les rêves lors des entretiens, mais les intervieweurs développeurs posent des questions de nature légèrement différente. Quelle est la différence entre le type de référence et le type de valeur ou les limites du cadre? Questions que chacun de nous a entendues plus d'une fois lors des entretiens. Si votre entretien commence par une question sur les différences entre les types significatifs et de référence ou dans l'esprit de «nous parler de SOLID», alors vous êtes clairement sur la voie de trouver un emploi chez So-so-Perspectives LLC.

Dans une entreprise décente, on ne vous demandera pas de telles bêtises. Préparez-vous aux questions sur la répartition, la table d'appoint et la file d'attente sous-jacente. Connaître ces nuances en aucune façon aidera à atteindre 60 FPS lors du défilement, chargé d'éléments cellulaires et ne fera pas de vous un développeur honoraire de la Russie. Ils vous aideront à reconnaître une personne qui n'a pas seulement changé le taux xib pendant 4 ans et se considère maintenant comme un développeur iOS senior, mais qui s'intéresse vraiment à la plate-forme. Cela restera toujours un mystère pour moi à quel point une personne décide qu'elle a atteint le niveau moyen ou senior. Participe probablement à des compétitions entièrement russes, dans lesquelles ROS-GOS-iOS attribue des catégories et des titres pour avoir satisfait aux normes et aux prix.

Retour aux entretiens. Non seulement le prestigieux employeur posera des questions délicates sur la plateforme, mais il posera certainement des questions sur l'architecture. Attendez la question: "Pourquoi avez-vous utilisé VIPER au lieu de MVVM en dernier lieu?". Vous vous demandez peut-être: "Qu'est-ce qu'un mauvais MVC?". Eh bien, le dernier clou dans le couvercle du cercueil sera des algorithmes. Même si vous maîtrisez parfaitement iOS et l'architecture des applications mobiles, mais que vous ne connaissez pas les faiblesses des tableaux et que vous ne pouvez pas optimiser la recherche d'un élément, alors après l'interview, attendez une réponse par e-mail:


Sur les étendues de la langue russe, Internet regorge d'articles sur les algorithmes et les structures de données. Le seul inconvénient qui peut masquer l'étude est la rareté des exemples et des implémentations sur Swift. Il est assez difficile de comprendre ce sujet lorsque vous obtenez beaucoup de mots obscurs et des exemples C ++ encore plus obscurs.

Pour tous ceux qui veulent boire des smoothies tous les jours dans des bureaux chics et lors de réunions d'anciens élèves pour parler de la façon dont lui seul entraîne tout le développement mobile de Sber, j'ai préparé quelques articles sur les structures de données. Les articles sont destinés aux développeurs qui connaissent déjà les génériques, ont travaillé avec des tableaux / ensembles / dictionnaires, comprennent les différences entre les classes et les structures et prétendent comprendre la récursivité. Je ne peindrai pas la théorie. Cela a déjà été fait avant moi et je suis sûr que c'est assez informatif. Concentrons-nous sur les exemples.

Liste liée

Wikipedia aidera avec la théorie . Commençons par créer le même nœud.


_{* Assurez-vous de changer votre schéma de couleurs Xcode en foncé sinon vous ne verrez pas de travail dans Mail}

Un lecteur attentif devrait demander: «Pourquoi le développeur Momkin a-t-il décidé d'implémenter le nœud en tant que classe, pas en tant que structure? L'article porte sur les structures de données! » Je suggère de discuter de cette décision dans les commentaires. Passons à la liste la plus liée. L'implémentation initiale ressemblera à ceci:



Chaque expert en alésage qui se respecte notera que WeakReference est un type inconnu et nécessitera à juste titre une implémentation.



Ajoutez aux méthodes de mise en œuvre chargées de remplir notre liste:




_{* La complexité O (1) n'est valide que s'il n'est pas nécessaire de copier la structure. Sinon, nous aurons une complexité O (n). Cela s'applique à toutes les méthodes de mutation.}

Ajoutez les méthodes responsables de la suppression de la liste:




_{* @ discardableResult nous évitera d'avoir à écrire "_ =" avant d'appeler la fonction lorsque la valeur de retour ne nous intéresse pas}

Notre métier ressemble déjà à une liste chaînée fonctionnelle. Essayons de le rendre aussi orienté Swift que possible. Pour ce faire, il suffit d'implémenter deux choses: le protocole BidirectionalCollection et la technique de copie sur écriture . Commençons par le protocole. Il y a très peu de méthodes, et le plus difficile est de comprendre et de mettre en œuvre Index.




Super! Maintenant, toutes nos collections de collections sont disponibles dans notre liste. Nous pouvons lui appliquer map, compactMap, filter, contains, etc. C'était au tour de la copie sur écriture. Nous implémentons la méthode copyIfNeeded () en raison de l'absence de votre compilateur laisse entendre que le code n'a pas été écrit par D'Artagnan:



Ceux qui souhaitent poser une question intelligente ou signaler des défauts attendent dans les commentaires.
PS Je remercie ivlevAstef pour son aide dans la correction des bugs. Personne n'a encore proposé une implémentation fonctionnelle sans wrappers faibles.

Code Github