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

Обязательно ознакомьтесь с моей статьей об односвязном списке здесь, чтобы найти предыдущие ссылки! 😃 Здесь я подробно расскажу, как создать класс односвязного списка, а также класс узла, чтобы начать реализацию в нем различных методов.

Чем двусвязные списки отличаются от односвязных списков? Дважды имеет предыдущий указатель, указывающий на его предыдущий узел! Это может быть выгодно в зависимости от того, какие действия мы хотим выполнить с нашей структурой данных, о чем мы поговорим далее в этой статье. ✔️

Оглавление

  1. Плюсы и минусы двусвязного списка
  2. Создание класса узла с помощью универсальных шаблонов
  3. Создание класса LinkedList с помощью универсальных шаблонов
  4. Методы в классе Doubly LinkedList:
    • Добавить
    • Добавить
    • Элементы
    • Получить узел по индексу
    • Вставить по индексу
  5. Примеры использования двусвязного списка в реальной жизни
  6. Растянуть вызовы!
    • Удалить все узлы в связанном списке
    • Вставить узел после определенного узла
    • Распечатать связанный список в порядке
    • Распечатать связанный список в обратном порядке.

Плюсы и минусы двусвязного списка

Класс узла

Как вы можете видеть в этом классе узла выше, каждый узел содержит ровно 3 переменные; значение (данные), next, которое будет содержать узел после него, и prev, которое будет содержать узел перед ним.

Дженерики

Универсальный код позволяет вам писать гибкие, многократно используемые функции и типы, которые могут работать с любым типом в соответствии с определенными вами требованиями. - Swift Docs

Типы Swift Array и Dictionary являются общими коллекциями.
В нашем случае мы также хотели бы создать наш класс связанного списка с использованием общих типов, чтобы мы могли создавать узлы с любым типом, который мы хотим, например целыми числами, числами с плавающей запятой, двойными числами, строками, кортежами , или даже наши собственные модели!

Класс связанного списка

Этот класс связанного списка будет содержать свойства головы, хвоста и размера. Это значение size будет полезно, когда мы хотим найти длину всего связанного списка.

Теперь, когда у нас есть основа, мы можем приступить к реализации различных методов в нашем классе LinkedList👇🏼👇🏼👇🏼

Методы в классе DoublyLinkedList

Я настоятельно рекомендую попробовать кодировать эти функции или записать псевдокод, прежде чем искать решения !! 📝 ✍🏼
Не забывайте учитывать как следующие, так и предыдущие указатели при реализации следующих методов.

  • Добавить

Добавление нового элемента в конец связанного списка.

Здесь будет использоваться и обновляться self.size!

  1. Создайте новый узел из значения, переданного в параметре
  2. Создайте оператор защиты, чтобы убедиться, что значение заголовка не равно нулю, чтобы продолжить строки после 12.
  3. Если заголовок равен нулю, что означает, что наш связанный список пуст, мы инициализируем заголовок и хвост как новый узел, созданный в строке 3.
  4. Теперь, когда мы уверены, что наш связанный список не пустой, мы знаем, что есть хвостовое значение. Поэтому мы устанавливаем следующий указатель хвоста на newNode. Мы также даем newNode предыдущий указатель на наш хвост. Наконец, нужно обновить хвост, чтобы он стал newNode.
  5. Увеличиваем наш размер на 1, так как мы только что добавили нового члена в наше семейство списков. 😲😄
  • Подготовить

Добавление нового элемента в начало связанного списка.

  1. Создайте новый узел из параметра значения
  2. Использование оператора guard, чтобы убедиться, что есть значение заголовка, иначе будут выполнены строки 8–11.
  3. Инициализируем нашу голову и хвост как newNode без изменения или добавления каких-либо указателей.
  4. Теперь, когда регистр связанного списка не пуст, мы продолжаем и делаем следующее:
    Устанавливаем предыдущий указатель заголовка на newNode
    Предоставление newNode следующий указатель на нашу голову
    И, наконец, обновление головы до нашего первого узла (newNode)
  5. Увеличиваем наш размер на 1, так как мы только что добавили нового члена в наше семейство списков. 😲😄
  • Предметы

