|
Двусвязный список. Структура и основные операцииНа этом занятии мы познакомимся с новой структурой данных – двусвязными списками. Если вы хорошо понимаете, как работает односвязный список, то вся основа у вас уже есть, так как двусвязный список – это все тот же односвязный, только каждый элемент имеет ссылки 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
А следующие две (между right и ptr) командами: right.prev = ptr
Все, новый элемент вставлен в двусвязный список после объекта left. Разумеется, в реальных программах нужно дополнительно проверять, чтобы объекты left и right существовали, прежде чем обращаться к указателям next и prev этих объектов. Вычислительная сложность непосредственно вставки нового элемента, составляет O(1). Но здесь нужно учитывать, что прежде необходимо получить ссылку на объект left, после которого вставляется новый элемент. А эта операция выполняется за O(n). Поэтому, в общем случае, вставка нового элемента в двусвязный список имеет сложность O(n). И часто реализуется командой insert(). Удаление промежуточных элементовСледующая операция – удаление промежуточных элементов. Предположим, имеется список из четырех элементов и мы хотим удалить третий. На него ведет указатель node:
Первым шагом нам нужно получить ссылки на соседние объекты относительно удаляемого. Это можно сделать командами: left = node.prev
Затем, освободить память, занимаемую объектом 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).
На следующем занятии мы продолжим эту тему и посмотрим на пример реализации односвязного списка на языке программирования. Видео по теме |
