что такое связанный список

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

Jul 25, 2020 · 5 min read

Определение и пояснение👨‍💻

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

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

Представление связного списка

Вот, как он выглядит:

Теперь, давайте разберём эту диагра м му. В ней мы видим 4 рамки, называемые узлами. Каждый узел может обладать двумя характеристиками: значением и связкой, содержащей адрес ячейки памяти следующего узла. В нашей диаграмме первый узел содержит значение 10 и адрес следующего узла 4900 (таким образом он находит в памяти следующий узел).

Первый узел называется Head (голова), а последний Tail (хвост). В последнем узле на приведённой диаграмме адрес указан как null. Это означает, что за ним узла не последует.

Важно помнить при работе с кодом🗣

В С++ и С элемент, хранящий адрес ячейки памяти, мы называем Pointer (указатель).

В Java, Python его же мы называем Reference (ссылкой).

Для хранения деталей узла в С мы используем Struct (структуры), а в C++, Java или Python — Class (класс).

В C и C++ в последнем узле адрес обозначается как nil (ноль), а в Python как None (нет).

Создание узла

Давайте создадим узел в Python:

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

Здесь мы создаём Class под названием Node и добавляем в него конструктор. Поскольку узел может иметь значение и ссылку, то мы соответственно называем эти компоненты value и link. Нужно отметить, что изначально мы определяем link как none, потому что, когда первый узел только создается, для него ещё не существует соседнего узла и, соответственно, адреса в памяти тоже нет 😎.

Теперь в строке 7 мы создаём экземпляр этого класса под названием first и передаём его узлу значение 10. При выводе в консоль значения этого узла мы получим 10, а при выводе значения link — none.

Добавление узла

Теперь добавим в связный список узел и отобразим его. Для добавления мы напишем insert_at_beginning в начале списка и insert_at_end в конце.

Теперь мы создали для нашего связного списка класс, который будет содержать столько узлов, сколько нам потребуется (Class LinkedList).

В строке 8 мы создаём конструктор. Теперь в коде будет два метода для добавления узлов в начале и в конце. Давайте их рассмотрим:

Компиляция 1

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

Как и в коде выше, мы вставляем элементы в начало и конец. В итоге наш список должен выглядеть так: 5, 10, 20, 30.

Настал черёд написания метода для отображения этого списка.

Отображение связного списка

Добавляем метод для отображения:

Этот метод сначала будет проверять список на наличие элементов. Если он окажется пуст, будет выводится надпись List empty, в противном случае метод произведёт итерацию и выведет в консоль значения.

Компиляция 2

Давайте выполним компиляцию и используем методы класса LinkedList:

В этом коде мы используем метод display, и наш связный список будет выглядеть так:

Удаление узла

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

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

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

Компиляция 3

Теперь давайте применим этот метод удаления для нашего списка:

В итоге мы получим следующий вывод:

Поиск узлов

Теперь найдем узлы по их значению и создадим для этого метод search.

Добавив этот метод в класс LinkedList, мы вновь сначала проверяем список на наличие элементов. Если он пуст, тогда выводится list is empty, иначе производится его перебор в поиске нужного элемента.

Компиляция 4

Пробуем поиск по нашему списку:

Здесь мы ищем узел со значением 30, и вывод должен получиться следующий:

Источник

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

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

Реализация узла

Значение, которое будет задавать пользователь

Указатель на следующий элемент (по умолчанию nullptr)

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

Указатель на первый узел

Указатель на последний узел

Функция проверки наличия узлов в списке

Функция добавления элемента в конец списка

Функция печати всего списка

Функция поиска узла в списке по заданному значению

Функция удаления первого узла

Функция удаления последнего узла

Функция удаления узла по заданному значению значению

Функция обращения к узлу по индексу (дополнительная функция)

Реализация 1-3 пункта

Функция проверки наличия узлов в списке

Функция добавления элемента в конец списка

Здесь надо рассмотреть два случая:

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

Первый случай:

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

Второй случай:

Нам уже не нужно проверка наличия узлов в списке, так как если первый случай не происходит, то в списке есть узлы. Раз мы добавляем в конец, надо указать, что новый узел стоит после последнего узла. Затем мы меняем значения указателя last.