Возвращение всех элементов связанного списка в виде массива значений, отсортированных от начала к концу.

  1. Если связанный список пуст, мы возвращаем пустой массив
  2. Создайте пустой массив, в который мы будем добавлять все значения узлов
  3. Прокрутите связанный список, начиная с self.head.
    В цикле while мы сначала добавляем значение текущего узла, а затем обновляем curr, чтобы он стал следующим узлом.
  4. Как только мы дойдем до конца связанного списка, мы сможем вернуть массив, который теперь заполнен всеми значениями узлов в связанном списке!
  • Вставить по индексу:

Вставка узла в заданную позицию, в которую мы хотели бы вставить его.

Не пугайтесь этого огромного фрагмента кода! Мы вместе пройдем через это шаг за шагом и посмотрим, как все это волшебство происходит.

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

⚠️Прежде чем переходить к шагам 2, 3 и 4, мы должны знать, что есть 3 варианта того, куда мы хотим вставить узел.
- Вставка спереди: изменение self.head
- Вставка в конце: изменение self.tail
- Вставка между двумя узлами: изменение следующего и предыдущего ссылочных указателей.
Мы хотелось бы проверить эти случаи отдельно, чтобы наш код был более эффективным!

2. index == 0 означает, что мы вставляем перед нашим списком.
Вот что происходит в методе prepend. (Порядок имеет значение! ☝🏼)
- Установить предыдущий указатель текущей головы на наш newNode
- Установить следующий указатель нашего newNode на self.head. Нам не нужно устанавливать предыдущий указатель newNode, поскольку он по умолчанию равен nil
- Измените заголовок на наш newNode !!

3. index == self.size означает, что мы вставляем в конец нашего списка.
Вот что происходит в методе добавления. (Порядок имеет значение! ☝🏼)
- Устанавливаем следующий указатель текущего хвоста на наш newNode
- Устанавливаем предыдущий указатель нашего newNode на текущий хвост
- затем мы меняем хвост!

4. index находится где-то между 2 узлами, что означает, что нам придется перемещаться по связанному списку, пока мы не дойдем до желаемого индекса.
- 1: Создать новый узел с желаемым значением
- 2: Цикл через связанный список, обновляя наш узел curr, чтобы он стал узлом прямо в индексе, который мы хотели бы вставить newNode
- 3: Присоединение нашего текущего предыдущего указателя к следующему на newNode.
А также прикрепив предыдущий указатель нашего newNode к предыдущему нашему текущему узлу.
Теперь мы можем переназначить предыдущий указатель current на newNode.
И следующий указатель нашего newNode на текущий узел.
- 4: Увеличение self.size на 1. И мы только делаем этот шаг в предложении else, поскольку методы append и prepend уже охватывают приращение.

  • Получить узел по индексу

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

1. Проверяет, находится ли индекс ввода в диапазоне от 0 до self.size. В противном случае мы вернем nil, поскольку в этом недопустимом индексе нет значений.
2. Начнем с self.head и пройдемся по связанному списку. Если, скажем, индекс был равен 1, то мы обновляем «curr» до следующего узла 1 раз. Точно так же, если индекс был равен 0, код вообще не будет выполнять цикл for (0 раз).
3. Наконец, мы возвращаем значение этого текущего узла, потому что оно правильно соответствует индексу, который мы ищем. для.

Примеры использования двусвязных списков в реальной жизни

• Создание музыкального плейлиста 🎶🎵🎶. Эта статья даже дает вам пример кода о том, как реализовать свой собственный класс!
• Рисование из колоды карт. Узлы могут представлять ранг и цвет одной карты.
• И, наконец, функция отмены и повтора в браузере !! Здесь вы можете перевернуть узел, чтобы перейти на предыдущую страницу.

Методы упражнений на растяжку

  1. deleteAll (): удаляет все узлы в связанном списке
  2. insertAfter (_ value: T, after: T): принимает значение, которое вы хотите вставить, и значение узла, который вы хотите вставить сразу после
  3. listForward (): распечатывает значения узла связанного списка спереди назад
  4. listBackward (): распечатывает значения узла связанного списка снизу вверх

Я надеюсь, что вы нашли ценность в этом сообщении в блоге, и настоятельно рекомендую вам попробовать реализовать все эти методы на игровой площадке Swift.

Спасибо, что прочитали это сообщение в блоге!

Если у вас есть вопросы или комментарии, обращайтесь ко мне. И не забудьте дать этой статье несколько аплодисментов! 👏🏼 * до 50x * 👏🏼, если вы сочли это полезным.