На этом занятии мы познакомимся с новой
структурой данных – двусвязными списками. Если вы хорошо понимаете, как
работает односвязный список, то вся основа у вас уже есть, так как двусвязный
список – это все тот же односвязный, только каждый элемент имеет ссылки next и prev на следующий и
предыдущий элементы. Во всем остальном он идентичен односвязному.
Также мы имеем здесь
два указателя: head – на первый элемент списка; tail – на последний.
В результате, можно очень быстро обрабатывать первые и последние элементы,
например, делать добавление элементов в начало списка или вконец, а также
удалять их. У граничных объектов указатель prev и next принимают
значения NULL. Так можно
определять первый и последний элементы списка. (Помимо значения NULL можно
использовать любую другую предопределенную величину, например, None если программа
пишется на Python).
Добавление элементов в начало и конец двусвязного списка
Я думаю, что
структура двухсвязного списка вам понятна. Давайте теперь рассмотрим базовые
операции работы с этой структурой данных. И начнем с операции добавления
элементов в начало и конец списка.
Предположим, что в списке два объекта и
мы хотим добавить новый в его конец:
Вначале
создается новый элемент в памяти компьютера, на который ведет временная ссылка ptr. Затем, ссылка next последнего
объекта списка должна вести на этот новый объект. Для этого достаточно
присвоить ссылке адрес нового элемента:
tail.next = ptr
Далее необходимо
ссылке prev нового элемента
присвоить адрес последнего элемента списка:
ptr.prev = tail
И последнее,
указатель tail переместить на
новый последний элемент списка:
tail = ptr
Скорость работы
этой операции составляет O(1) и часто реализуется командой push_back().
По аналогии выполняется
добавление нового элемента в начало двусвязного списка. Создается новый объект,
на который ссылается указатель ptr. Затем, ссылка prev первого объекта
должна вести на добавляемый элемент:
head.prev = ptr
Ссылка next добавляемого
элемента должна вести на объект head:
ptr.next = head
И указатель head перемещаем на
объект ptr:
head = ptr
Вот так,
достаточно просто выполняется добавление нового элемента в начало двусвязного
списка. Скорость выполнения этой операции с точки зрения О большого составляет O(1) и часто
реализуется командой push_front().
Доступ к произвольному элементу двусвязного списка
Давайте теперь
посмотрим, как осуществляется доступ к произвольному элементу в двусвязном
списке. Предположим, имеется список из нескольких элементов и указатели head и tail, которые
ссылаются на первый и последний элементы этого списка. Затем, создадим еще один
временный указатель ptr, который пусть изначально ссылается на первый
элемент:
То есть, через
указатель ptr мы сейчас
обращаемся к первому элементу и можем, например, прочитать его данные командой:
value = ptr.data
Чтобы перейти к
следующему второму элементу необходимо переместить указатель ptr на него.
Сделать это можно очень просто с помощью указателя next первого объекта:
ptr = ptr.next
Получаем доступ
ко второму элементу списка. Можем записывать и считывать из него данные:
ptr.data = new_value
По аналогии, для
перехода к следующему третьему элементу, снова выполняем команду:
ptr = ptr.next
и указатель ptr ссылается на
третий элемент. И так можно проходить по всем элементам списка до последнего.
С точки зрения О
большого объем вычислений для перехода к произвольному k-му элементу
списка составляет O(n), где n – общее число
элементов в списке. И в этом двусвязный список проигрывает массивам, у которых
скорость доступа к произвольному элементу O(1).
Но у двусвязных
списков есть важное преимущество по сравнению с односвязными списками: мы можем
перемещаться по элементам в обе стороны (и вправо и влево). Когда выполняется
команда:
ptr = ptr.next
то осуществляется
переход вправо. А с помощью команды:
ptr = ptr.prev
влево. В
частности, это несколько упрощает некоторые операции, например, удаление
промежуточных элементов.
Вставка элемента в двусвязный список
Но сначала мы
рассмотрим вставку нового элемента в произвольную позицию двусвязного списка. Предположим,
в списке имеется три элемента и мы хотим вставить новый элемент после второго,
на который ссылается указатель left:
Затем, создается
новый объект в памяти устройства, на который ссылается временный указатель ptr. Все что нам
осталось – это настроить связи между соседними элементами относительно
вставляемого. Для этого создадим еще один временный указатель right, который будет
ссылаться на следующий элемент после left:
right = left.next
В результате мы
имеем ссылки left и right на соседние
объекты относительно вставляемого.
Сформируем новые
связи между элементами. Первые две связи между объектом left и ptr, очевидно, создаются
командами:
left.next = ptr
ptr.prev = left
А следующие две
(между right и ptr) командами:
right.prev = ptr
ptr.next = right
Все, новый
элемент вставлен в двусвязный список после объекта left. Разумеется, в
реальных программах нужно дополнительно проверять, чтобы объекты left и right существовали,
прежде чем обращаться к указателям next и prev этих объектов.
Вычислительная
сложность непосредственно вставки нового элемента, составляет O(1). Но здесь
нужно учитывать, что прежде необходимо получить ссылку на объект left, после которого
вставляется новый элемент. А эта операция выполняется за O(n). Поэтому, в
общем случае, вставка нового элемента в двусвязный список имеет сложность O(n). И часто
реализуется командой insert().
Удаление промежуточных элементов
Следующая
операция – удаление промежуточных элементов. Предположим, имеется список из
четырех элементов и мы хотим удалить третий. На него ведет указатель node:
Первым шагом нам
нужно получить ссылки на соседние объекты относительно удаляемого. Это можно
сделать командами:
left = node.prev
right = node.next
Затем,
освободить память, занимаемую объектом node. Например, в C++ это делается
командой:
delete node
В некоторых
других языках, таких как Python, эту операцию берет на себя
сборщик мусора, когда на объект не ведет никаких внешних ссылок.
Осталось только
изменить связи у объектов left и right (связать их
между собой). Делается это очень просто. Ссылка next объекта left должна вести на
объект right:
left.next
= right
А ссылка prev объекта right на left:
right.prev = left
Все, связи
настроены и удаление промежуточного элемента выполнено. Вычислительная
сложность самой операции удаления составляет O(1). С учетом
поиска удаляемого элемента – O(n). А сама
команда часто называется erase().
Удаление первого и последнего элементов
В заключение
этого занятия отдельно рассмотрим алгоритмы удаления первого и последнего
элемента двусвязного списка.
Предположим, в
списке имеется четыре элемента и мы собираемся удалить первый. Тогда создадим
временный указатель ptr, который будет ссылаться на следующий (второй)
элемент:
ptr = head.next
И у этого
второго элемента указатель prev приравняем
значению NULL:
ptr.prev = NULL
Затем, освободим
память, занимаемую первым элементом head. В С++ это
делается с помощью оператора delete:
delete head
И переместим
указатель head на второй
элемент, который теперь стал первым:
head = ptr
Вот общий
принцип удаления первого элемента в двусвязном списке. Вычислительная сложность
этого алгоритма составляет O(1) и часто реализуется командой pop_front().
По аналогии
выполняется удаление последнего элемента. Вначале формируем временный указатель
ptr на предыдущий
объект списка:
ptr = tail.prev
Затем, указатель
next объекта ptr приравниваем
значению NULL:
ptr.next
= NULL
Освобождаем
память из под последнего элемента:
delete tail
И устанавливаем
указатель tail на новый
последний элемент:
tail = ptr
Вычислительная
сложность этого алгоритма составляет O(1) и часто реализуется командой pop_back().
Заключение
Подведем общие
итоги этого занятия. Самые быстрые операции – это добавление элементов в начало
и конец списка, а также удаление последних элементов. Остальные операции имеют
сложность O(n).
|
Команда
|
Big O
|
Добавление в начало
|
push_front()
|
O(1)
|
Добавление
в конец
|
push_back()
|
O(1)
|
Удаление с конца
|
pop_back()
|
O(1)
|
Удаление с начала
|
pop_front()
|
O(1)
|
Вставка элемента
|
insert()
|
O(n)
|
Удаление промежуточных элементов
|
erase()
|
O(n)
|
Доступ к элементу
|
at()
|
O(n)
|
На следующем
занятии мы продолжим эту тему и посмотрим на пример реализации односвязного
списка на языке программирования.