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

Перевернуть двусвязный список | Набор 4 (обмен данными)

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

Примеры:

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

Есть другой подход, который немного более интуитивен, но также и немного более дорог.
Этот метод похож на обратный массив. Чтобы обратить массив, мы помещаем два указателя — один в начале, а другой в конец списка. Затем мы меняем местами данные двух указателей и продвигаем оба указателя друг к другу. Мы останавливаемся либо когда встречаются два указателя, либо когда они пересекаются. Мы выполняем ровно n / 2 свопов, а временная сложность также составляет O (N).

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

Алгоритм

Примечание о сравнительной эффективности трех методов

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

Ниже приведена реализация алгоритма.

// Программа Cpp для обращения к списку с помощью обмена данными

Источник

Реализация двусвязного списка в Python

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

В односвязном списке каждый узел списка имеет два компонента: фактическое значение узла и ссылку на следующий узел в связанном списке. В двусвязном списке каждый узел имеет три компонента: значение узла, ссылку на предыдущий узел и ссылку на следующий узел. Для начального узла двусвязного списка ссылка на предыдущий узел равна нулю. Точно так же для последнего узла в двусвязном списке ссылка на следующий узел равна нулю.

Плюсы и минусы

Ниже приведены некоторые плюсы и минусы двусвязного списка:

Реализация

В этом разделе мы увидим, как мы можем создать очень простой двусвязный список в Python. Если вы читали часть 1 и часть 2 этой серии статей, код должен быть довольно простым.

Как всегда, давайте сначала создадим класс для единственного узла в списке. Добавьте в свой файл следующий код:

В приведенном выше коде вы можете видеть, что мы создаем класс Node с тремя переменными-членами: item, nref и pref. Переменная item будет хранить фактические данные для узла. Nref хранит ссылку на следующий узел, а pref сохраняет ссылку на предыдущий узел в двусвязном списке.

Затем нам нужно создать класс DoublyLinkedList, который содержит различные функции, связанные с двусвязным списком Python. Добавьте следующий код:

В этой статье мы продолжим добавлять функции к этому классу.

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

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

В приведенном выше скрипте мы определяем метод insert_in_emptylist(). Сначала метод проверяет, имеет ли значение переменной self.start_node значение None или нет. Если переменная равна None, это означает, что список фактически пуст.

Затем создается новый узел, и его значение инициализируется значением, переданным в качестве параметра данных функции insert_in_emptylist(). Наконец, значение переменной self.start_node устанавливается на новый узел. В случае, если список не пустой, пользователю просто отображается сообщение о том, что список не пуст.

Добавьте метод insert_in_emptylist() в созданный вами ранее класс DoublyLinkedList.

Вставка элементов в начало

Чтобы вставить элемент в начало двусвязного списка, мы должны сначала проверить, является ли список пустым или нет. Если список пуст, мы можем просто использовать логику, определенную в insert_in_emptylist(), для вставки элемента, поскольку в пустом списке первый элемент всегда находится в начале.

Следующий скрипт вставляет элемент в начало двусвязного списка:

Добавьте метод insert_at_start() в созданный вами ранее класс DoublyLinkedList.

Вставка элементов в конец

Вставка элемента в конец двусвязного списка чем-то похожа на вставку элемента в начало. Сначала нам нужно проверить, пуст ли список. Если список пуст, мы можем просто использовать метод insert_in_emptylist() для вставки элемента. Если список уже содержит какой-то элемент, мы проходим по списку, пока ссылка на следующий узел не станет None. Когда ссылка на следующий узел становится None, это означает, что текущий узел является последним узлом.

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

Добавьте метод insert_at_end() в созданный вами ранее класс DoublyLinkedList.

Вставка элемента после другого элемента

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

Скрипт для вставки элемента после другого элемента выглядит следующим образом:

Добавьте метод insert_after_item() в созданный вами ранее класс DoublyLinkedList.

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

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

Скрипт для добавления элемента перед другим элементом в двусвязном списке выглядит следующим образом:

Добавьте метод insert_before_item() в созданный вами ранее класс DoublyLinkedList.

Обход двусвязного списка

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

Добавьте метод traverse_list() в созданный вами ранее класс DoublyLinkedList.

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

Как и вставка, существует несколько способов удаления элементов из двусвязного списка. В этом разделе мы рассмотрим некоторые из них.

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

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

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

Добавьте метод delete_at_start() к классу DoublyLinkedList, который вы создали ранее.

Удаление элементов с конца

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

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

Добавьте метод delete_at_end() к классу DoublyLinkedList, который вы создали ранее.

Удаление элементов по значению

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

В приведенном выше скрипте мы создаем функцию delete_element_by_value(), которая принимает значение узла в качестве параметра и удаляет этот узел. В начале функции мы проверяем, пустой список или нет. Если список пуст, мы просто показываем пользователю, что список пуст.

Эта логика реализована в следующем фрагменте кода:

