Как написать двусвязный список в питоне
Перейти к содержимому

Как написать двусвязный список в питоне

  • автор:

Добавление элемента в двусвязный список

Я пытаюсь создать отсортированный двусвязный список, состоящий из товаров. У товара есть название и цена, сортировка по цене. Соответственно товар с самой высокой стоимостью будет впереди итд.

class Node: def __init__(self, nextNode, prevNode, data): self.data = data self.nextNode = nextNode self.prevNode = prevNode class Listnew: def __init__(self): self.head = None def push(self, item): if self.head is None: newNode = Node(None, None, item) self.head = newNode return else: newNode = Node(None, None, item) node = self.head while node is not None: if node.data.price > newNode.data.price: break node = node.nextNode newNode.prevNode = node newNode.nextNode = node.prevNode if node.prevNode is not None: node.nextNode.prevNode = newNode node.prevNode = newNode def printList(self): node = self.head while node is not None: print(node.data.price) node = node.nextNode class Item: def __init__(self, name, price): self.name = name self.price = price 

Но при попытке добавить более одного элемента в список получаю следующую ошибку:

node.nextNode.prevNode = newNode AttributeError: 'NoneType' object has no attribute 'prevNode' 

16. Связные списки¶

Мы уже видели примеры атрибутов, которые ссылаются на другие объекты. Ссылки на объекты использует и широко известная структура данных связный список.

Связные списки состоят из узлов, каждый из которых содержит ссылку на следующий узел в списке. Кроме того, каждый узел содержит какие-то полезные данные.

Связный список относится к рекурсивным структурам данных, поскольку его определение рекурсивно.

Связный список представляет собой либо

  • пустой список, представленный значением None , либо
  • узел, содержащий данные и ссылку на связный список.

Рекурсивные структуры данных могут обрабатываться рекурсивными методами.

16.2. Класс Node

Как обычно при определении нового класса, мы начнем с инициализирующего метода и метода __str__ , обеспечив возможность создания и отображения объектов нового класса:

class Node: def __init__(self, cargo=None, next=None): self.cargo = cargo self.next = next def __str__(self): return str(self.cargo) 

Параметры инициализирующего метода опциональны. По умолчанию и данные, cargo , и ссылка, next , получают значения None .

Строковым представлением узла будет строковое представление данных этого узла. Поскольку функции str можно передать любое значение, в нашем узле можно хранить любое значение.

Для тестирования создадим объект Node и выведем его на печать:

>>> node = Node("test") >>> print node test 

Чтобы было интереснее, нам нужен список с более чем одним узлом:

>>> node1 = Node(1) >>> node2 = Node(2) >>> node3 = Node(3) 

Этот код создает три узла, но у нас нет списка, так как ни один узел не связан с другим. Посмотрите на рисунок:

Три не связанных узла

Чтобы связать узлы, нам нужно заставить первый узел ссылаться на второй, а второй — на третий:

>>> node1.next = node2 >>> node2.next = node3 

Ссылка в третьем узле имеет значение None , что означает конец списка.

Три связанных узла

Теперь вы знаете, как создавать узлы и связывать их в списки. Но, возможно, пока не понимаете, зачем это нужно.

16.3. Списки как коллекции¶

Списки полезны, поскольку дают возможность собрать многочисленные объекты в единую сущность, иногда называемую коллекцией. В примере выше, первый узел списка может служить ссылкой на весь список.

Чтобы передать связный список в качестве аргумента, достаточно передать ссылку на первый узел. Например, функция print_list принимает один узел в качестве аргумента. Начиная с первого узла списка, она выводит на печать каждый узел, пока не достигнет конца списка:

def print_list(node): while node: print node, node = node.next print 

Вызовем функцию, передав ей ссылку на первый узел:

>>> print_list(node1) 1 2 3 

Хотя у print_list есть ссылка на первый узел списка, внутри функции нет переменных, ссылающихся на другие узлы. Функция получает ссылку на следующий узел, используя значение атрибута next каждого узла.

Обход списка

