Структуры данных
Связный список (Linked List) представляет набор связанных узлов, каждый из которых хранит собственно данные и ссылку на следующий узел. В реальной жизни связный список можно представить в виде поезда, каждый вагон которого может содержать некоторый груз или пассажиров и при этом может быть связан с другим вагоном.
Таким образом, если в массиве положение элементов определяется индексами, то в связном списке — указателями на следующий и (или) на предыдущий элемент.
Связные списки могут различаться. Есть односвязные списки, в которых каждый узел хранит указатель только на следующий узел. Есть двусвязные списки: в них каждый элемент хранит ссылку как на следующий элемент, так и на предыдущий. Есть кольцевые замкнутые списки. В данном случае мы рассмотрим создание односвязного списка.
Перед созданием списка нам надо определить класс узла, который будет представлять одиночный объект в списке:
Класс Node является обобщенным, поэтому может хранить данные любого типа. Для хранения данных предназначено свойство Data . Для ссылки на следующий узел определено свойство Next .
Далее определим сам класс списка:
Разберем основные моменты. В зависимости от конкретных задач реализация списков может отличаться, но для всех реализаций характерны прежде всего два метода: добавление и удаление.
Но прежде чем выполнять различные операции с данными, в классе списка определяются три переменные:
Если у нас не установлена переменная head (то есть список пуст), то устанавливаем head и tail. После добавления первого элемента они будут указывать на один и тот же объект.
Если же в списке есть как минимум один элемент, то устанавливаем свойство tail.Next — теперь оно хранит ссылку на новый узел. И переустанавливаем tail — теперь она ссылается на новый узел.
Сложность данного метода составляет O(1) . Графически это выглядит так:
Важно отметить наличие переменной tail, которая указывает на последний элемент. Ряд реализаций не используют подобную переменную и добавляют иным образом:
Данный способ вполне рабочий и нередко встречается, однако необходимость перебора элементов для нахождения последнего увеличивает время на поиск и сложность алгоритма. Она равна O(n) .
Особняком стоит метод добавления в начало списка, где нам достаточно переустановить ссылку на головной элемент:
Алгоритм удаления элемента представляет следующую последовательность шагов:
Поиск элемента в списке путем перебора всех элементов
Установка свойства Next у предыдущего узла (по отношению к удаляемому) на следующий узел по отношению к удаляемому.
Для отслеживания предыдущего узла применяется переменная previous . Если элемент найден, и переменная previous равна null, то удаление идет сначала, и в этом случае происходит переустановка переменной head, то есть головного элемента.
Если же previous не равна null, то реализуются шаги выше описанного алгоритма.
Сложность такого алгоритма составляет O(n) . Графически удаление можно представить так:
Чтобы проверить наличие элемента, исползуется метод Contains:
Здесь опять же просто осуществляется перебор. Сложность алгоритма метода составляет O(n) .
И для того, чтобы список можно было бы перебрать во внешней прграмме с помощью цикла for-each, класс списка реализует интерфейс IEnumerable :
Реализация данного интерфейса не является неотъемлимой частью односвязных списков, однако предоставляет эффективный метод для перебора коллекции в цикле foreach. Иначе нам бы пришлось реализовать какие-то собственные конструкции по перебору списка.
Структуры данных: связный список
Сегодня хочу просто и доходчиво рассказать про такую структуру данных как связный список. Это одна из базовых структур, которая может быть полезной при реализации алгоритмов различной сложности, в том числе при решении задачек на собеседованиях.
А зачем вообще эти структуры данных?
Многие начинающие (да и не только начинающие) программисты могут даже не знать, что существуют структуры данных, кроме встроенных в их любимый ЯП. Проработав несколько лет сначала с использованием Ruby, а затем и JavaScript, я был в их числе. Но в какой-то момент…говоря коротка — понадобились. И если вы считаете, что вам все эти алгоритмы и структуры данных даром не нужны, то…просто добавьте эту статью в закладки, вернетесь, когда будет надо.
Пишу я не только для вас, дорогие читатели, но (даже в первую очередь) для себя, поскольку в процессе объяснения материала кому-то сам начинаешь его лучше понимать. Как говорится, если ты не можешь объяснить что-то, чтобы тебя понял шестилетний ребенок — ты сам этого не понимаешь.
Собственно, к теме
Связный список — это базовая динамическая структура данных, состоящая из узлов, каждый из которых содержит значение и ссылку на следующий узел. Первый элемент списка — Head, последний — Tail, он ссылается на NULL.
Связные списки похожи на массивы, однако добавление и удаление элементов из середины или из начала списка здесь проще, так как нет необходимости менять индексы всех последующих элементов.
Двойной связанный список — это список, в котором узлы содержат ссылки еще и на предыдущий элемент.
Реализация
Этот раздел также делал в своих эгоистичных целях.
Для того, чтобы при решении различных задач и контестов мне не нужно было искать реализацию той или иной структуры данных в интернете или реализовывать вручную, теряя драгоценное время, я решил реализовать самые популярные структуры данных и алгоритмы, собрать это все в кучу и поместить к себе на github.
Базовым элементом списка является узел (Node) с полями value, next и prev (последнее — для двунаправленного списка). Реализуем двунаправленный список, из которого при необходимости можно легко сделать простой, просто убрав из кода указатели prev.
У самого списка также есть начальный набор свойств:
head — это “точка входа”, начальный элемент списка
tail — конечный элемент списка
length — количество элементов списка. Необязательный элемент, но иногда бывает необходим. Да и, пожалуй, одно значение много памяти не отнимет.
Методы
Сам список не будет представлять никакой ценности, если мы не сможем с ним ничего сделать.
Базовыми “умениями” нашего списка будет добавление элементов в конец (append) и в начало (prepend) списка.
Стоит отметить, что применение связанного списка вместо массива весьма оправдано как раз в случае, когда нужно добавлять или удалять большое количество элементов в начало списка, поскольку в связанном списке нет необходимости менять индексы элементов, после удаленных, то есть временная сложность O(1) у списка против O(n) у массива (для shift/unshift).
Для двунаправленного списка можно также добавить метод разворота списка.
Для понимания, что вообще происходит внутри списка, добавим служебный метод, выводящий список в консоль.
В итоге получаем нечто подобное:
Что в итоге
У любой вещи, технологии, концепции…у всего есть положительные и отрицательные стороны. Не бывает чего-либо однозначно хорошего и однозначно плохого, есть набор плюсов и минусов.
Если вы будете судить рыбу по её способности взбираться на дерево, она проживёт всю жизнь, считая себя дурой (А. Эйнштейн)
Плюсы связанного списка:
имеет гибкий размер
временная сложность вставки в начало (prepend) и в конец (append) — O(1)
занимает много памяти
перебор, вставка в середину и удаление произвольного элемента имеют временную сложность O(n)
Реализации связных списков (простого, двойного, сортированного, а также реализацию структуры данных «очередь», основанную на связном списке) можно взять в моем github
Резюме
Надеюсь, данная статья оказалась для вас полезной. Буду признателен за ваши плюсики, особенно учитывая, что это моя первая статья на Хабре (никогда ведь не поздно начинать).
Реализация связных списков на С++
Более подробно про структуры данных и алгоритмы, используемые статье можно прочитать тут:
Однонаправленный связанный список. Очередь
В данной своей статье я хотел бы рассмотреть такую интересную структуру данных, как связанный список или как его еще называют динамический список. Связный список — это динамическая структура данных, состоящая из узлов, которые содержат в себе в классическом варианте два значения: первое — это какое-либо данное (этим данным может быть что угодно: обычная переменная, объект класса и так далее), а второе — это указатель на следующий узел в списке (не зря же список является связанным).
Список связный потому что все узлы списка связаны между собой с помощью указателей, а динамический потому что динамически во время выполнения программы можно расширять данную структуру путем добавления новых узлов в список. В отличие от массива будь то статического, либо динамического, динамический список можно увеличивать во время работы программы. В этом то и есть его очень большой плюс. А вот давайте теперь и рассмотрим все это на рисунке:
На рисунке мы видим узлы, содержащие в себе два значения — данное и указатель. Указатель всегда указывает (содержит в себе адрес памяти) на следующий узел связанного списка. И самое важное — это то, что указатель последнего узла должен всегда выставляться в нуль (NULL, nullptr или просто 0). Этим он сообщает что является последним узлом связанного списка и что дальше указывать не на что. Если нужно будет добавить новый узел в динамический список, то это значение NULL заменяется на адрес нахождения в памяти нового узла (как это делается мы рассмотрим ниже), а сам же указатель нового узла опять выставляется в NULL. По ходу работы программы мы можем сколь угодно создавать таких узлов нашего связанного списка, единственное ограничение накладывает размер свободной оперативной памяти компьютера (ее конечно же должно хватать). Логически мы видим, что все узлы расположены как бы по порядку, хотя на самом деле в памяти компьютера они могут располагаться где угодно. И найти его не составит никакого труда, т.к. у нас есть в узле поле-указатель, указывающий на нужную ячейку памяти.
Давайте теперь последовательно рассмотрим работу связанного списка. Итак, мы описали в своей программе структуру, представляющую собой узел динамического списка. Эта структура из двух полей — данное и указатель на структуру того же типа. Такие структуры еще называются самоссылающимися (или структуры с самоадресацией). Вот как это будет выглядеть
А теперь нужно создать сам объект «связанный список», который и будет хранить эти самоссылающиеся узлы (Node — с англ. узел). Вот как мы это сделаем
Итак, если с первой структурой Node все понятно, то со структурой List , представляющей «связанный список» нам нужно сейчас разобраться. Мы выяснили, что динамический список состоит из узлов, значит класс List должен манипулировать этими узлами: создавать их, удалять, выводить на печать и так далее. Пока что остановимся только на таких моментах как создавать и выводить на печать, удаление оставим на потом. Как видите, в нашем классе List имеются два метода: addNode() — создает новый узел в динамическом списке, printList() — выводит содержание списка (всех узлов поочереди) на печать. Также у нас есть закрытое поле класса head типа Node — это так называемая «голова» связанного списка и судя из названия должна всегда указывать на начало списка в памяти компьютера, т.е. на его первый узел (этот момент мы не обсуждали выше, но он логически понятен — должен же быть указатель, указывающий просто на начало динамического списка и не содержащий никаких данных). Зная, где начинается связанный список, на него нам указывает «голова» head , и где заканчивается, об этом нам сообщает указатель последнего узла, выставленный в NULL , мы можем путешествовать по всему динамическому списку и произодить с них необходимые операции.
Изначально в конструкторе класса List переменной head выставляется значение в NULL , т.к. при создании объекта класса List связанный список еще пуст и узлов в нем нет, соответственно и указывать не на что. Складываем все вышеупомянутое и получаем рабочую программу, реализующую динамический список.
Результат работы программы будет выглядеть так: 
Думаю, что метод, добавляющий новый узел в список ( addNode ) нужно рассмотреть подробнее — не всем и все здесь будет понятно сразу же:
Итак, первая строка кода
Node *nd = new Node;
динамически (new) создает новый объект типа Node , т.е. новый узел. Как вы знаете, после отработки данной строки, в указатель nd , при успешном создании объекта, записывается адрес созданного объекта в памяти (в неудачном случае будет записано NULL , т.е. объект не создан). Идем дальше…
В этих двух строках кода мы уже обращаемся к полям созданного узла и присваиваем им необходимые значения: задаем данное — это данное метод addNode() принимает в качестве аргумента, выставляем указатель в NULL , т.к. вновь созданный узел всегда у нас будет последним (в данном варианте программы узлы добавляются в конец связанного списка — классический вариант). Далее…
Следующая конструкция выбора служит для определения: создается первый узел в списке или он уже не первый. В случае, если создается только первый узел, то head будет в NULL и выполнится условие после if , т.е. head присвоится адрес первого узла в памяти. В последующих случаях, когда создаются 2, 3, 4, 5, . узлы будет срабатывать блок после else . Его рассмотрим подробнее…
Создаем вспомагательную переменную типа Node и присваиваем ей указатель на начало списка. Далее в цикле мы последовательно проходимся по нашему связанному списку, пока не дойдем до узла, который был создан последним прошлый раз и присваиваем его указателю адрес нашего вновь созданного узла. Описанный процесс показан на рисунке:
Однонаправленный связнный список. Стек
Нами был рассмотрен классический вариант динамического списка, в котором новые узлы добавляются в конец, но есть еще вариант, когда узлы добаляются в начало, кстати, код такой программы немного меньше и проще. Его мы сейчас и рассмотрим.
Рассмотрев код программы, видим, что изменился метод добавления нового узла в список. Теперь новый узел как бы вклинивается между «головой» списка и следующим после нее узлом. Соответственно, в результатах работы мы видим в какой последовательности выводятся значения, находящиеся в узлах. Если вам подходит такой вариант обратного вывода, то можете использовать этот код.
Двунаправленный связанный список. Дек
В однонаправленном мы могли перемещаться только в одно направление и не могли вернуться назад, т.к. любой из следующих узлов не содержал в себе указателя на предыдущий. Также я добавил в программу возможность добавлять узлы как в начало списка, так и в конец, удалять узлы можно по условию, задаваемому функциональным объектом:
Определение и пояснение����
Когда мы будем говорить “связный список”, то подразумеваться будет однонаправленный связный список. Чтобы получше понять эту структуру данных, давайте рассмотрим ее отличительные особенности и возможности.
В массиве вы можете обращаться к элементам в произвольном порядке (напрямую), но в связном списке вам придётся перемещаться через все элементы, потому что в нём присутствуют так называемые ссылки (связки). Позже мы рассмотрим, что это означает. Что касается массивов, если вы делаете их динамическими, то возникает много сложностей. В случае же со связным списком всё намного проще, поскольку он растёт динамически.
Представление связного списка
Вот, как он выглядит:
Теперь, давайте разберём эту диаграмму. В ней мы видим 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 в конце.
Обратите внимание: обычно первый узел называется head, но в данном случае вместо head мы используем firstnode. Это не лучший вариант ��, но так нагляднее.
Теперь мы создали для нашего связного списка класс, который будет содержать столько узлов, сколько нам потребуется (Class LinkedList).
В строке 8 мы создаём конструктор. Теперь в коде будет два метода для добавления узлов в начале и в конце. Давайте их рассмотрим:
- В методе insert_at_beginning мы создаём новый узел и проверяем, является ли он первым узлом. При наличии узлов будет выполнена инструкция if, при их отсутствии же будет выполнена инструкция else.
- В методе inser_at_end мы создаём новый узел, и если список при проверке не окажется пуст, то сработает ветка условия if. Чтобы добавить узел в конец списка, потребуется перебрать его весь, поскольку обращаться к узлам напрямую нельзя. Здесь мы применяем перебор посредством цикла while, выполняя в нём проверку обнаружения последнего узла и размещая в итоге за ним новый узел. Если же связный список оказывается пуст, тогда срабатывает инструкция else и узел становится первым.
Компиляция 1
Давайте скомпилируем наш код и попробуем использовать эти методы:
Как и в коде выше, мы вставляем элементы в начало и конец. В итоге наш список должен выглядеть так: 5, 10, 20, 30.
Настал черёд написания метода для отображения этого списка.
Отображение связного списка
Добавляем метод для отображения:
Этот метод сначала будет проверять список на наличие элементов. Если он окажется пуст, будет выводится надпись List empty, в противном случае метод произведёт итерацию и выведет в консоль значения.
Компиляция 2
Давайте выполним компиляцию и используем методы класса LinkedList:
В этом коде мы используем метод display, и наш связный список будет выглядеть так:
Удаление узла
Теперь создадим метод, куда будет передаваться значение элемента, который нужно удалить, и назовём этот метод delete_node.
В этом методе сначала мы проверяем список на наличие элементов. Если он окажется пуст, тогда в консоль выводится LinkedList is Empty. Следующее условие проверяет, является ли удаляемый элемент firstNode. Если да, то удаляется первый узел.
Если же оба условия окажутся неверны, тогда придётся перебрать весь список, чтобы найти удаляемый элемент.
Компиляция 3
Теперь давайте применим этот метод удаления для нашего списка:
В итоге мы получим следующий вывод:
Поиск узлов
Теперь найдем узлы по их значению и создадим для этого метод search.
Добавив этот метод в класс LinkedList, мы вновь сначала проверяем список на наличие элементов. Если он пуст, тогда выводится list is empty, иначе производится его перебор в поиске нужного элемента.