Затем мы проверяем, есть ли в списке единственный элемент и действительно ли этот элемент является элементом, который мы хотим удалить. Если единственным элементом является тот, который мы хотим удалить, мы просто устанавливаем для self.start_node значение None, что означает, что теперь в списке не будет элемента.

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

Следующий фрагмент кода реализует эту логику:

Затем мы обрабатываем случай, когда список имеет более одного элемента, но элемент, который нужно удалить, является первым элементом. В этом случае мы просто выполняем логику, написанную для метода delete_at_start(). Следующий фрагмент кода удаляет элемент с самого начала в случае нескольких элементов:

Наконец, если удаляемый узел является последним узлом, для следующей ссылки узла, предшествующего последнему узлу, устанавливается значение «None». Следующий скрипт реализует эту логику:

Добавьте метод delete_element_by_value() к классу DoublyLinkedList, который вы создали ранее.

Переворачивание списка

Скрипт обращения двусвязного списка выглядит следующим образом:

Добавьте метод reverse_linked_list() в созданный вами ранее класс DoublyLinkedList.

Тестирование функций двусвязного списка

Сначала создадим объект класса DoublyLinkedList. Выполните следующий скрипт:

Тестирование функций вставки

Давайте сначала протестируем функции вставки. Сначала мы добавим элементы в пустой список. Выполните следующий скрипт:

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

Теперь давайте добавим несколько элементов в начале. Выполните следующий скрипт:

Теперь, если вы пройдете по списку, вы должны увидеть следующие элементы в списке:

Чтобы добавить элементы в конце, выполните следующий скрипт:

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

Вставим элемент после 50.

Теперь список должен выглядеть так:

Наконец, давайте добавим элемент перед пунктом 29.

Список на данный момент должен содержать следующие элементы:

Тестирование функций удаления

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

Пункт 18 будет удален, и теперь список будет выглядеть так:

Точно так же следующий скрипт удаляет элемент из конца двусвязного списка:

Теперь при просмотре списка будут возвращены следующие элементы:

Наконец, вы также можете удалить элементы по значению, используя функцию delete_element_by_value(), как показано ниже:

Если вы сейчас пройдете по списку, вы увидите, что элемент 65 будет удален из списка.

Проверка обратной функции

Наконец, давайте перевернем список с помощью функции reverse_linked_list(). Выполните следующий скрипт:

Теперь, если вы пройдете по списку, вы увидите перевернутый связанный список:

Заключение

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

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

Источник

Как перевернуть список в Python

В этом руководстве мы расскажем, как перевернуть список в Python. Мы разберем несколько разных способов реверсирования списков и диапазонов списков на примерах.

Итак, давайте начнем!

От редакции Pythonist. Также рекомендуем статью «Как перевернуть строку в Python».

Как создать диапазон элементов в Python

range(start, stop, step)

Параметр start – это число, с которого начнется отсчет. По умолчанию данный параметр равен 0. Таким образом, мы формируем наш диапазон, начиная с нулевого элемента.

Рассмотрим пример, чтобы лучше понять, как это работает:

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

Ещё раз заметим, что в данном случае параметры start и step можно было не передавать, так как они по умолчанию и так равны 0 и 1 соответственно.

Марк Лутц «Изучаем Python»

Скачивайте книгу у нас в телеграм

Как перевернуть диапазон в Python

Как перевернуть массив в Python

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

Каждый элемент в массиве имеет собственный порядковый номер (индекс).

Однако, в отличие от других языков программирования, в Python массивы не являются встроенной структурой данных. Для работы с массивами их нужно импортировать из сторонних библиотек (Numpy).

Вместо этого мы используем списки. А для поворота списков Python предлагает несколько способов. Давайте их рассмотрим!

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

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

Например, предположим, что у нас есть следующий список:

Чтобы изменить порядок элементов списка my_list на 50, 40, 30, 20, 10, выполним следующее:

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

Как перевернуть список в Python с помощью срезов

К примеру, давайте рассмотрим такой случай:

В приведенном выше примере мы хотели получить каждый элемент из исходного списка, начиная с индекса 1 до индекса 3 (но не включая его!).

Примечание. Индексирование в Python начинается с 0, поэтому первый элемент имеет индекс 0, второй элемент имеет индекс 1 и так далее.

Если вы хотите вывести все элементы, вы можете использовать один из двух следующих способов:

Итак, мы поняли, как использовать срезы для вывода всех элементов, содержащихся в списке.

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

Рассмотрим на примере, как это работает:

Как перевернуть список в Python с помощью функции reversed()

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

К примеру, возьмем следующий список my_list :

Функция reversed() принимает список в качестве аргумента и возвращает нам исходные элементы, только в обратном порядке.

Заключение

Вот и все – теперь вы знаете основы работы с реверсированными списками в Python!

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

Источник

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

Я делаю программу на Python, которая реализует связанный список для поддержки нескольких функций, одна из функций, которую мне нужно сделать, это обратить стек. Я сделал классы Node, LinkedList и Stack, вот мой код:

Вот моя попытка решить проблему:

Изменить 2 : добавлена функция get.

Редактировать 3 : добавлена доработка моего кода, он снова и снова возвращает неправильное обращение с первым элементом.

