Estructuras de datos rápidas con ejemplos. Primera parte: lista vinculada

Prólogo

¿Cuál de los desarrolladores de iOS no soñó con trabajar en un lugar prestigioso como Yandex o Avito? Desafortunadamente, solo hr pregunta sobre los sueños en las entrevistas, pero los entrevistadores desarrolladores hacen preguntas de una naturaleza ligeramente diferente. ¿Cuál es la diferencia entre el tipo de referencia y el tipo de valor o los límites del marco? Preguntas que cada uno de nosotros ha escuchado más de una vez en las entrevistas. Si su entrevista comienza con la pregunta sobre las diferencias entre los tipos significativos y de referencia o con el espíritu de "cuéntenos acerca de SOLID", entonces está claramente en el camino para encontrar un trabajo en So-so-Perspectives LLC.

En una empresa decente, no se le preguntarán tales tonterías. Prepárese para preguntas sobre despacho, mesa auxiliar y cola subyacente. Conocer tales matices de ninguna manera ayudará a alcanzar 60 FPS al desplazarse, cargado con elementos celulares y no lo convertirá en un desarrollador honorario de Rusia. Ayudarán a reconocer en usted a una persona que no solo ha cambiado la constante xib durante 4 años y ahora se considera un desarrollador sénior de iOS, sino que está realmente interesado en la plataforma. Siempre será un misterio para mí en qué punto una persona decide que ha alcanzado el nivel de Medio o Superior. Probablemente participa en competiciones de toda Rusia, en las que ROS-GOS-iOS otorga categorías y títulos por cumplir con los estándares y premios.

De vuelta a las entrevistas. El prestigioso empleador no solo hará preguntas difíciles sobre la plataforma, sino que también hará preguntas sobre arquitectura. Espere la pregunta: "¿Por qué usó VIPER en lugar de MVVM en el último lugar?". Quizás se esté preguntando: "¿Qué es el MVC malo?". Bueno, el último clavo en la tapa del ataúd serán algoritmos. Incluso si conoce bien iOS y la arquitectura de las aplicaciones móviles, pero no conoce las debilidades de los arreglos y no puede optimizar la búsqueda de un elemento, luego de la entrevista, espere una respuesta por correo:


En las extensiones de Internet en ruso está lleno de artículos sobre algoritmos y estructuras de datos. El único inconveniente que puede oscurecer el estudio es la escasez de ejemplos e implementaciones en Swift. Es bastante difícil entender este tema cuando obtienes muchas palabras oscuras e incluso más ejemplos oscuros de C ++.

Para todos los que quieren beber batidos todos los días en oficinas elegantes y en reuniones de antiguos alumnos para hablar sobre cómo él solo arrastra todo el desarrollo móvil de Sber, preparé un par de artículos sobre estructuras de datos. Los artículos están destinados a desarrolladores que ya están familiarizados con los genéricos, han trabajado con matrices / conjuntos / diccionarios, entienden las diferencias entre clases y estructuras y fingen que entienden la recursividad. No pintaré la teoría. Esto ya se ha hecho antes que yo y estoy seguro de que es bastante informativo. Centrémonos en los ejemplos.

Lista vinculada

Wikipedia ayudará con la teoría . Comencemos creando el mismo nodo.


_{* Asegúrese de cambiar su esquema de color Xcode a oscuro, de lo contrario no verá el trabajo en Mail}

Un lector atento debería preguntar: “¿Por qué el desarrollador de Momkin decidió implementar el nodo como una clase, no como una estructura? ¡El artículo trata sobre estructuras de datos! ” Sugiero discutir esta decisión en los comentarios. Pasemos a la lista más vinculada. La implementación inicial se verá así:



Cada experto en aburrimiento respetuoso notará que WeakReference es un tipo desconocido y requerirá implementación de manera justificada.



Agregue a los métodos de implementación responsables de llenar nuestra lista:




_{* La complejidad O (1) es válida solo si no hay necesidad de copiar la estructura. De lo contrario, tendremos O (n) complejidad. Esto se aplica a todos los métodos de mutación.}

Agregue los métodos responsables de eliminar de la lista:




_{* @ discardableResult nos ahorrará tener que escribir "_ =" antes de llamar a la función cuando el valor de retorno no nos interesa}

Nuestra nave ya parece una lista enlazada que funciona. Tratemos de hacerlo lo más rápido posible. Para hacer esto, solo necesitamos implementar dos cosas: el protocolo BidirectionalCollection y la técnica de copiar en escritura . Comencemos con el protocolo. Hay muy pocos métodos, y lo más difícil es comprender e implementar Index.




Genial Ahora todas nuestras colecciones de colecciones están disponibles en nuestra lista. Podemos aplicarle map, compactMap, filter, contiene, etc. Era el turno de copiar y escribir. Implementamos el método copyIfNeeded () debido a la falta del cual el compilador ahora sugiere que el código no fue escrito por D'Artagnan:



Aquellos que deseen hacer una pregunta inteligente o señalar fallas están esperando en los comentarios.
PD: Agradezco a ivlevAstef por ayudarme a solucionar los errores. Nadie ha propuesto una implementación funcional sin envoltorios débiles.

Código Github