Разница между двусторонними связанными списками и двусвязным списком
Я не понимаю разницы между двунаправленным и двусвязным списком.
В чем главное различие между ними?
6 ответов
В двусвязном списке каждый узел имеет два указателя. Один к его следующему узлу и другой к его предыдущему узлу.
В двустороннем связанном списке каждый узел имеет только один указатель, который указывает на его следующий узел. Его отличие от одностороннего связанного списка состоит в том, что вместо одного "головного" узла он содержит два указателя такого типа ("первый" и "последний"), поэтому кто-то может вставлять элементы в список с обоих концов Это.
(Последнее изображение не так ясно, но оно улавливает точку с двух сторон.)
Двусторонний список похож на обычный связанный список, но у него есть одна дополнительная особенность: ссылка на последнюю ссылку, а также на первую. В двусвязном списке каждая ссылка имеет две ссылки на другие ссылки вместо одной. Первая - это следующая ссылка, как в обычных списках. Второе к предыдущей ссылке.
Двусвязный список - это список, в котором элементы имеют указатели на элементы до и после в списке.
Двусторонний список от моего понимания такой же, как deque. Это очередь, из которой вы можете добавлять и удалять элементы как сверху, так и снизу.
Одиночная связь - это одностороннее направление, и она использует меньше памяти, а сложность вставки составляет O(n). Хотя двойное связывание является двусторонним направлением (следующим и предыдущим), оно использует больше памяти, чем единый список, а сложность вставки и удаления составляет O(n).
Поскольку двусторонний связанный список содержит только ссылку на следующий узел в узле, он больше напоминает односвязный список. Однако он отличается от отдельного списка, поскольку список содержит указатели как на первый, так и на последний узлы. Кроме того, новые узлы могут быть добавлены с обоих концов.
Узлы двусвязного списка содержат ссылки как на следующий, так и на предыдущий узел.
двусвязный список:
- узел содержит ссылки на следующий и предыдущий узел.
- Можно перемещаться вперед и назад по связанному списку.
двусторонний связанный список:
- узел содержит ссылки на следующий узел.
- Имейте два указателя для первого и последнего узла.
- Невозможно перемещаться по списку вперед и назад.
В обоих списках есть два указателя спереди и сзади. Но двусторонний список не может двигаться назад, только вперед, в то время как двусвязный список может перемещаться как вперед, так и назад.