Что такое односвязный список?

Односвязный список состоит из следующих свойств:

  • Это линейная структура данных, состоящая из узлов, и каждый узел содержит поле данных и ссылку на следующий узел.
  • Последний узел имеет значение null.
  • Элементы не хранятся в непрерывном месте, они связаны с помощью указателей / ссылок.
  • Первая запись связанного списка называется заголовком, если список пуст, заголовок будет пустой ссылкой.
  • Последняя запись в списке называется хвостом.
  • Следующий указатель последнего узла - ПУСТО (NULL), поэтому, если следующий текущий узел - ПУСТО (NULL), мы достигли конца связанного списка.

Мы будем выполнять следующие операции со связанным списком:

  • Add-To-Front: чтобы добавить узел в начало списка.
  • Добавить в конец: чтобы добавить узел в конец списка.
  • Remove-Front: удалить узел спереди.
  • Remove-End: удалить узел с конца.
  • Печать: чтобы распечатать все узлы.

Перейдем к реализации.

Чтобы добавить узел в начало списка:

Подход:

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

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

Код:

Сначала мы создадим два класса: один для узла и один для списка.

Теперь мы будем реализовывать наши операции со списком внутри класса списка:

Ниже показано, как добавить узел на передний план:

Сложность по времени для добавления на передний план составляет O (1), потому что нам нужно только обновить заголовок, чтобы он стал новым узлом, а следующий указатель - существующим заголовком. (Перемещение на одно место).

Добавление узла в конец списка; Подход:

Есть два способа добавить в конец списка:

Метод 1. Если у нас есть указатель на хвост, нам просто нужно обновить следующую ссылку хвоста, чтобы она была новым узлом, и это будет выполнено с временной сложностью O (1).

Способ 2:

Если у нас нет указателя на хвост, нам нужно будет пройти по списку, пока мы не найдем второй последний узел, а затем мы устанавливаем следующую ссылку как новый узел. Это будет выполнено на сложности O (n).

Подход для снятия узла спереди:

Поскольку у нас есть ссылка на указатель головы, мы можем установить текущую голову как следующий узел. Это будет выполнено в O (1).

Подход к снятию с конца:

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

Поскольку односвязный список не имеет предыдущего указателя, следовательно, нам нужно перемещаться по списку, пока мы не найдем второй последний узел, а затем мы устанавливаем следующий указатель так, чтобы он указывал на null.

Подход к распечатке списка:

Каждый узел может содержать поле данных, которое может быть любым типом данных, поэтому здесь мы будем предполагать, что каждый узел состоит из данных.
Чтобы распечатать данные каждого узла, нам нужно просмотреть список и console.log каждого узла data, пока мы просматриваем список.

Подобно удалению конца списка, мы объявим текущую переменную, чтобы отслеживать текущую голову, поскольку голова не является последним узлом в списке.

Вот и все! Мы успешно реализовали базовые операции с одинарным списком ссылок.

В следующем блоге я рассмотрю двусвязный список.

Спасибо за прочтение.