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

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

В информатике, свя́зный спи́сок — базовая динамическая структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка. [1] Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.

Содержание

Виды связных списков

Линейный связный список

Односвязный список (Однонаправленный связный список)

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

Двусвязный список (Двунаправленный связный список)

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

XOR-связный список

Кольцевой связный список

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

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

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

Список с пропусками

Развёрнутый связный список

Пример реализации на Java

Достоинства

Недостатки

Примечания

См. также

Полезное

Смотреть что такое «Связный список» в других словарях:

связный список — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN linked list … Справочник технического переводчика

Развёрнутый связный список — список, каждый физический элемент которого содержит несколько логических (обычно в виде массива, что … Википедия

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

Список с пропусками — (англ. Skip List) вероятностная структура данных, основанная на нескольких параллельных отсортированных связных списках с эффективностью, сравнимой с двоичным деревом (порядка O(log n) среднее время для большинства операций). В основе… … Википедия

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

Список заголовков HTTP — HTTP Постоянное соединение · Сжатие · HTTPS Методы OPTIONS · GET · HEAD · POST · PUT · DELETE · TRACE · CONNECT · PATCH Заголовки Cookie · ETag · Location · Referer DNT · X Forwarded For … Википедия

Двусвязный список — В информатике, cвязный список структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующее и/или предыдущее поле. Принципиальным преимуществом перед массивом является… … Википедия

Односвязный список — В информатике, cвязный список структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующее и/или предыдущее поле. Принципиальным преимуществом перед массивом является… … Википедия

Связанный список — В информатике, cвязный список структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующее и/или предыдущее поле. Принципиальным преимуществом перед массивом является… … Википедия

Источник

Список

Связный список (англ. 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** для итерации указателей на элементы списка. Всё остальное вытекает оттуда: отпадает необходимость в специальных случаях или ветвлениях. Достаточно одного итератора, чтобы найти и удалить целевой элемент. И оказывается, что тот же подход обеспечивает элегантное решение для вставки вообще и для вставки перед существующим элементом в частности.

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

Источник

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

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(). И рассматриваем уже три случая:

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

Источник