Связанный список — это структура данных, состоящая из последовательности узлов, содержащих значение и ссылку (ссылку) на следующий узел.
Обозначение Big-O
access: O(n) search: O(n) insert: O(1) delete: O(1)
Доступ и поиск довольно медленные, так как узлы связаны один за другим, в отличие от массивов, где есть индексы или хэш-таблицы, где есть ключи.
Вставка и удаление выполняются быстро, как в начале, так и в конце.
Односвязный и двусвязный список
Односвязный список содержит узлы, которые имеют только одну ссылку (следующий узел), а двусвязный список содержит ссылку в противоположном направлении.
Это позволяет разработчикам настраивать структуру данных в зависимости от того, что ценнее, время или память.
Допустим, вы хотите вставить данные в 7-й индекс в связанных списках из 8 элементов. Для односвязного списка у вас нет другого выбора, кроме как пройти по списку от 0-го индекса до 7-го индекса, так как есть только ссылка на следующий узел.
Двусвязные списки позволяют мне перемещаться в обратном направлении, делая временную сложность O(n)/2. Понятие Big-O упростит это до O(n), но в таком случае использование двусвязного списка имеет явное преимущество. Но сложность пространства увеличивается, поскольку каждому узлу необходимо хранить дополнительную переменную.
Вот мой пользовательский односвязный список в Javascript.
