Что такое односвязный список
Реализация односвязного списка на c++
Эта картинка демонстрирует, как будет выглядеть односвязный список.
Реализация узла
Значение, которое будет задавать пользователь
Указатель на следующий элемент (по умолчанию nullptr)
Реализация односвязного списка
Указатель на первый узел
Указатель на последний узел
Функция проверки наличия узлов в списке
Функция добавления элемента в конец списка
Функция печати всего списка
Функция поиска узла в списке по заданному значению
Функция удаления первого узла
Функция удаления последнего узла
Функция удаления узла по заданному значению значению
Функция обращения к узлу по индексу (дополнительная функция)
Реализация 1-3 пункта
Функция проверки наличия узлов в списке
Функция добавления элемента в конец списка
Здесь надо рассмотреть два случая:
В обоих случаях надо создать сам узел со значением, которое мы передали в эту функцию.
Первый случай:
Здесь нам как раз пригодиться функция проверки наличия узлов. Если список пустой, тогда мы присваиваем указателю на первый узел и последний узел указатель на новый узел и выходим из функции.
Второй случай:
Нам уже не нужно проверка наличия узлов в списке, так как если первый случай не происходит, то в списке есть узлы. Раз мы добавляем в конец, надо указать, что новый узел стоит после последнего узла. Затем мы меняем значения указателя last.
Теперь в список можно добавлять элементы.
Функция печати всего списка
Тест уже написанных функций
Код который мы написали:
Функция поиска узла в списке по заданному значению
Также делаем проверку is_empty() и создаём указатель p на первый узел
Обходим список, пока указатель p не пустой и пока значение узла p не равно заданному значению. После цикла возвращаем наш узел
Функция удаления первого узла
Функция удаления последнего узла
Конец списка одновременно и начало
Когда размер списка больше одного
Первый случай:
Сравниваем указатель на первый узел и указатель на последний узел, если они равны, то вызываем функцию удаления первого узла.
Второй случай:
Функция удаления узла по заданному значению значению
Делаем проверку is_empty(). И рассматриваем уже три случая:
Узел, который нам нужен, равен первому
Узел, который нам нужен, равен последнему
Когда не первый и не второй случаи
Первый случай:
Сравниваем значение первого узла с заданным значением, если значения совпадают, тогда вызываем функцию удаления первого узла.
Второй случай:
Сравниваем значение последнего узла с заданным значением, если значения совпадают, тогда вызываем функцию удаления последнего узла.
Третий случай:
Функция обращения к узлу по индексу
Для этой функции надо перегрузить оператор []
Тест программы
Заключение
Вот Вы и научились реализовывать односвязный список, и, надеюсь, стали лучше его понимать.
Односвязные списки
В односвязном списке каждый элемент информации содержит ссылку на следующий элемент списка. Каждый элемент данных обычно представляет собой структуру, которая состоит из информационных полей и указателя связи. Концептуально односвязный список выглядит так, как показано на рис. 22.2.
Рис. 22.2 Односвязный список
Как правило, элементы связанного списка являются структурами, так как, помимо данных, они содержат ссылку на следующий элемент. Поэтому необходимо определить структуру, которая будет использоваться в последующих примерах. Поскольку списки рассылки обычно хранятся в связанных списках, хорошим выбором будет структура, описывающая почтовый адрес. Ее описание показано ниже:
Несмотря на то, что созданный с помощью функции slstore() список можно отсортировать отдельной операцией уже после его создания, легче сразу создавать упорядоченный список, вставляя каждый новый элемент в нужное место в последовательности. Кроме того, если список уже отсортирован, имеет смысл поддерживать его упорядоченность, вставляя новые элементы в соответствующие позиции. Для вставки элемента таким способом требуется последовательно просматривать список до тех пор, пока не будет найдено место нового элемента, затем вставить в найденную позицию новую запись и переустановить ссылки.
При вставке элемента в односвязный список может возникнуть одна из трех ситуаций: элемент становится первым, элемент вставляется между двумя другими, элемент становится последним. На рис. 22.3 показана схема изменения ссылок в каждом случае.
Последовательный перебор элементов связанного списка осуществляется очень просто: начать с начала и следовать указателям. Обычно фрагмент кода перебора настолько мал, что его вставляют в другую процедуру — например, функцию поиска, удаления или отображения содержимого. Так, приведенная ниже функция выводит на экран все имена из списка рассылки:
Для получения элемента из списка нужно просто пройти по цепочке ссылок. Ниже приведен пример функции поиска по содержимому поля name :
Удаление элемента из односвязного списка выполняется просто. Так же, как и при вставке, возможны три случая: удаление первого элемента, удаление элемента в середине, удаление последнего элемента. На рис. 22.4 показаны все три операции.
Рис. 22.4. Удаление элемента из односвязного списка
У односвязных списков есть один большой недостаток: односвязный список невозможно прочитать в обратном направлении. По этой причине обычно применяются двусвязные списки.
[1] Не забывайте, что у односвязного списка, как и у веревки, два конца: начало и конец.
Односвязный список
В информатике, cвя́зный спи́сок — структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующее и/или предыдущее поле. Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.
Содержание
Виды связных списков
Линейный связный список
Односвязный список
В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента из данного невозможно.
Двусвязный список
По двусвязному списку можно передвигаться в любом направлении — как к началу, так и к концу. В этом списке проще производить удаление и перестановку элементов, т.к. всегда известны адреса тех элементов списка, указатели которых направлены на изменяемый элемент.
XOR-связный список
Кольцевой связный список
Разновидностью связных списков является кольцевой (циклический, замкнутый) список. Он тоже может быть односвязным или двусвязным. Последний элемент кольцевого списка содержит указатель на первый, а первый (в случае двусвязного списка) — на последний.
Список с пропусками
Развёрнутый связный список
Достоинства
Недостатки
См. также
Полезное
Смотреть что такое «Односвязный список» в других словарях:
Связный список — В информатике, связный список базовая динамическая структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка.[1] Принципиальным… … Википедия
Двусвязный список — В информатике, cвязный список структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующее и/или предыдущее поле. Принципиальным преимуществом перед массивом является… … Википедия
Связанный список — В информатике, cвязный список структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующее и/или предыдущее поле. Принципиальным преимуществом перед массивом является… … Википедия
Линейный список — У этого термина существуют и другие значения, см. Список. Разновидность связного списка односвязный список, содержащий 3 элемента Линейный однонаправленный список это структура данных, состоящая из элементов одног … Википедия
Развёрнутый связный список — список, каждый физический элемент которого содержит несколько логических (обычно в виде массива, что … Википедия
Развёрнутый связанный список — список, каждый физический элемент которого содержит несколько логических (обычно в виде массива, что позволяет ускорить доступ к отдельным элементам). Позволяет значительно уменьшить размер памяти и увеличить производительность по сравнению с… … Википедия
Развернутый связанный список — Развёрнутый связанный список список, каждый физический элемент которого содержит несколько логических (обычно в виде массива, что позволяет ускорить доступ к отдельным элементам). Позволяет значительно уменьшить размер памяти и увеличить… … Википедия
Сортировка связного списка — Сортировка связного списка. Подавляющее большинство алгоритмов сортировки требует для своей работы возможности обращения к элементам сортируемого списка по их порядковым номерам (индексам). В связных списках, где элементы хранятся неупорядоченно … Википедия
Коллекция (программирование) — У этого термина существуют и другие значения, см. Коллекция. Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные исто … Википедия
Коллекция данных — Коллекция в программировании программный объект, содержащий в себе, тем или иным образом, набор значений одного или различных типов, и позволяющий обращаться к этим значениям. Коллекция позволяет записывать в себя значения и извлекать их.… … Википедия
Список
Связный список (англ. 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] изменят свое направление, не нарушив связности самого списка.
Односвязный список
Каждый элемент списка мы представим программно с помощью структуры, которая состоит из двух составляющих:
1.Одно или несколько полей, в которых будет содержаться основная информация, предназначенная для хранения.
2. Поле, содержащее указатель на следующий элемент списка.
Отдельные объекты подобной структуры мы далее будем называть узлами, связывая их между собой с помощью полей, содержащих указатели на следующий элемент.
После создания структуры, нам необходимо инкапсулировать её объекты в некий класс, что позволит управлять списком, как цельной конструкцией. В классе будет содержаться два указателя (на хвост, или начало списка и голову, или конец списка), а так же набор функции для работы со списком.
В целом, полученный список можно представить так:
Итак, основные моменты создания списка, мы рассмотрели, переходим непосредственно к его формированию.
Формирование списка. Отведем место для указателей в статической памяти.
Зарезервируем место для динамического объекта.
Присвоим значение переменной ptail, и поместим в информационное поле значение элемента.
Переменная ptail должна содержать адрес последнего добавленного элемента, т. к. он добавлен в конец.
Если требуется завершить построение списка, то в поле указателя последнего элемента нужно поместить NULL.
В результате построен линейный односвязный список, содержащий два узла.
Вставка узла в определенное заданное место списка. Здесь и далее, мы не будем приводить фрагменты кода, так как они являются крупными. Позже мы с вами просто рассмотрим пример реализации односвязного списка целиком. А, сейчас, разберем операции над списком с помощью иллюстраций. Выделить память под новый узел. Записать в новый узел значение. Записать в указатель на следующий узел адрес узла, который должен располагаться после нового узла. Заменить в узле, который будет располагаться перед новым узлом, записанный адрес на адрес нового узла.
Удаление узла из списка. Записать адрес узла, следующего за удаляемым узлом, в указатель на следующий узел в узле, предшествующем удаляемому. Удалить узел, предназначенный для удаления.