Односвязный список — это одна из многих структур данных. Структура данных — это набор данных, отношения между ними и функциональные возможности или методы, которые можно использовать для доступа к ним. Обычными структурами данных, широко используемыми в Swift, являются массивы, наборы и словари. Эти структуры данных охватывают большинство вариантов использования. Однако в некоторых случаях использование других структур данных более эффективно.

Почему вас это должно волновать?

Помимо расширения вашего набора инструментов для структур данных, который вы можете эффективно развертывать на разовой основе, вы также можете увеличить вероятность того, что вас наймут крупные технологические компании, узнав о структурах данных. Известно, что FAANG основывает большинство своих вопросов на интервью на теории и практической реализации структур данных.

Как упоминалось выше, есть случаи использования, в которых имеет смысл предпочесть связанные списки массивам или другим структурам данных. Как вы, наверное, знаете, массивы индексируют все содержащиеся в них элементы. Эта характеристика работает в обоих направлениях — она имеет как преимущества, так и недостатки.

Одной из областей, в которой массивы преуспевают, является доступ. Доступ к массивам эффективен из-за того, как они структурированы. Нам не нужно сдвигать индексы элементов или проходить через массив, чтобы получить доступ к нужному элементу. Мы просто делаем это:

С другой стороны, вставка элементов в начало массива неэффективна.

Неэффективность связана с необходимостью переиндексации всех элементов. Здесь лучше использовать связанный список.

Как работают связанные списки?

Существует три типа связанных списков: одиночные, дважды и круговые. В этой статье я буду придерживаться односвязных списков. Односвязный список состоит из следующих свойств:

  • головка (первый узел)
  • хвост (последний узел)

Вот и все. Круглые элементы называются узлами. Узел состоит из следующих свойств:

  • значение
  • ссылка на следующий узел

Пройдемся по коду:

  • использование дженериков позволяет создавать связанные списки любого типа, который мы хотим
  • в инициализаторе мы присваиваем значение по умолчанию nil следующему параметру, поскольку следующего узла может не быть
  • isEmpty – это вычисляемое свойство, которому будет присвоено значение true, если головка отсутствует.

Простота этой структуры неуловима. Подумайте об этом — как мы можем получить доступ, например, к третьему значению в списке? Связанный список, в отличие от массива, не индексируется.

Очевидно, что это плохой способ построения связанного списка. Мы создадим методы, которые позволят избежать ручного создания узлов. Цель здесь — показать, что для доступа к нужному узлу необходимо пройтись по узлам со свойством .next.

толчок (_ значение: T)

Рекомендуется сначала попробовать реализовать методы самостоятельно.

  • мы определяем метод push, который принимает общий тип и ничего не возвращает.
  • мы создаем экземпляр узла с value (поскольку мы используем дженерики, это может быть bool, String и т. д.) и head (следующий параметр — это ссылка на следующий узел )
  • если хвост равен нулю, мы присваиваем голову хвосту

Давайте рассмотрим код шаг за шагом:

  • когда мы в первый раз добавляем узел в список, у списка нет ни головы, ни хвоста. Поэтому, когда мы push(3), следующее свойство узла, которое мы создаем, равно нулю. Назначаем этот узел голове.
  • хвост по-прежнему равен нулю, поэтому мы присваиваем голову хвосту. Теперь и голова, и хвост равны 3. Мы можем это проверить. Удалите push(2) и push(1):
  • когда мы добавляем push(2), созданный узел имеет значение 2, а его следующим свойством является голова, которую мы назначили ранее (которая равна 3). Итак, наш список сейчас выглядит так: 2 (голова) -> 3 (конец)
  • так как хвост не равен нулю, кодовый блок не вводится
  • обратите внимание, что метод push(_ value: T) не изменяет хвост после того, как хвост назначен с помощью первого нажатия

Однако смущает одно. Было бы намного удобнее, если бы мы распечатали наш связанный список, чтобы мы могли видеть, что происходит. Следующая переменная не является обязательной, поэтому я не буду ее объяснять (к тому же это может вас сейчас запутать). Он используется исключительно в иллюстративных целях:

Теперь мы можем видеть, что происходит с каждым вызовом push. Шум.

pop() -> T?

  • мы определяем метод с именем pop(), который не принимает никаких параметров и возвращает общее необязательное значение.
  • defer используется для выполнения кода непосредственно перед выходом из области, в которой содержится оператор. Это означает, что после return head, непосредственно перед передачей области действия наружу, код внутри defer будет запущен