5 ответов

Довольно просто перевернуть стек, используя базовые операции со стеком. Вытащите каждый предмет из старого стека и поместите его в новый.

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

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

Вы не должны возиться с указателями ссылок в своей функции реверса. Я предполагаю, что у вас есть метод pop () и другие основы вашего стека; если нет, то клонируйте вашу функцию removeFirst, чтобы вернуть удаленный узел.

Теперь рекурсивная функция проста: вытолкните заголовок списка, переверните оставшийся стек (если есть) и добавьте вытолкнутый узел в конец. Это решает вашу проблему?

Обычный алгоритм обращения вещей с использованием базовых структур данных состоит в том, чтобы использовать тот факт, что стек является структурой данных «первым в последнем из». Это означает, что если вы pop до тех пор, пока стек не опустеет, вы получите элементы в обратном порядке, в котором вы push их ввели.

Другие подходы к решению этой проблемы: чит.

Определите метод __iter__ (который имеет смысл в любом случае; итерация является основным поведением Python), чтобы сделать ваш тип итеративным. Простой пример:

Тогда просто сделайте:

Конечно, это вероятно менее эффективно при распределении памяти / накладных расходах, чем при правильном выполнении. Но эффект, вероятно, незначительный, и он значительно упрощает код реализации.

Конечно, сделать это правильно не так сложно, это просто немного более запутанно (абсолютно не проверено, но это должно быть близко к праву):

Источник

Двусвязный список с примерами Python

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

В одном связанном списке каждый узел списка имеет два компонента: фактическое значение узла и ссылку на следующий узел в связанном списке. В двусвязном списке каждый узел имеет три компонента: значение узла, ссылка на предыдущий узел и ссылка на следующий узел. Для начального узла двусвязного списка ссылка на предыдущий узел равна нулю. Аналогично, для последнего узла в двусвязном списке ссылка на следующий узел равна нулю.

Плюсы и минусы двусвязного списка

Ниже приведены некоторые плюсы и минусы двусвязного списка:

Плюсы

Аферы

Реализация двусвязного списка с помощью Python

В этом разделе мы увидим, как мы можем создать очень простой двусвязный список в Python. Если вы читали Часть 1 и Часть 2 этой серии статей, код должен быть довольно простым.

Как всегда, давайте сначала создадим класс для одного узла в списке. Добавьте следующий код в свой файл:

На протяжении всей этой статьи мы будем продолжать добавлять функции в этот класс.

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

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

Вставка элементов в Пустой список

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

Вставка элементов в начале

В противном случае, если список не пуст, нам нужно выполнить три операции:

Следующий сценарий вставляет элемент в начало двусвязного списка:

Вставка элементов в конце

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

Вставка элемента после другого элемента

Чтобы вставить элемент после другого элемента, мы сначала проверяем, пуст ли список. Если список на самом деле пуст, мы просто выводим сообщение о том, что “список пуст”.

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

Сценарий вставки элемента после другого элемента выглядит следующим образом:

Вставка элемента перед другим элементом

Чтобы вставить элемент перед другим элементом, мы сначала проверяем, пуст ли список. Если список на самом деле пуст, мы просто выводим сообщение о том, что “список пуст”.

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

Сценарий добавления элемента перед другим элементом в двусвязном списке выглядит следующим образом:

Обход двусвязного списка

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

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

Как и вставка, существует несколько способов удаления элементов из двусвязного списка. В этом разделе мы рассмотрим некоторые из них.

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

Удаление элементов из конца

Удаление элементов по значению

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

Эта логика реализована в следующем фрагменте кода:

Следующая часть кода реализует эту логику:

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

Реверсирование двусвязного списка

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

Сценарий реверсирования двусвязного списка выглядит следующим образом:

Тестирование Функций Двусвязного Списка

В этом разделе мы протестируем двусвязные функции, созданные в предыдущих разделах.

Тестирование Функций Вставки

Давайте сначала проверим функции вставки. Сначала мы добавим элементы в пустой список. Выполните следующий сценарий:

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

Теперь давайте добавим несколько элементов в самом начале. Выполните следующий сценарий:

Теперь, если вы пройдете по списку, вы увидите в нем следующие элементы:

Чтобы добавить элементы в конце, выполните следующий сценарий:

Теперь, если вы пройдете по двусвязному списку, вы увидите следующие элементы:

Давайте вставим элемент после 50.

Теперь список должен выглядеть так:

Наконец, давайте добавим элемент перед пунктом 29.

Список на данный момент времени должен содержать следующие элементы:

Тестирование Функций Удаления

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

Пункт 18 будет удален и список теперь будет выглядеть так:

Аналогично, следующий сценарий удаляет элемент из конца двусвязного списка:

Теперь при обходе списка будут возвращены следующие элементы:

Если вы пройдете по списку сейчас, то увидите, что пункт 65 будет удален из списка.

Тестирование Обратной Функции

Теперь, если вы пройдете по списку, вы увидите перевернутый связанный список:

Вывод

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

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

Источник