Чтобы пройти весь связный список, обычно используют переменную цикла вроде node , которая последовательно получает значения, ссылающиеся на узлы списка.

16.4. Списки и рекурсия¶

Многие операции над списком естественно реализовать с помощью рекурсивных методов. Вот рекурсивный алгоритм для вывода на печать списка в обратном порядке:

  1. Разделить список на две части: первый узел (голова) и все остальные (хвост).
  2. Распечатать хвост в обратном порядке.
  3. Распечатать голову.

Разумеется, шаг 2, рекурсивный вызов, предполагает, что у нас имеется способ распечатать список в обратном порядке. Но если мы примем, что рекурсивный вызов работает – нужно в это поверить – то мы можем убедиться в том, что алгоритм работает.

Все, что нам нужно, это простейший случай списка (базовый случай) и доказательство того, что, какой бы список мы ни взяли, наш алгоритм в конце концов приведет нас к этому базовому случаю. Имея рекурсивное определение списка, приведенное выше, в качестве базового случая возьмем пустой список, представленный значением None :

def print_backward(list): if list == None: return head = list tail = list.next print_backward(tail) print head, 

Первая строка обрабатывает базовый случай. Две следующие строки кода разделяют список на head (англ.: голова) и tail (англ.: хвост). Две последние строки кода выводят список на печать. Запятая в конце последней строки удерживает Python от перевода строки после печати каждого узла.

Вызовем функцию так же, как вызывали print_list :

>>> print_backward(node1) 3 2 1 

В результате на печать выведен список в обратном порядке.

Возможно, вы недоумеваете, почему print_list и print_backward являются функциями, а не методами класса Node . Причина в том, что мы используем None для представления пустого списка, а вызвать метод для None нельзя. Это ограничение не позволяет написать чистый объектно-ориентированный код для манипулирования списком.

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

16.5. Бесконечные списки¶

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

Узел списка ссылается сам на себя

Если вызвать print_list с этим списком, функция зациклится. Если вызвать print_backward , возникнет бесконечная рекурсия. Таким образом, работа с бесконечными списками сопряжена с определенными сложностями.

Тем не менее, иногда бесконечные списки полезны. Например, можно представить число как список цифр, и воспользоваться бесконечным списком для представления дробного периода этого числа.

И все же тот факт, что мы не можем доказать, что print_list и print_backward завершатся, представляет проблему. Лучшее, что мы можем сделать, это выдвинуть гипотезу: Если список не содержит циклов, то эти методы завершатся. Такого рода утверждения называются предусловием. Предусловие налагает ограничение на параметры и описывает поведение функции в случае, когда это ограничение выполняется. Вскоре мы встретимся с другими примерами предусловий.

16.6. Неоднозначность ссылки на узел списка¶

Следующий фрагмент print_backward может вызвать удивление:

head = list tail = list.next 

После выполнения первого предложения присваивания head и list имеют один и тот же тип и одно и то же значение. В таком случае, зачем мы создаем новую переменную?

Причина в том, что эти две переменные играют разные роли. Мы думаем о head как о ссылке на один узел, а о list – как о ссылке на первый узел списка. Эти роли не являются частью программы; они существуют в уме программиста.

В общем случае, глядя на код программы, мы не можем сказать, какую роль играет та или иная переменная. Эта неоднозначность может быть полезной, но также может затруднить чтение программы. Часто, чтобы подчеркнуть роль, которую играет переменная, мы используем переменные с “говорящими” именами, например, node и list , а иногда создаем дополнительные переменные с этой целью.

Можно переписать print_backward без переменных head и tail , что сделает функцию более компактной, но менее ясной:

def print_backward(list) : if list == None : return print_backward(list.next) print list, 

Глядя на два вызова функции, нужно помнить, что print_backward рассматривает свой аргумент как коллекцию, а print – как единичный объект.

Если же взять ссылку на узел связного списка вне контекста, то ее семантика неоднозначна. Ссылка на узел связного списка может рассматриваться как ссылка на один узел или как ссылка на список.

16.7. Изменение списков¶

