Связный список на Python: Коты в коробках
LinkedList или связный список – это структура данных. Связный список обеспечивает возможность создать двунаправленную очередь из каких-либо элементов. Каждый элемент такого списка считается узлом. По факту в узле есть его значение, а также две ссылки – на предыдущий и на последующий узлы. То есть список «связывается» узлами, которые помогают двигаться вверх или вниз по списку. Из-за таких особенностей строения из связного списка можно организовать стек, очередь или двойную очередь.
Давайте визуализируем сухие определения. Теперь у нас есть коты, которые сидят в коробках. И на каждой коробке написано какая она по порядку и за какой должна стоять.
Что мы будем делать со связным списком:
- Проверять содержится ли в нем тот или иной элемент;
- Добавлять узлы в конец;
- Получать значение узла по индексу;
- Удалять узлы.
Начать придется с создания двух классов:
В общем случае, у нас получился узел, у которого есть внутри какое-то значение – кот, и ссылка на следующий узел. То есть в классе Box, соответственно, есть кот и ссылка на следующую коробку. Как и у любого списка, у связного тоже есть начало, а именно head. Поскольку изначально там ничего нет, начальному элементу присваивается значение None.
Содержится ли элемент в списке
Начнем с простого. Чтобы проверить есть ли какой-то определенный кот в одной из последовательно расположенных коробок, нужно пройтись циклом по всему списку, сверяя имеющееся значение со значениями элемента в списке.
Добавить узел в конец списка
Для начала новую коробку нужно создать, а уже в нее поместить нового кота. После необходимо проверять начиная с начала связного списка, есть ли в текущем узле ссылка на следующий и если она есть, то переходить к нему, в противном случае узел — последний, значит нужно создавать ссылку на следующий узел и помещать в него ту самую новую коробку, которую мы создали.
Получить узел по индексу
По индексу catIndex мы хотим получить узел-коробку, но поскольку как такового индекса у узлов не предусмотрено, нужно придумать какую-то замену, а именно переменную, которая будет выполнять роль индекса. Эта переменная – это boxIndex. Мы проходимся по всему списку и сверяем «порядковый номер» узла, и при совпадении его с искомым индексом – выдаем результат.
Удалить узел
Здесь мы рассмотрим удаление элемента не по индексу, а по значению, чтобы внести хоть какое-то разнообразие.
Поиск начинается с головы списка, то есть с первой по счету коробки, и продолжается, пока коробки не закончатся, то есть пока headcat не станет None. Мы проверяем соответствует ли значение, хранящееся в текущем узле, тому, которое мы хотим удалить. Если нет, то мы просто идем дальше. Однако, если соответствует, то мы удаляем его и «перепривязываем» ссылки, то есть мы удаляем N-ую коробку, при этом коробка N-1 теперь ссылается на коробку N+1.
Вот и все, спасибо, что ознакомились с материалом! На самом деле структура LinkedList это не сложно, и важно понимать, как она работает изнутри. Конечно, на Python ее можно было бы реализовать и в lambda-выражениях, это заняло бы гораздо меньше места, однако здесь я преследовала целью объяснить ее строение, и принцип ее работы на Python максимально подробно, а не гнаться за оптимизацией.
Связанные списки в Python
Связанный список — это линейная структура данных, элементы которой не хранятся в непрерывном месте. Это означает, что связанный список содержит отдельные вакуоли, известные как «узлы», которые содержат данные, для которых они были созданы, и ссылку на другой узел в списке.
Некоторыми преимуществами связного списка являются его прерывистый характер и время чтения, никогда не превышающее O(n). Связанный список не нужно хранить постоянно, потому что он имеет ссылки, встроенные в каждый узел, для расположения следующего по порядку. Если в памяти вашего компьютера мало места, идеально подойдет связанный список, поскольку всю структуру не нужно хранить в одном месте. Это также означает, что чтение связанного списка является линейным, поскольку размер списка приближается к бесконечности.
Однако недостатки делают его особенным. Кроме того, если в список вносится добавление, необходимо обновить весь список, чтобы ссылки оставались правильными. Последовательный характер связанного списка означает, что произвольный доступ не разрешен. Каждый узел необходимо читать в том порядке, в котором он был создан, чтобы иметь доступ ко всей необходимой информации.
В этой статье мы рассмотрим концепцию единственных и двусвязных списков и некоторые общие вопросы интервью, которые могут появиться для каждого из них.
Односвязный список
Односвязный список состоит из нескольких узлов, каждый из которых содержит а) данные и б) ссылку на следующий узел.
На изображении выше мы видим макет связанного списка. Начиная слева и продвигаясь вправо, мы видим, что заголовок списка содержит данные и указатель на следующий узел. Этот шаблон продолжается до конца списка, где он не является узлом. Значение NULL означает, что список закончился.
Посмотрите ниже код для создания односвязного списка.
Двусвязный список
В двусвязном списке каждый узел содержит данные, ссылку на узел, после него, и ссылку на узел, предшествующий ему.
Разница между односвязным списком и двусвязным списком — это «предыдущие» стрелки, указанные на рисунке выше. Преимущества дополнительного указателя означают, что список можно перемещать в любом направлении при доступе к информации — это означает, что переход от узла 5 к узлу 8 может быть проще, чем обход с начала списка.
Новые узлы в начале и в конце списка называются «дозорными». Эти узлы заменяют значения NULL, которые вы видите выше. Они позволяют быстро вставлять или удалять вверху или внизу списка.
Посмотрите ниже код для двусвязного списка.
Теперь, когда у нас есть код, необходимый для создания связанных списков, давайте рассмотрим некоторые общие вопросы собеседования, варианты которых вы можете найти на Leetcode.
Вопросов
1. Сторнирование связанного списка
Создайте функцию, чтобы перевернуть связанный список на месте. Вы будете использовать заголовок исходного списка и возвращать заголовок перевернутого списка.
Уловка, стоящая за этой проблемой, заключается в том, что разворот должен происходить в постоянном пространстве. Поэтому мы не создаем новый список и не добавляем или не используем прокси. Это необходимо сделать, работая непосредственно с этим списком.
Как объяснено в приведенном выше коде, мы, по сути, просто переключаем указатели для каждого узла. Входными данными является текущая глава связанного списка — или в наших примерах. Затем функция проходит через каждый узел и переключает направление атрибута nextnode. Посмотрите картинку ниже для дальнейшей визуализации.
Этот подход имеет то преимущество, что снижает затраты на память и впечатляет интервьюеров своей способностью работать без создания нового списка и удержания процесса на O(n) времени.
2. Связанный список с N-го до последнего узла
Создайте функцию, которая принимает головной узел и целое число n, а затем возвращает n-й и последний узел из списка.
Уловка для этой задачи состоит в том, чтобы пройти по списку двумя маркерами. Первый маркер выполняет итерацию и проверяет, действительно ли существует предпоследний узел. Второй маркер идет позади и заканчивается в этом узле.
Хотя код отлично справляется с созданием пространства между ними, давайте посмотрим на визуальный элемент.
Как вы можете видеть между первым и вторым шагами, идея состоит в том, что указатель 1 должен создавать расстояние между собой и указателем 2, равное n узлам. Как только это безопасно, два указателя могут перемещаться в унисон — указатель 1 проверяет, не закончился ли список, и указатель 2 готов к объявлению своей текущей позиции как n-го до последнего узла.
Вот и все. У нас были базовые основы того, что такое связанный список, и какие вопросы по нему можно задать.
Связный список на Python: что это такое и как его реализовать
Давайте поговорим немного о связных списках. Вероятно, вы о них слышали. Скажем, на лекциях по структурам данных. И возможно, вы думали, что это как-то сильно заумно. Почему бы не использовать массив? На самом деле связные списки имеют некоторые преимущества перед массивами и простыми списками. Поначалу эта тема может показаться сложной, но не волнуйтесь: мы все разберем.
Если вы представите себе фотографию людей, взявшихся за руки в хороводе, вы получите примерное представление о такой структуре, как связный список. Это некоторое количество отдельных узлов, связанных между собой ссылками, т. е. ссылками на другие узлы. Связные списки бывают двух видов: однонаправленные и двунаправленные (односвязные и двусвязные).
Источник: Medium.com
В односвязных списках каждый узел имеет одну стрелку, указывающую вперед, а в двусвязных узлы имеют еще и стрелки, указывающие назад. Но на собеседованиях в вопросах, касающихся связных списков, чаще всего имеются в виду односвязные. Почему? Их проще реализовать. Да, у вас не будет возможности перемещаться по списку в обратном направлении, но для отслеживания узлов хватит и однонаправленных связей.
Давайте попробуем реализовать связный список на Python. Возможно, вы бы начали с class Linked_list , а затем создали в нем узлы, но все можно сделать куда проще. Представьте цепочку из скрепок. Мы берем кучку скрепок и соединяем их, цепляя друг за дружку.
Цепочку создают отдельные скрепки плюс тот факт, что они сцеплены между собой. Поэтому вместо создания класса Linked_list мы просто создадим класс Node и позволим отдельным узлам связываться друг с другом.
Далее, как обычно при создании класса на Python, мы создаем метод __init__ . Этот метод инициализирует все поля, например, переменные в классе, при создании каждого нового объекта Node .
Мы будем принимать переменную data — это значение, которое мы хотим сохранять в узле. Также нам нужно определить ссылку, направленную вперед, она традиционно называется next . Сначала узел не связан ни с чем, поэтому мы устанавливаем next в None .
Это почти все, что нам нужно. Можно оставить, как есть, но в книге «Cracking the Coding Interview» также реализуется метод appendToTail() , который создает новый узел и добавляет его в конец списка, проходя его, так что нам не приходится делать это вручную.
Начнем с определения этого метода в классе Node . Метод будет принимать значение, которое мы хотим поместить в новый узел, и ключевое слово self (это специфично для Python).
Первое, что мы делаем, это создаем новый узел с заданным значением. Назовем его end .
Затем мы создаем указатель (поинтер). Это может звучать слишком технически, но по сути мы создаем ссылку на головной элемент ( head ) нашего списка. Мы делаем так, потому что хотим проходить по списку, не переназначая в нем ничего. Итак, мы делаем ссылку на первый узел, self , и сохраняем его в переменной n .
Наконец, мы проходим список. Как мы это делаем? Нам нужно всего лишь перемещаться к следующему узлу, если он есть. А если следующего узла нет, мы поймем, что мы уже в конце списка. Для прохождения списка до предпоследнего узла мы используем простой цикл while .
Наконец, мы указываем на последний узел, за которым нет следующего узла. Мы просто берем end — наш новый узел — и устанавливаем n.next = end .
Вот и все! Вот как выглядит наш класс полностью:
Проверяем наш связный список
Давайте все это проверим. Начнем с создания нового объекта Node. Назовем его ll (две латинские буквы «l» в нижнем регистре как сокращение Linked List). Назначим ему значение 1.
Поскольку мы написали такой классный метод append() , мы можем вызывать его для добавления в наш список новых узлов.
Как нам увидеть, как выглядит наш список? Теоретически, выглядеть он должен следующим образом:
Но нет способа вывести его именно в таком виде. Нам нужно пройти список, выводя каждое значение. Вы же помните, как проходить список? Мы только что это делали. Повторим:
- Создаем переменную, указывающую на head .
- Если есть следующий узел, перемещаемся к этому узлу.
И просто выводим data в каждом узле. Мы начинаем с шага № 1: создаем новую переменную и назначаем ее головным элементом списка.
Далее мы выводим первый узел. Почему мы не начали с цикла while? Цикл while проитерируется только дважды, потому что только у двух узлов есть next (у последнего узла его нет). В информатике это называется ошибкой на единицу (когда нужно сделать что-то Х раз плюс 1). Это можно представить в виде забора. Вы ставите столб, затем секцию забора, и чередуете пару столб + секция столько раз, сколько нужно по длине.
Но вы не можете оставить последнюю секцию забора висящей в воздухе. Ограда должна закончиться столбом, а не секцией. Поэтому вам приходится либо добавлять еще один столб в конце, либо (что в информатике более распространено) начать с постановки столба, а затем добавлять пары секция + столб . Это мы и сделаем.
Для начала мы выведем первый узел, а затем запустим цикл while для вывода всех последующих узлов.
Запустив это для нашего предыдущего списка, мы получим в консоли:
Ура! Наш связный список работает.
Зачем уметь создавать связный список на Python?
Зачем вообще может понадобиться создавать собственный связный список на Python? Это хороший вопрос. Использование связных списков имеет некоторые преимущества по сравнению с использованием просто списков Python.
Традиционно вопрос звучит как «чем использование связного списка лучше использования массива». Основная идея в том, что массивы в Java и других ООП-языках имеют фиксированный размер, поэтому для добавления элемента приходится создавать новый массив с размером N + 1 и помещать в него все значения из предыдущего массива. Пространственная и временная сложность этой операции — O(N). А вот добавление элемента в конец связного списка имеет постоянную временную сложность (O(1)).
Списки в Python это не настоящие массивы, а скорее реализация динамического массива, что имеет свои преимущества и недостатки. В Википедии есть таблица со сравнением производительности связных списков, массивов и динамических массивов.
Если вопрос производительности вас не тревожит, тогда да, проще реализовать обычный список Python. Но научиться реализовывать собственный связный список все равно полезно. Это как изучение математики: у нас есть калькуляторы, но основные концепции мы все-таки изучаем.
В сообществе разработчиков постоянно ведутся горячие споры о том, насколько целесообразно давать на технических интервью задания, связанные с алгоритмами и структурами данных. Возможно, в этом и нет никакого смысла, но на собеседовании вас вполне могут попросить реализовать связный список на Python. И теперь вы знаете, как это сделать.