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