Теперь в список можно добавлять элементы.

Функция печати всего списка

Тест уже написанных функций

Код который мы написали:

Функция поиска узла в списке по заданному значению

Также делаем проверку is_empty() и создаём указатель p на первый узел

Обходим список, пока указатель p не пустой и пока значение узла p не равно заданному значению. После цикла возвращаем наш узел

Функция удаления первого узла

Функция удаления последнего узла

Конец списка одновременно и начало

Когда размер списка больше одного

Первый случай:

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

Второй случай:

Функция удаления узла по заданному значению значению

Делаем проверку is_empty(). И рассматриваем уже три случая:

Узел, который нам нужен, равен первому

Узел, который нам нужен, равен последнему

Когда не первый и не второй случаи

Первый случай:

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

Второй случай:

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

Третий случай:

Функция обращения к узлу по индексу

Для этой функции надо перегрузить оператор []

Тест программы

Заключение

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

Источник

Связный список на Python: что это такое и как его реализовать

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

Если вы представите себе фотографию людей, взявшихся за руки в хороводе, вы получите примерное представление о такой структуре, как связный список. Это некоторое количество отдельных узлов, связанных между собой ссылками, т. е. ссылками на другие узлы. Связные списки бывают двух видов: однонаправленные и двунаправленные (односвязные и двусвязные).

Источник: Medium.com

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

Цепочку создают отдельные скрепки плюс тот факт, что они сцеплены между собой. Поэтому вместо создания класса Linked_list мы просто создадим класс Node и позволим отдельным узлам связываться друг с другом.

Вот и все! Вот как выглядит наш класс полностью:

Проверяем наш связный список

Давайте все это проверим. Начнем с создания нового объекта Node. Назовем его ll (две латинские буквы «l» в нижнем регистре как сокращение Linked List). Назначим ему значение 1.

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

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

И просто выводим data в каждом узле. Мы начинаем с шага № 1: создаем новую переменную и назначаем ее головным элементом списка.

Далее мы выводим первый узел. Почему мы не начали с цикла while? Цикл while проитерируется только дважды, потому что только у двух узлов есть next (у последнего узла его нет). В информатике это называется ошибкой на единицу (когда нужно сделать что-то Х раз плюс 1). Это можно представить в виде забора. Вы ставите столб, затем секцию забора, и чередуете пару столб + секция столько раз, сколько нужно по длине.

Для начала мы выведем первый узел, а затем запустим цикл while для вывода всех последующих узлов.

Запустив это для нашего предыдущего списка, мы получим в консоли:

Ура! Наш связный список работает.

Зачем уметь создавать связный список на Python?

Зачем вообще может понадобиться создавать собственный связный список на Python? Это хороший вопрос. Использование связных списков имеет некоторые преимущества по сравнению с использованием просто списков Python.

Традиционно вопрос звучит как «чем использование связного списка лучше использования массива». Основная идея в том, что массивы в Java и других ООП-языках имеют фиксированный размер, поэтому для добавления элемента приходится создавать новый массив с размером N + 1 и помещать в него все значения из предыдущего массива. Пространственная и временная сложность этой операции — O(N). А вот добавление элемента в конец связного списка имеет постоянную временную сложность (O(1)).

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

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

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

Источник

Введение в связанные списки

Авторизуйтесь

Введение в связанные списки

Знакомимся со структурой связных списков вместе с Арианой на примере её песни «‎Thank U, Next». Если вы её ещё не слышали, то посмотрите клип, прежде, чем читать дальше.

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

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

В статье мы будем использовать следующий список:

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

Thought I’d end up with Sean
But he wasn’t a match
Wrote some songs about Ricky
Now I listen and laugh
Even almost got married
And for Pete, I’m so thankful
Wish I could say, «Thank you» to Malcolm
‘Cause he was an angel

Последний узел — сама Ариана:

Plus, I met someone else
We havin’ better discussions
I know they say I move on too fast
But this one gon’ last
‘Cause her name is Ari
And I’m so good with that (so good with that)

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

Простейший способ создать односвязный список — поочерёдно создать и связать узлы:

Пример аналогичного кода на Python.

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

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

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

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

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

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

