javascript-algorithms
Двусвязный список
Двусвязный список — связная структура данных в информатике, состоящая из набора последовательно связанных записей, называемых узлами. Каждый узел содержит два поля, называемых ссылками, которые указывают на предыдущий и последующий элементы в последовательности узлов. Ссылка на предыдущий элемент корневого узла ссылка на последующий элемент последнего узла, указывают на некого рода прерыватель, обычно сторожевой узел или null, для облегчения обхода списка. Если в списке только один сторожевой узел, тогда список циклически связана через него. Двусвязный список можно представить, как два связных списка, которые образованны из одних и тех же данных, но расположенных в противоположном порядке.
Две ссылки позволяют обходить список в обоих направлениях. Добавление и удаление узла в двусвязном списке требует изменения большего количества ссылок, чем аналогичные операции в связном списке. Однако данные операции проще и потенциально более эффективны (для некорневых узлов) - при обходе не нужно следить за предыдущим узлом или повторно обходить список в поиске предыдущего узла, плюс его ссылка может быть изменена.
Псевдокод основных операций
Вставка
Add(value)
Pre: value - добавляемое значение
Post: value помещено в конец списка
n ← node(value)
if head = ø
head ← n
tail ← n
else
n.previous ← tail
tail.next ← n
tail ← n
end if
end Add
Удаление
Remove(head, value)
Pre: head - первый узел в списке
value - значение, которое следует удалить
Post: true - value удалено из списка, иначе false
if head = ø
return false
end if
if value = head.value
if head = tail
head ← ø
tail ← ø
else
head ← head.next
head.previous ← ø
end if
return true
end if
n ← head.next
while n = ø and value = n.value
n ← n.next
end while
if n = tail
tail ← tail.previous
tail.next ← ø
return true
else if n = ø
n.previous.next ← n.next
n.next.previous ← n.previous
return true
end if
return false
end Remove
Обратный обход
ReverseTraversal(tail)
Pre: tail - конечный элемент обходимого списка
Post: элементы списка пройдены в обратном порядке
n ← tail
while n = ø
yield n.value
n ← n.previous
end while
end Reverse Traversal
Сложность
Временная сложность
| Чтение | Поиск | Вставка | Удаление |
|---|---|---|---|
| O(n) | O(n) | O(1) | O(n) |
Пространственная сложность
O(n)