Sequence of events:
1. return head?.value
2. defer { // this code block is run }
  • когда мы pop() в первый раз, будет вызван defer, но его блок кода еще не будет выполнен
  • поэтому мы return.head (это узел со значением 1). Это узел, который выталкивается из списка
  • затем запускается блок кода внутри defer. Причина, по которой мы используем defer, заключается в том, что мы хотим вернуть значение предыдущего заголовка перед назначением ему нового узла.
  • свойство next первого узла равно 2, поэтому head теперь равно 2
  • isEmpty не равен нулю (поскольку заголовок имеет значение), поэтому этот блок кода не вводится
  • self.print называется
  • в последний раз, когда мы pop(), мы должны установить head и tail равными нулю. Поскольку 3 является последним значением, его свойство next равно nil (таким образом, для head установлено значение nil)
  • поскольку head равен нулю, мы вводим блок кода isEmpty и также устанавливаем tail равным нулю

добавить (_ значение: T)

Нам нужно сделать три вещи:

  • 1. Создайте ссылку на узел, который мы собираемся добавить
  • 2. Назначьте новый хвост
  • 3. Рассмотрим крайний случай, когда список пуст.
  • при первом добавлении список пуст. Мы создаем узел со значением, которое было передано в метод
  • созданный узел назначается свойству next элемента tail. Но так как нет хвоста, необязательно связанный хвост даст ноль
  • в строке 5 присваивается новый хвост (1).
  • head равен нулю, поэтому вводится блок кода isEmpty.
  • голова и хвост теперь одинаковы
  • во второй раз, когда мы добавляем, tail?.next устанавливается на созданный нами узел (2).
  • Этот узел теперь является новым хвостом.

removeLast() -> Узел‹T›?

Этот метод отличается от методов, которые мы использовали ранее. Помните, что мы должны перебирать узлы, чтобы получить желаемый узел. До сих пор в этом не было необходимости: когда мы использовали push(), нам просто нужно было назначить новую голову. Не было необходимости перебирать список. То же самое касается pop() и append(). Все, что нам нужно было сделать с помощью append(), — это назначить новый заголовок и установить соединение между предыдущим заголовком. strong> и новый заголовок со свойством .next. Но как удалить последний узел? Мы должны назначить узел до узла, который мы удаляем, как новый конец. Поскольку мы используем односвязный список, указатель на последний узел отсутствует (как в случае с двусвязными списками). Это означает, что единственный способ, которым мы можем получить доступ к узлу, предшествующему узлу, который мы удаляем, — это перебирать узлы, начиная с head.

Пройдемся по коду:

  • если список пуст, возвратите nil
  • если в списке только один узел, pop() отключает его
  • цикл while перебирает список со свойством .next
  • после завершения цикла while установите для свойства .next значение nil, назначьте новый хвост и верните удаляемый узел
  • когда мы используем removeLast() в первый раз, head не равен нулю, потому что мы передали три значения ранее.
  • кроме того, head.next не равен nil
  • мы создаем две переменные: newTail и currentNode. Как следует из их названий, мы используем один для назначения нового хвоста, а currentNode — это узел, который будет удален и возвращен функцией.
  • newTail и currentNode оба получают значение узла head, которое имеет значение 1 (помните, что мы итерируем с начала списка)
  • цикл while будет выполняться до тех пор, пока currentNode.next не равен нулю
  • во время первой итерации цикла currentNode.next равно 2, поэтому вводится внутренний блок цикла
  • подумайте о том, чего мы хотим достичь: наша цель — иметь доступ как к 1) узлу перед последним, так и к 2) последнему узлу. Первый будет новый хвост, а последний будет возвращен. Этого можно добиться путем реализации задержки между currentNode и newTail. Таким образом, логика в цикле while должна установить currentNode (то, что будет удалено) как один узел после newTail (что будет новым хвостом). , ну)
  • в первой итерации для newTail устанавливается значение 1, а для currentNode — 2. Первая итерация завершается.
  • currentNode.next равно 3, поэтому мы вводим блок while
  • newTail теперь равен 2
  • currentNode теперь равен 3. Вторая итерация завершена.
  • currentNode.next равен нулю, поэтому мы выходим из цикла
  • newTail.next имеет значение nil. Делая это, мы удаляем последний узел
prior 1 -> 2 -> 3
now   1 -> 2
  • tail установлен на 2
  • currentNode(3) возвращается

узел(в индексе: Int) -> Узел‹T›?

Этот метод возвращает узел с заданным индексом.

  • Оператор guard защищает метод от отрицательных индексов.
  • точно так же, как мы повторялись с начала списка с помощью метода removeLast(), мы должны сделать то же самое здесь. Вот почему head хранится в current, который будет использоваться в цикле while.
  • спросите себя, как бы вы вернули 736-й узел в гипотетическом гигантском связанном списке (или любой узел, кроме первого и последнего). Опять же, нет никаких индексов, которые можно было бы использовать. Это можно сделать, увеличивая переменную каждый раз, когда мы передаем узел в списке. Мы делаем это с помощью current?.next (так же, как removeLast())
  • условие разрыва цикла while обеспечивает выход из цикла после достижения желаемого индекса
linkedList.node(at: 1)
  • Оператор guard передается
  • head равен 1 и хранится в переменной current.
  • счетчик начинается с 0
  • условие while истинно, поэтому его блок кода выполняется (current?.next имеет значение и 0 ‹ 1)
  • чтобы просмотреть список, мы делаем то же самое, что и раньше, с removeLast(): мы сохраняем следующийузел текущего, который равно 2 в текущем
  • counter равен 1, первая итерация завершена
  • current?.next равен 3, а счетчик равен индексу (оба 1), поэтому пока условие false и мы выходим из цикла
  • Возвращается current, то есть узел со значением 2. На всякий случай мы печатаем значение узла перед возвратом.