Все объекты красного цвета удаляются.

Два других полезных метода — search и iterate :

Итак, мы знаем, что хранение перечня бывших Арианы в связном списке — хорошее применение этой структуры данных. Ведь мы всегда перечисляем их в одном порядке, напевая «‎thank u, next»! Ещё они хорошо подходят, например, для формирования очереди задач. Так, принтеры печатают по одной странице, но мы хотим добавлять дополнительные задачи и не отправлять документы на печать по одной странице. Когда мы создаём список задач, мы всегда будем добавлять новые объекты в конец очереди и потом печатать первый объект в списке. Похожим образом работает кнопка браузера «‎Назад» или функция «‎Undo» редактора. Для реализации этих возможностей ПО обычно используют структуры данных стек или очередь, основанные на связанных списках.

Источник

Алгоритмы и структуры данных для начинающих: связный список

Авторизуйтесь

Алгоритмы и структуры данных для начинающих: связный список

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

Связный список

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

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

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

Это отличный способ хранить данные. Большинство языков программирования позволяют так или иначе выделить память в виде массива и оперировать его содержимым. Последовательное хранение данных увеличивает производительность (data locality), позволяет легко итерироваться по содержимому и получать доступ к произвольному элементу по индексу.

Тем не менее, иногда массив — не самая подходящая структура.

Предположим, что у нашей программы следующие требования:

Поскольку в требованиях указано, что считанные числа передаются в метод ProcessItems за один раз, очевидным решение будет массив целых чисел:

У этого решения есть ряд проблем, но самая очевидная из них — что случится, если будет необходимо прочесть больше 20 значений? В данной реализации значения с 21 и далее просто проигнорируются. Можно выделить больше памяти — 200 или 2000 элементов. Можно дать пользователю возможность выбрать размер массива. Или выделить память под новый массив большего размера при заполнении старого и скопировать элементы. Но все эти решения усложняют код и бесполезно тратят память.

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

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

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

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

Реализация класса LinkedList

Класс Node

В основе связного списка лежит понятие узла, или элемента (Node). Узел — это контейнер, который позволяет хранить данные и получать следующий узел.

В самом простом случае класс Node можно реализовать так:

Класс LinkedList

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

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

Учитывая все вышесказанное, давайте набросаем примерный план класса, а затем заполним недостающие методы.

Метод Add

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

Основная сложность заключается в том, чтобы найти последний узел списка. Можно сделать это двумя способами. Первый — сохранять указатель на первый узел списка и перебирать узлы, пока не дойдем до последнего. В этом случае нам не требуется сохранять указатель на последний узел, что позволяет использовать меньше памяти (в зависимости от размера указателя на вашей платформе), но требует прохода по всему списку при каждом добавлении узла. Это значит, что метод Add займет O(n) времени.

Второй метод заключается в сохранении указателя на последний узел списка, и тогда при добавлении нового узла мы поменяем указатель так, чтобы он указывал на новый узел. Этот способ предпочтительней, поскольку выполняется за O(1) времени.

Первое, что нам необходимо сделать — добавить два приватных поля в класс LinkedList : ссылки на первый (head) и последний (tail) узлы.

Теперь мы можем добавить метод, который выполняет три необходимых шага.

Метод Remove

После удаления узла поле Next узла со значением «2» будет указывать на узел со значением «4».

Основной алгоритм удаления элемента такой:

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

Поле Count декрементируется при удалении узла.

Метод Contains

Метод GetEnumerator

Метод Clear

Метод CopyTo

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

Метод Count

Метод IsReadOnly

Двусвязный список

Связный список, который мы только что создали, называется также «односвязным». Это значит, что между узлами только одна связь в единственном направлении от первого узла к последнему. Есть также достаточно распространенный вариант списка, который предоставляет доступ к обоим концам — двусвязный список.

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

Класс Node

Единственное изменение, которое надо внести в класс LinkedListNode — добавить поле со ссылкой на предыдущий узел.

Метод AddFirst

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

Метод AddLast

Метод RemoveFirst

Метод RemoveLast

Метод Remove

Зачем нужен двусвязный список?

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

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

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

Продолжение следует

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

Источник