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

Список

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

Содержание

Односвязный список [ править ]

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

Двусвязный список [ править ]

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

XOR-связный список [ править ]

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

Циклический список [ править ]

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

Операции на списке [ править ]

Рассмотрим базовые операции на примере односвязного списка.

Вставка [ править ]

Очевиден случай, когда необходимо добавить элемент ( [math]newHead[/math] ) в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.

Поиск [ править ]

Удаление [ править ]

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

Удаление элемента после заданного ( [math]thisElement[/math] ) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.

Поиск цикла в списке [ править ]

Для начала необходимо уметь определять — список циклический или нет. Воспользуемся алгоритмом Флойда «Черепаха и заяц». Пусть за одну итерацию первый указатель (черепаха) переходит к следующему элементу списка, а второй указатель (заяц) на два элемента вперед. Тогда, если эти два указателя встретятся, то цикл найден, если дошли до конца списка, то цикла нет.

Поиск длины хвоста в списке с циклом [ править ]

Наивные реализации [ править ]

Реализация за [math]O(n^2)[/math] [ править ]

Будем последовательно идти от начала цикла и проверять, лежит ли этот элемент на цикле. На каждой итерации запустим от [math]pointMeeting[/math] вперёд указатель. Если он окажется в текущем элементе, прежде чем посетит [math]pointMeeting[/math] снова, то точку окончания (начала) хвоста нашли.

Реализация за [math]O(n \log n)[/math] [ править ]

Эффективная реализация [ править ]

Доказательство корректности алгоритма [ править ]

[math]f_1(n) = L + (n-L) \bmod N[/math]

[math]f_2(n) = L + (2n-L) \bmod N[/math]

[math]Q = L + (1-k) N[/math]

Пусть [math]L = p N + M, 0 \leqslant M \lt N[/math]

[math]L \lt k N \leqslant L + N[/math]

[math]pN + M \lt kN \leqslant (p+1)N + M[/math] откуда [math]k = p + 1[/math]

Задача про обращение списка [ править ]

Для того, чтобы обратить список, необходимо пройти по всем элементам этого списка, и все указатели на следующий элемент заменить на предыдущий. Эта рекурсивная функция принимает указатель на голову списка и предыдущий элемент (при запуске указывать [math]NULL[/math] ), а возвращает указатель на новую голову списка.

Алгоритм корректен, поскольку значения элементов в списке не изменяются, а все указатели [math]next[/math] изменят свое направление, не нарушив связности самого списка.

Источник

Связные списки, трюки с указателями и хороший вкус

В интервью на TED 2016 (14:10) Линус Торвальдс рассказывает о хорошем стиле программирования. В качестве примера приводит два варианта удаления элементов из односвязных списков (см. ниже). В первом варианте есть специальный случай, а в другом — нет. Линус предпочитает второй.

[. ] Не надо размышлять, почему здесь нет оператора if. Важно посмотреть на задачу с другой стороны и переписать её так, чтобы особый случай исчез и стал обычным случаем, и это хороший код. — Л. Торвальдс

В качестве примера Линус показывает достаточно простой псевдокод в стиле Си. Но не даёт концептуального объяснения. Поэтому не сразу понятно, как работает косвенный указатель.

Подробно разберём это решение и его преимущества. В качестве бонуса показано не только удаление, но и вставка элемента через косвенную адресацию.

Базовая структура данных для односвязного списка целых чисел показана на рис. 1.

Рис. 1. Односвязный список из целых чисел

Реализация структуры данных на Си:

Также (минимальный) API:

Базовая версия

Рис. 2. Концептуальная модель структуры данных списка в базовом алгоритме

Более элегантное решение

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

Как это работает?

Косвенный указатель p даёт два концептуальных преимущества:

Интеграция указателя head

Элегантная реализация использует схему косвенной адресации, которая даёт другое представление о структуре данных:

Рис. 3. Концептуальная модель структуры данных списка в более элегантном решении

Здесь p представляет тип IntListItem** и содержит адрес указателя на текущий элемент списка. Когда указатель продвигается вперёд, его адрес меняется на следующий элемент.

В коде это выглядит как p = &(*p)->next :

Последний штрих

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

Если p содержит адрес указателя на элемент списка, сравнение в цикле поиска становится таким:

Новое применение

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

Во-первых, добавим следующую декларацию в list.h :

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

Быстрый рефакторинг

Прежде чем двигаться дальше, оформим цикл поиска в отдельную функцию:

и используем её в remove_elegant() :

Реализация insert_before()

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

Заключение

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

Итак, возвращаясь к первоначальному замечанию Линуса: это показатель хорошего вкуса? Трудно сказать. Но явно налицо творческое и очень элегантное решение хорошо известной задачи.

Источник

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

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

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

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

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

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

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

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

20–22 декабря, Онлайн, Беcплатно

Это отличный способ хранить данные. Большинство языков программирования позволяют так или иначе выделить память в виде массива и оперировать его содержимым. Последовательное хранение данных увеличивает производительность (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 для того, чтобы обойти список задом наперед.

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

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

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

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

Источник

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

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

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

По типу связности выделяют односвязные, двусвязные, XOR-связные, кольцевые и некоторые другие списки.

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

На изображении каждый из блоков представляет элемент (узел) списка. Здесь и далее Head list – заголовочный элемент списка (для него предполагается поле next). Он не содержит данные, а только ссылку на следующий элемент. На наличие данных указывает поле info, а ссылки – поле next (далее за ссылки будет отвечать и поле prev). Признаком отсутствия указателя является поле nil.

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

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

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

Когда количество памяти, по каким-либо причинам, ограничено, тогда альтернативой двусвязному списку может послужить XOR-связный список. Последний использует логическую операцию XOR (исключающее «ИЛИ», строгая дизъюнкция), которая для двух переменных возвращает истину лишь при условии, что истинно только одно из них, а второе, соответственно, ложно. Таблица истинности операции:

Источник