Можно изменить список двумя способами. Очевидно, что мы можем изменить данные одного из узлов. Но более интересны операции по добавлению, удалению и перестановке узлов.

В качестве примера давайте напишем функцию, которая удаляет второй узел из списка и возвращает ссылку на удаленный узел:

def remove_second(list): if list == None: return first = list second = list.next # make the first node refer to the third first.next = second.next # separate the second node from the rest of the list second.next = None return second 

Здесь мы вновь используем временные переменные для того, чтобы сделать код яснее. Воспользуемся этой функцией:

>>> print_list(node1) 1 2 3 >>> removed = remove_second(node1) >>> print_list(removed) 2 >>> print_list(node1) 1 3 

Следующий рисунок иллюстрирует результат работы функции remove_second :

Удаление второго узла из списка

А что случится, если вызвать эту функцию со списком из одного элемента? С пустым списком? Существует ли предусловие для этой функции? Если да, то добавьте в функцию проверку предусловия и обработку его нарушения.

16.8. Обертки и помощники¶

Если нам понадобится вывести связный список в обратном порядке, заключенный в квадратные скобки, то, как вариант, мы можем воспользоваться функцией print_backward чтобы вывести 3 2 1 , и отдельно вывести открывающую и закрывающую скобки. Назовем новую функцию print_backward_nicely :

def print_backward_nicely(list) : print "[", print_backward(list) print "]", 

В любом месте программы можно вызвать функцию print_backward_nicely , а она, в свою очередь, вызовет print_backward . Здесь print_backward_nicely работает как обертка, используя функцию print_backward в качестве помощника.

16.9. Класс LinkedList

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

Создадим новый класс LinkedList . Его атрибутами будут целое число, представляющее длину списка, и ссылка на первый узел списка. С помощью объектов LinkedList удобно манипулировать списками объектов Node :

class LinkedList: def __init__(self): self.length = 0 self.head = None 

Класс LinkedList оказывается удобным местом для помещения в него таких функций, как print_backward_nicely , и превращения их в методы этого класса:

class LinkedList: . def print_backward(self): print "[", if self.head != None: self.head.print_backward() print "]", class Node: . def print_backward(self): if self.next != None: tail = self.next tail.print_backward() print self.cargo, 

Мы переименовали print_backward_nicely , и теперь у нас два метода с именами print_backward : один в классе Node (помощник), и один в классе LinkedList (обертка). Когда метод-обертка вызывает self.head.print_backward , он вызывает метод-помощник, поскольку self.head ссылается на объект Node .

Еще один плюс класса LinkedList состоит в том, что он облегчает добавление и удаление первого элемента списка. Например, следующий метод add_first класса LinkedList принимает в качестве аргумента данные для узла и помещает новый узел с этими данными в начало списка:

class LinkedList: . def add_first(self, cargo): node = Node(cargo) node.next = self.head self.head = node self.length += 1 

Создадим связный список, добавим в него три узла и выведем его на печать в обратном порядке:

>>> linkedlist = LinkedList() >>> linkedlist.add_first(1) >>> linkedlist.add_first(2) >>> linkedlist.add_first(3) >>> linkedlist.print_backward() [ 1 2 3 ] 

Поскольку каждый раз новый узел добавляется в начало списка, то последовательно добавленные нами узлы со значениями 1 , 2 , 3 расположились в обратном порядке, и метод print_backward вывел узлы в порядке их добавления.

В качестве упражнений вам будет предложено добавить другие полезные методы в класс LinkedList и поэкспериментировать с ними.

16.10. Инварианты¶

Некоторые списки построены правильно; другие нет. Например, если список содержит цикл, он сломает многие из наших методов. Поэтому мы можем потребовать, чтобы списки не содержали циклов. Другое разумное требование состоит в том, чтобы значение length в объекте LinkedList всегда равнялось реальному числу узлов в списке.

Требования, подобные этим, называются инвариантами, поскольку, в идеале, они должны выполняться для каждого объекта в любой момент времени. Указание инвариантов для объектов — полезный прием программирования. Он облегчает доказательство корректности кода, проверку целостности структур данных, и способствует обнаружению ошибок.

