Добавить, добавить в начало, удалить, найти и заменить

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

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

Класс узла содержит: значение и следующий

Класс связанного списка содержит: голову и хвост

Мы соответствуем «протоколу Equatable» в обоих классах.
Протокол Equatable - имеет ограничение, при котором вы можете проверять равенство между объектами одного типа. Таким образом, позволяет нам выполнять операцию == для нашего типа T и для наших узлов !!

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

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

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

  • Вставить в начало (вставить в начало)
    Время выполнения: O (1)

  1. Создайте новый узел из нашего входного значения
  2. Если наш связанный список пуст, назначьте заголовок и хвост нашему новому узлу.
  3. Если наш связанный список не пуст:
    назначьте следующий указатель нашего нового узла на self.head
    и обновите указатель заголовка, чтобы он стал нашим новым узлом
  • Добавить в конец
    Время выполнения: O (1)

  1. Создайте новый узел из нашего входного значения
  2. Если наш связанный список пуст, назначьте заголовок и хвост нашему новому узлу.
  3. Если наш связанный список не пуст:
    установите следующий указатель хвоста на новый узел
    и обновите указатель хвоста, чтобы он стал нашим новым узлом
  • Удалите значение
    Время выполнения: O (n), где n - количество узлов, через которые нам нужно пройти

В приведенном ниже коде мы проверяем следующие случаи, когда мы хотим удалить узел:
case1: это хвост
case2: это голова
case3: находится между узлами
case4: единственный узел (и голова, и хвост)

  1. Создайте переменные, чтобы у нас был доступ к текущему узлу и предыдущему узлу
  2. Просматривайте связанные списки, пока текущий не равен нулю
  3. Найден узел, равный нашему входному значению !!
  4. Проверка предыдущего узла имеет значение
  5. Удаление узла в конце связанного списка
    установка self.tail в качестве предыдущего узла
  6. Измените указатель предыдущей следующей на текущую следующую
  7. В противном случае предыдущий узел равен нулю. И мы удаляем узел в конце связанного списка.
    установите self.tail в качестве предыдущего узла
  8. Изменение self.head на следующий узел текущего
  9. Мы еще не нашли элемент, поэтому продолжаем перебирать и проверять следующий узел.
  • Длина
    Время выполнения: O (n), где n - количество узлов в связанном списке.
    Однако время выполнения может быть O (1), если у нас есть другое значение в классе связанного списка. который ведет учет элементов по мере того, как мы вставляем / добавляем или удаляем.

  1. Если связанный список пуст, вернуть 0 и выйти из функции
  2. Создать переменные для счетчика и текущего узла
  3. Просмотрите связанный список, пока curr не равен нулю
  4. Увеличить счетчик на 1 и проверить следующий узел
  5. Верните счет!
  • Последний элемент
    Время выполнения: O (1)

Возвращает последний элемент в нашем связанном списке.

  • Найдите
    Время выполнения: O (n), где n - количество узлов, через которые мы прошли.

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

  • Замените старый элемент новым элементом
    Время выполнения: O (n), где n - количество узлов, через которые мы проходим.

  1. Создайте переменную для подсчета текущего узла
  2. Просмотрите связанный список, пока curr не равен нулю
  3. Мы нашли узел! Поэтому замените значение curr новым входным значением и вернитесь из функции
  4. Узел еще не найден, поэтому мы зацикливаемся, чтобы проверить следующий узел

Тестирование

Теперь, когда у нас записан и функционирует наш базовый класс, давайте продолжим и проверим, действительно ли эти методы работают 🤔🤔

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

let ll = LinkedList<String>()
ll.append(value: "apple")
ll.append(value: "butter")
ll.append(value: "cinnamon")

Если мы напишем оператор печати, проверяющий голову и хвост, он должен распечатать «яблоко» и «корицу» соответственно.

print(ll.head?.value ?? "no head found")   // apple
print(ll.tail?.value ?? "no tail found")   // cinnamon

Удалить
Удаление чего-либо из начала связанного списка должно изменить указатель заголовка…

ll.remove(value: "apple")
print(ll.head?.value ?? "nothing found")    // butter
print(ll.tail?.value ?? "no tail found")    // cinnamon

Заменить
Заменяет старое значение на наше новое и должно распечатать новое значение.

ll.replace(old: "cinnamon", new: "chocolate")
print(ll.tail?.value ?? "no tail found")    // chocolate

Это лишь некоторые методы класса связанного списка, реализованного в Swift. Попробуйте их на игровой площадке Swift и увидите волшебство! Ѻ → Ѻ → Ѻ
Я уверен, что есть другие методы, и хотел бы, чтобы кто-нибудь поделился ими ниже😃🤓

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