Разница между односвязным списком и двусвязным списком

Единственно связанный список против двусвязного списка

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

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

Каждый элемент в односвязном списке имеет два поля, как показано на рисунке 1. Поле данных содержит фактические сохраненные данные, а следующее поле содержит ссылку на следующий элемент в цепочке. Первый элемент связанного списка хранится как заголовок связанного списка..

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

Двусвязный список

Каждый элемент в двусвязном списке имеет три поля, как показано на рисунке 3. Как и в односвязном списке, поле данных содержит фактические сохраненные данные, а следующее поле содержит ссылку на следующий элемент в цепочке. Кроме того, в предыдущем поле содержится ссылка на предыдущий элемент в цепочке. Первый элемент связанного списка хранится как заголовок связанного списка..

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

В чем разница между односвязным списком и двусвязным списком?

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