Заметим, что в отдельные моменты времени инварианты все же не выполняются. Например, в середине метода addFirst , после того, как мы добавили узел, но перед тем, как мы увеличили length , инвариант оказывается нарушенным. Такого рода нарушение приемлемо; действительно, часто невозможно изменить объект, не нарушая инвариант хотя бы ненадолго. Достаточно потребовать, чтобы метод, который нарушает инвариант, восстанавливал его.

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

16.11. Глоссарий¶

инвариант Утверждение, которое должно выполняться для объекта в любое время (за исключением того времени, когда объект изменяется). обертка Метод, который выступает посредником между вызывающим кодом и методом-помощником; способствует упрощению и повышению надежности кода. помощник Метод, не вызываемый непосредственно, а используемый вызываемым методом для выполнения части работы. предусловие Утверждение, которое должно быть справедливым, для того чтобы функция выполнялась корректно. связный список Структура данных, реализующая коллекцию, используя последовательность связанных узлов. узел списка Элемент списка, обычно реализуемый как объект, содержащий ссылку на объект того же типа и некоторые полезные данные.

16.12. Упражнения¶

  1. Традиционно списки выводятся на печать в скобках, с запятыми между элементами, например: [1, 2, 3] . Добавьте в класс LinkedList метод print_list так, чтобы он возвращал список в таком формате.
  2. Добавьте в класс LinkedList метод last , который вернет последний узел в списке или None в случае, когда список пуст. Протестируйте работу метода для пустого и непустого списков.
  3. Добавьте в класс LinkedList метод append(self, cargo) для добавления узла в конец списка. Используйте метод list из предыдущего упражнения для получения узла, к которому будет добавляться новый узел. Протестируйте работу метода.
  4. Добавьте в класс LinkedList метод find(self, cargo) для поиска в списке узла с cargo , ближайшего к началу списка. Протестируйте метод для пустого списка, списка, содержащего узел с искомым cargo , и для списка, не содержащего такого узла.
  5. Добавьте в класс LinkedList метод __contains__(self, cargo) чтобы реализовать оператор in для LinkedList . Используйте метод find из предыдущего упражнения в методе __contains__ . Протестируйте работу оператора in для пустого списка, списка, содержащего узел с cargo , и списка, не содержащего такого узла.

Просмотр

© Copyright 2009, 2012, Джеффри Элкнер, Аллен Б. Дауни, Крис Мейерс, Андрей Трофимов. При создании использован Sphinx 1.1.3.

Связный список на Python: Коты в коробках

Python очень удобный и многогранный язык, но по умолчанию не имеет такой структуры данных как связный список или LinkedList. Сегодня я поделюсь своими наработками на эту тему и расскажу немного о том, что из себя представляет эта структура данных. Эта статья будет интересна тем, кто впервые сталкивается с темой связных списков и хочет понять, как они работают с алгоритмической точки зрения.

Что такое LinkedList?

LinkedList или связный список – это структура данных. Связный список обеспечивает возможность создать двунаправленную очередь из каких-либо элементов. Каждый элемент такого списка считается узлом. По факту в узле есть его значение, а также две ссылки – на предыдущий и на последующий узлы. То есть список «связывается» узлами, которые помогают двигаться вверх или вниз по списку. Из-за таких особенностей строения из связного списка можно организовать стек, очередь или двойную очередь.

Давайте визуализируем сухие определения. Теперь у нас есть коты, которые сидят в коробках. И на каждой коробке написано какая она по порядку и за какой должна стоять.

Что мы будем делать со связным списком:

  1. Проверять содержится ли в нем тот или иной элемент;
  2. Добавлять узлы в конец;
  3. Получать значение узла по индексу;
  4. Удалять узлы.

Начать придется с создания двух классов:

class Box: def __init__ (self,cat = None): self.cat = cat self.nextcat = None class LinkedList: def __init__(self): self.head = None

