В информатике связанная структура данных — это структура данных , которая состоит из набора записей данных ( узлов ), связанных вместе и организованных ссылками ( линками или указателями ). Связь между данными также можно назвать соединителем .
В связанных структурах данных ссылки обычно рассматриваются как специальные типы данных , которые можно только разыменовывать или сравнивать на предмет равенства. Таким образом, связанные структуры данных противопоставляются массивам и другим структурам данных, требующим выполнения арифметических операций над указателями. Это различие сохраняется даже тогда, когда узлы фактически реализованы как элементы одного массива, а ссылки фактически являются индексами массива : пока над этими индексами не выполняется арифметика, структура данных по сути является связанной.
Связывание может быть выполнено двумя способами — с использованием динамического выделения памяти и с использованием связывания индексов массива.
Связанные структуры данных включают связанные списки , деревья поиска , деревья выражений и многие другие широко используемые структуры данных. Они также являются ключевыми строительными блоками для многих эффективных алгоритмов, таких как топологическая сортировка [1] и объединение множеств-поиск . [2]
Связанный список — это набор структур, упорядоченных не по их физическому размещению в памяти, а по логическим связям, которые хранятся как часть данных в самой структуре. Не обязательно, чтобы он хранился в соседних ячейках памяти. Каждая структура имеет поле данных и поле адреса. Поле адреса содержит адрес своего преемника .
Связанный список может быть односвязным, двусвязным или многосвязным, а также линейным или кольцевым.
Это пример класса узла, используемого для хранения целых чисел в реализации связанного списка на Java:
public class IntNode { public int value ; public IntNode link ; public IntNode ( int v ) { value = v ; } } Это пример структуры, используемой для реализации связанного списка в языке C:
структурный узел { int val ; структурный узел * следующий ; }; Вот пример использования typedef :
typedef struct узел узел ; struct node { int val ; node * next ; }; Примечание: Подобная структура, содержащая элемент, указывающий на ту же структуру, называется самореферентной структурой.
Это пример структуры класса узла, используемой для реализации связанного списка в C++:
класс Узел { int val ; Узел * следующий ; }; Дерево поиска — это древовидная структура данных, в узлах которой могут храниться значения данных из некоторого упорядоченного набора , так что при упорядоченном обходе дерева узлы посещаются в порядке возрастания хранимых значений.
По сравнению с массивами, связанные структуры данных обеспечивают большую гибкость в организации данных и выделении для них пространства. В массивах размер массива должен быть указан точно в начале, что может быть потенциальной тратой памяти или произвольным ограничением, которое впоследствии каким-то образом затруднит функциональность. Связанная структура данных создается динамически и никогда не должна быть больше, чем требуется программе. Она также не требует угадывания во время создания с точки зрения того, сколько места должно быть выделено. Это функция, которая является ключевой для предотвращения траты памяти.
В массиве элементы массива должны находиться в непрерывной (связанной и последовательной) части памяти. Но в связанной структуре данных ссылка на каждый узел дает пользователям информацию, необходимую для поиска следующего. Узлы связанной структуры данных также могут быть перемещены по отдельности в разные места в физической памяти, не влияя на логические связи между ними, в отличие от массивов. При должной осторожности определенный процесс или поток может добавлять или удалять узлы в одной части структуры данных, даже если другие процессы или потоки работают над другими частями.
С другой стороны, доступ к любому конкретному узлу в связанной структуре данных требует следования цепочке ссылок, которые хранятся в каждом узле. Если структура имеет n узлов, и каждый узел содержит не более b ссылок, будут некоторые узлы, которые не могут быть достигнуты менее чем за log b n шагов, замедляя процесс доступа к этим узлам - это иногда представляет собой значительное замедление, особенно в случае структур, содержащих большое количество узлов. Для многих структур некоторые узлы могут потребовать в худшем случае до n −1 шагов. Напротив, многие структуры данных массива позволяют получить доступ к любому элементу с постоянным числом операций, независимо от числа записей.
В целом реализация этих связанных структур данных осуществляется через динамические структуры данных . Это дает нам возможность снова использовать определенное пространство. Память может использоваться более эффективно с использованием этих структур данных. Память выделяется в соответствии с потребностью, и когда память больше не нужна, происходит освобождение.
Связанные структуры данных также могут повлечь за собой существенные накладные расходы на выделение памяти (если узлы выделяются индивидуально) и нарушить алгоритмы страничного обмена памятью и кэширования процессора (поскольку они, как правило, имеют плохую локальность ссылок ). В некоторых случаях связанные структуры данных также могут использовать больше памяти (для полей ссылок), чем конкурирующие структуры массивов. Это происходит потому, что связанные структуры данных не являются смежными. Экземпляры данных могут быть найдены по всей памяти, в отличие от массивов.
В массивах доступ к n-му элементу возможен немедленно, тогда как в связанной структуре данных нам приходится следовать нескольким указателям, поэтому время доступа к элементу зависит от того, где в структуре находится элемент.
В некоторых теоретических моделях вычислений , которые накладывают ограничения связанных структур, таких как указательная машина , многие проблемы требуют большего количества шагов, чем в модели машины с неограниченным произвольным доступом .