Структуры данных с примерами на языке Swift. Часть первая: связаный список

в 17:03, , рубрики: data structures, swift, разработка под iOS

Предисловие

Кто из 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. Часть первая: связаный список - 1
На просторах русскоязычного интернета полным-полно статей про алгоритмы и структуры данных. Единственный недостаток, который может омрачить изучение — скудность примеров и реализаций на Swift. Достаточно сложно разбираться в этой теме, когда тебе подсовывают много непонятных слов и еще больше непонятных примеров на C++.

Для всех, кто хочет каждый день пить смузи в шикарных офисах и на встречах выпускников рассказывать как он один тащит на себе всю мобильную разработку Сбера, я подготовил пару статей по структурам данных. Статьи рассчитаны на разработчиков, которые уже знакомы с дженериками, работали с массивами/множествами/словарями, разбираются в отличиях классов от структур и делают вид, что понимают рекурсию. Я не буду расписывать теорию. Это уже сделано до меня и уверен, что достаточно информативно. Сосредоточимся на примерах.

Связаный список

С теорией поможет википедия. Начнем с создания того самого узла.

Структуры данных с примерами на языке Swift. Часть первая: связаный список - 2
*обязательно смените свою цветовую схему Xcode на темную иначе не видать вам работы в Mail

Внимательный читатель должен задаться вопросом: «Почему мамкин девелопер решил реализовать узел как класс, а не структуру? Статья же про структуры данных!». Обсудить это решение предлагаю в комментариях. Перейдем к самому связанному списку. Начальная реализация будет выглядеть так:

Структуры данных с примерами на языке Swift. Часть первая: связаный список - 3

Каждый уважающий себя эксперт-зануда отметит, что WeakReference какой-то неведомый тип и справедливо потребует реализацию.

Структуры данных с примерами на языке Swift. Часть первая: связаный список - 4

Добавим в реализацию методы, отвечающие за наполнение нашего списка:

Структуры данных с примерами на языке Swift. Часть первая: связаный список - 5
Структуры данных с примерами на языке Swift. Часть первая: связаный список - 6
Структуры данных с примерами на языке Swift. Часть первая: связаный список - 7

Добавим методы, отвечающие за удаление из списка:

Структуры данных с примерами на языке Swift. Часть первая: связаный список - 8
Структуры данных с примерами на языке Swift. Часть первая: связаный список - 9
Структуры данных с примерами на языке Swift. Часть первая: связаный список - 10
*@discardableResult избавит нас от необходимости писать "_ = " перед вызовом функции, когда возвращаемое значение нам не интересно

Наша поделка уже выглядит как рабочий связаный список. Попробуем сделать ее максимально Swift-ориентированной. Для этого нам осталось реализовать всего две вещи: BidirectionalCollection протокол и copy-on-write технику. Начнем с протокола. Методов в нем совсем мало и самое сложное это понять и реализовать Index.

Структуры данных с примерами на языке Swift. Часть первая: связаный список - 11
Структуры данных с примерами на языке Swift. Часть первая: связаный список - 12

Замечательно! Теперь нашему списку доступны все плюшки коллекций. Можем применить к нему map, compactMap, filter, contains и тд. Настала очередь copy-on-write. Реализуем метод copyIfNeeded() из-за отсутствия которого у вас сейчас компилятор намекает на то, что код писал не Д'Артаньян:

Структуры данных с примерами на языке Swift. Часть первая: связаный список - 13

Желающих задать умный вопрос или указать на недочеты жду в комментариях.

Код на GitHub

Автор: mamkin_developer

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js