В общем случае, у нас получился узел, у которого есть внутри какое-то значение – кот, и ссылка на следующий узел. То есть в классе Box, соответственно, есть кот и ссылка на следующую коробку. Как и у любого списка, у связного тоже есть начало, а именно head. Поскольку изначально там ничего нет, начальному элементу присваивается значение None.

Содержится ли элемент в списке

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

def contains (self, cat): lastbox = self.head while (lastbox): if cat == lastbox.cat: return True else: lastbox = lastbox.nextcat return False

Добавить узел в конец списка

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

 def addToEnd(self, newcat): newbox = Box(newcat) if self.head is None: self.head = newbox return lastbox = self.head while (lastbox.nextcat): lastbox = lastbox.nextcat lastbox.nextcat = newbox

Получить узел по индексу

По индексу catIndex мы хотим получить узел-коробку, но поскольку как такового индекса у узлов не предусмотрено, нужно придумать какую-то замену, а именно переменную, которая будет выполнять роль индекса. Эта переменная – это boxIndex. Мы проходимся по всему списку и сверяем «порядковый номер» узла, и при совпадении его с искомым индексом – выдаем результат.

 def get(self, catIndex): lastbox = self.head boxIndex = 0 while boxIndex 

Удалить узел

Здесь мы рассмотрим удаление элемента не по индексу, а по значению, чтобы внести хоть какое-то разнообразие.

Поиск начинается с головы списка, то есть с первой по счету коробки, и продолжается, пока коробки не закончатся, то есть пока headcat не станет None. Мы проверяем соответствует ли значение, хранящееся в текущем узле, тому, которое мы хотим удалить. Если нет, то мы просто идем дальше. Однако, если соответствует, то мы удаляем его и «перепривязываем» ссылки, то есть мы удаляем N-ую коробку, при этом коробка N-1 теперь ссылается на коробку N+1.

 def removeBox(self,rmcat): headcat = self.head if headcat is not None: if headcat.cat==rmcat: self.head = headcat.nextcat headcat = None return while headcat is not None: if headcat.cat==rmcat: break lastcat = headcat headcat = headcat.nextcat if headcat == None: return lastcat.nextcat = headcat.nextcat headcat = None

Вот и все, спасибо, что ознакомились с материалом! На самом деле структура LinkedList это не сложно, и важно понимать, как она работает изнутри. Конечно, на Python ее можно было бы реализовать и в lambda-выражениях, это заняло бы гораздо меньше места, однако здесь я преследовала целью объяснить ее строение, и принцип ее работы на Python максимально подробно, а не гнаться за оптимизацией.

  • Блог компании OTUS
  • Python
  • Программирование

Двусвязный список. Структура и основные операции

На этом занятии мы познакомимся с новой структурой данных – двусвязными списками. Если вы хорошо понимаете, как работает односвязный список, то вся основа у вас уже есть, так как двусвязный список – это все тот же односвязный, только каждый элемент имеет ссылки next и prev на следующий и предыдущий элементы. Во всем остальном он идентичен односвязному.

Также мы имеем здесь два указателя: head – на первый элемент списка; tail – на последний. В результате, можно очень быстро обрабатывать первые и последние элементы, например, делать добавление элементов в начало списка или вконец, а также удалять их. У граничных объектов указатель prev и next принимают значения NULL. Так можно определять первый и последний элементы списка. (Помимо значения NULL можно использовать любую другую предопределенную величину, например, None если программа пишется на Python).

Добавление элементов в начало и конец двусвязного списка

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

Предположим, что в списке два объекта и мы хотим добавить новый в его конец:

Вначале создается новый элемент в памяти компьютера, на который ведет временная ссылка ptr. Затем, ссылка next последнего объекта списка должна вести на этот новый объект. Для этого достаточно присвоить ссылке адрес нового элемента:

Далее необходимо ссылке prev нового элемента присвоить адрес последнего элемента списка:

И последнее, указатель tail переместить на новый последний элемент списка:

Скорость работы этой операции составляет O(1) и часто реализуется командой push_back().

