Что такое связанная структура данных?

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

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

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

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

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

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