удалить(по индексу: Int) -> Узел‹T›?

Мы используем ту же стратегию, что и с removeLast() (есть некоторые отличия, о которых я расскажу позже):

  • с current.next мы можем перебирать список
  • подсчитав, в каком узле мы сейчас находимся, мы можем выйти из цикла while, когда доберемся до нужного узла
  • мы реализуем отставание в блоке кода while
  • если последний или первый узлы удалены, мы просто возвращаем removeLast() и pop()

Что происходит, когда мы удаляем узел с индексом 1?

  • Оператор guard и условие if пропускаются
  • текущее равно 1
  • Условие пока равно true, поэтому вводится блок кода
  • предыдущий имеет значение 1
  • current установлен на 2
  • счетчик увеличивается до 1
  • первая итерация завершена
  • при втором запуске условие while равно false, поскольку counter равно index (оба 1), поэтому цикл while выходит из строя
  • мы проверяем, есть ли следующий узел. Если нет, это означает, что цель состоит в том, чтобы удалить последний узел списка, поэтому мы можем использовать наш метод removeLast()
  • иначе, если нет следующего узла, мы делаем previous?.next = current?.next
Prior to previous?.next = current?.next, our list looked like this:
1           ->           2           ->      3
previous   .next       current       .next
Now, it looks like this:
1           ->           3

Проще говоря, мы говорим: «Привет, предыдущий узел (который равен 1). Ты здесь? Если да, задайте для следующего свойства (которое равно 2 и имеет тип Node‹T›?) значение свойства next (которое равно 3) текущего узла (если оно существует)». Вот как мы переходим от 1 -> 2 -> 3 – 1 – 3.

вставить (по индексу: Int, значение: T)

Мы можем использовать многое из того, чему научились здесь. С одним отличием — я хочу показать, что вам не нужно придерживаться циклов while.

Давайте поработаем с кодом:

  • guard пропускается
  • создать новый узел со значением, которое было передано в функцию
  • если пропускается (индекс равен 1)
  • предыдущий равен 1
  • текущее равно 1
  • цикл for введен, потому что 0..‹1
  • предыдущий равен 1
  • current равен 3 (поскольку current?.next равен 3, список выглядит так 1 -> 3 до того, как мы использовали insert ())
  • первая итерация завершена
  • цикл for равен false, цикл разрывается
  • previous?.next равно 3, которое установлено в next свойство newNode (ранее оно было nil) . Новый узел равен 2, поэтому теперь newNode.next дает нам 2 -> 3.
  • если бы свойство next newNode было равно нулю, мы бы вошли в блок кода и использовали наш метод append()
  • в строке 18 свойство следующий узла предыдущий установлено равным 2. У узла предыдущий значение равно 1. , Это означает, что previous?.next = newNode дает нам 1 -› 2.
  • конечный результат: 1 -› 2 -› 3

обеспечить регресс()

Поздравляю с тем, что зашел так далеко в блоге, умник. Теперь давайте убьем последнего босса — перевернув односвязный список!

Некоторые предостережения:

  • на этот раз мы используем 3 переменные вместо 2: предыдущая, текущая и следующая. Почему? Предположим, мы хотим поменять местами 1 -> 2 -> 3. Назовем их previousNode, currentNode и nextNode. Конечным продуктом должно быть 3 -> 2 -> 1. Посмотрите на второй узел, 2. Перед реверсированием предыдущий узел (1) следующий указывало на 2, а свойство текущего узла (2) следующего указывало на 3. После реверсирования следующего узла (3) следующий указывает на 2, а свойство текущего узла (2) следующий указывает на 1. Таким образом, чтобы обратить связанный список, мы должны для изменения свойств next узлов при их повторении.
  • хвост становится головой, а голова становится хвостом

Давайте пройдемся по коду: (на примере 1 -> 2 -> 3)

  • в строке 3 мы устанавливаем tail со значением head
  • мы создаем 3 переменные: previousNode, currentNode, nextNode
  • previousNode равен nil, currentNode равен 1, а nextNode равен 2.
  • условие while истинно, так как nextNode не равно нулю, поэтому мы вводим блок кода
  • previous равно nil, поэтому строка 8 дает 1 → nil
  • previousNode теперь равен 1
  • currentNode теперь равен 2
  • nextNode теперь равен 3
  • как становится очевидным, мы сдвигаем наши переменные на один узел вверх по списку
  • первая итерация завершена
  • Условие пока по-прежнему истинно, потому что nextNode не равно nil (это 3)
  • поскольку previousNode равен 1, а currentNode равен 2, строка 8 даст 2 -> 1
  • previousNode теперь равен 2
  • currentNode теперь равно 3
  • nextNode теперь ноль
  • вторая итерация завершена
  • Условие пока равно false, потому что nextNode равно nil
  • строка 13 дает 3 -> 2
  • мы назначаем новую голову
  • конечный результат: 3 -> 2 -> 1

Я надеюсь, что смог помочь вам. Если у вас есть какие-либо вопросы, просто напишите мне в твиттере: ozgunyx