По аналогии выполняется добавление нового элемента в начало двусвязного списка. Создается новый объект, на который ссылается указатель ptr. Затем, ссылка prev первого объекта должна вести на добавляемый элемент:

Ссылка next добавляемого элемента должна вести на объект head:

И указатель head перемещаем на объект ptr:

Вот так, достаточно просто выполняется добавление нового элемента в начало двусвязного списка. Скорость выполнения этой операции с точки зрения О большого составляет O(1) и часто реализуется командой push_front().

Доступ к произвольному элементу двусвязного списка

Давайте теперь посмотрим, как осуществляется доступ к произвольному элементу в двусвязном списке. Предположим, имеется список из нескольких элементов и указатели head и tail, которые ссылаются на первый и последний элементы этого списка. Затем, создадим еще один временный указатель ptr, который пусть изначально ссылается на первый элемент:

То есть, через указатель ptr мы сейчас обращаемся к первому элементу и можем, например, прочитать его данные командой:

Чтобы перейти к следующему второму элементу необходимо переместить указатель ptr на него. Сделать это можно очень просто с помощью указателя next первого объекта:

Получаем доступ ко второму элементу списка. Можем записывать и считывать из него данные:

По аналогии, для перехода к следующему третьему элементу, снова выполняем команду:

и указатель ptr ссылается на третий элемент. И так можно проходить по всем элементам списка до последнего.

С точки зрения О большого объем вычислений для перехода к произвольному k-му элементу списка составляет O(n), где n – общее число элементов в списке. И в этом двусвязный список проигрывает массивам, у которых скорость доступа к произвольному элементу O(1).

Но у двусвязных списков есть важное преимущество по сравнению с односвязными списками: мы можем перемещаться по элементам в обе стороны (и вправо и влево). Когда выполняется команда:

то осуществляется переход вправо. А с помощью команды:

влево. В частности, это несколько упрощает некоторые операции, например, удаление промежуточных элементов.

Вставка элемента в двусвязный список

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

Затем, создается новый объект в памяти устройства, на который ссылается временный указатель ptr. Все что нам осталось – это настроить связи между соседними элементами относительно вставляемого. Для этого создадим еще один временный указатель right, который будет ссылаться на следующий элемент после left:

В результате мы имеем ссылки 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++ это делается командой:

В некоторых других языках, таких как Python, эту операцию берет на себя сборщик мусора, когда на объект не ведет никаких внешних ссылок.

Осталось только изменить связи у объектов left и right (связать их между собой). Делается это очень просто. Ссылка next объекта left должна вести на объект right:

А ссылка prev объекта right на left:

Все, связи настроены и удаление промежуточного элемента выполнено. Вычислительная сложность самой операции удаления составляет O(1). С учетом поиска удаляемого элемента – O(n). А сама команда часто называется erase().

Удаление первого и последнего элементов

В заключение этого занятия отдельно рассмотрим алгоритмы удаления первого и последнего элемента двусвязного списка.

Предположим, в списке имеется четыре элемента и мы собираемся удалить первый. Тогда создадим временный указатель ptr, который будет ссылаться на следующий (второй) элемент:

И у этого второго элемента указатель prev приравняем значению NULL:

Затем, освободим память, занимаемую первым элементом head. В С++ это делается с помощью оператора delete:

И переместим указатель head на второй элемент, который теперь стал первым:

Вот общий принцип удаления первого элемента в двусвязном списке. Вычислительная сложность этого алгоритма составляет O(1) и часто реализуется командой pop_front().

По аналогии выполняется удаление последнего элемента. Вначале формируем временный указатель ptr на предыдущий объект списка:

Затем, указатель next объекта ptr приравниваем значению NULL:

Освобождаем память из под последнего элемента:

И устанавливаем указатель tail на новый последний элемент:

Вычислительная сложность этого алгоритма составляет O(1) и часто реализуется командой pop_back().

Заключение

Подведем общие итоги этого занятия. Самые быстрые операции – это добавление элементов в начало и конец списка, а также удаление последних элементов. Остальные операции имеют сложность O(n).

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *