Читайте также:
|
Иногда возникает необходимость организовать эффективное перемещение по списку, как в прямом, так и в обратном направлениях; или по заданному элементу нужно быстро найти предшествующий ему и последующий элементы. В этих ситуациях можно дать каждой ячейке указатели и на следующие и на предыдущие ячейки списка, т.е. организовать дважды связный список. На рис. 10 приведен такой список.
Рис. 10 – Дважды связный список
Важным преимуществом является то, что можно использовать указатель ячейки, содержащей i -й элемент, для определения i -й позиции вместо использования указателя предшествующей ячейки. Однако при этом появляются дополнительные указатели и, следовательно, удлиняются некоторые процедуры. Ниже приведен код объявления дважды связного списка.
На рис. 11 приведены процедура и схема удаления элемента из дважды связного списка. Ниже приведена процедура удаления.
Рис. 11 – Удаление элемента из дважды связного списка
Здесь предполагается, что удаляемая ячейка не является ни первой, ни последней в списке. Сплошными линиями показаны указатели до удаления, а пунктирными – после удаления элемента. Сначала с помощью указателя поля previous определяется положение предыдущей ячейки. Затем в поле next этой ячейки устанавливается указатель на ячейку, предшествующую позиции р. Таким образом, ячейка в позиции р исключается из цепочек указателей и при необходимости может быть использована повторно.
Дата добавления: 2015-07-16; просмотров: 85 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Сравнение различных реализаций списков | | | Реализация очереди с помощью указателей |