[Из песочницы] Структуры данных с примерами на языке Swift. Часть первая: связаный список
Предисловие
Кто из iOS разработчиков не мечтал о работе в престижном месте вроде Yandex или Avito. К сожалению, про мечты на собеседованиях спрашивает только hr, а вот интервьюеры из числа разработчиков задают вопросы немного другого характера. Чем отличается reference type от value type или bounds от frame? Вопросы, который каждый из нас слышал не раз на собеседованиях. Если ваше интервью начинается с вопроса про отличия значимого и ссылочного типов или в духе «расскажите ка нам про SOLID», то вы явно на пути трудоустройства в ООО «Так себе перспективы».
В приличной компании у вас такую ерунду не спросят. Готовьтесь к вопросам про диспетчеризацию, side table и underlying queue. Знания подобных нюансов никоем образом не помогут добиться 60 FPS при скролле, нагруженных элементами ячеек и не сделают вас почетным девелопером России. Они помогут распознать в вас человека, который не просто 4 года менял констрейнты в xib-ах и теперь считает себя Senior iOS Developer, а действительно интересуется платформой. Для меня всегда останется загадкой, в какой момент человек решает, что он достиг уровня Middle или Senior. Наверное участвует в общероссийских соревнованиях, на которых РОС-ГОС-iOS присуждает разряды и звания за выполнение нормативов и призовые места.
Вернемся к собеседованиям. Мало того, что престижный работодатель обязательно задаст заковыристые вопросы по платформе, так еще обязательно спросит про архитектуру. Ждите вопроса: «Почему на прошлом месте вы использовали именно VIPER, а не MVVM?». Могут поинтересоваться: «Чем плох MVC?». Ну и последним гвоздем в крышку гроба будут алгоритмы. Даже если вы блестяще разбираетесь в iOS и архитектуре мобильных приложений, но не знаете слабые стороны массивов и не можете оптимизировать поиск элемента, то после собеседования ждите на почту ответ:
На просторах русскоязычного интернета полным-полно статей про алгоритмы и структуры данных. Единственный недостаток, который может омрачить изучение — скудность примеров и реализаций на Swift. Достаточно сложно разбираться в этой теме, когда тебе подсовывают много непонятных слов и еще больше непонятных примеров на C++.
Для всех, кто хочет каждый день пить смузи в шикарных офисах и на встречах выпускников рассказывать как он один тащит на себе всю мобильную разработку Сбера, я подготовил пару статей по структурам данных. Статьи рассчитаны на разработчиков, которые уже знакомы с дженериками, работали с массивами/множествами/словарями, разбираются в отличиях классов от структур и делают вид, что понимают рекурсию. Я не буду расписывать теорию. Это уже сделано до меня и уверен, что достаточно информативно. Сосредоточимся на примерах.
Связаный список
С теорией поможет википедия. Начнем с создания того самого узла.
*обязательно смените свою цветовую схему Xcode на темную иначе не видать вам работы в Mail
Внимательный читатель должен задаться вопросом: «Почему мамкин девелопер решил реализовать узел как класс, а не структуру? Статья же про структуры данных!». Обсудить это решение предлагаю в комментариях. Перейдем к самому связанному списку. Начальная реализация будет выглядеть так:
Каждый уважающий себя эксперт-зануда отметит, что WeakReference какой-то неведомый тип и справедливо потребует реализацию.
Добавим в реализацию методы, отвечающие за наполнение нашего списка:
Добавим методы, отвечающие за удаление из списка:
*@discardableResult избавит нас от необходимости писать »_ = » перед вызовом функции, когда возвращаемое значение нам не интересно
Наша поделка уже выглядит как рабочий связаный список. Попробуем сделать ее максимально Swift-ориентированной. Для этого нам осталось реализовать всего две вещи: BidirectionalCollection протокол и copy-on-write технику. Начнем с протокола. Методов в нем совсем мало и самое сложное это понять и реализовать Index.
Замечательно! Теперь нашему списку доступны все плюшки коллекций. Можем применить к нему map, compactMap, filter, contains и тд. Настала очередь copy-on-write. Реализуем метод copyIfNeeded () из-за отсутствия которого у вас сейчас компилятор намекает на то, что код писал не Д'Артаньян:
Желающих задать умный вопрос или указать на недочеты жду в комментариях.
Код на GitHub
