Связанная структура данных

Не путать со связанными данными .

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

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

Связывание можно выполнить двумя способами — с использованием динамического выделения и с помощью связывания индексов массива.

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

Распространенные типы связанных структур данных

Связанные списки

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

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

Основные свойства

• Объекты, называемые узлами , связаны в линейную последовательность.
• Ссылка на первый узел списка сохраняется всегда. Это называется «голова» или «перед».

Связный список с тремя узлами содержит по два поля: целое значение и ссылку на следующий узел.

Связанный список с одним узлом.

Пример на Java

Это пример класса узла, используемого для хранения целых чисел в Java-реализации связанного списка:

public class IntNode {
     public int value;
     public IntNode link;
     public IntNode(int v) { value = v; }
}

Пример на языке C

Это пример структуры, используемой для реализации связанного списка в C:

struct node
{
	int val;
	struct node *next;
};

Это пример использования typedefs :

typedef struct node node;

struct node
{
	int val;
	node *next;
};

Примечание. Подобная структура, содержащая элемент, указывающий на ту же структуру, называется самореферентной структурой.

Пример на С++

Это пример структуры класса узла, используемой для реализации связанного списка в C++:

class Node
{
	int val;
	Node *next;
};

Поиск деревьев

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

Основные свойства

• Объекты, называемые узлами, хранятся в упорядоченном наборе.
• Обход по порядку обеспечивает считывание данных в дереве по возрастанию.

Преимущества и недостатки

Связанный список против массивов

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

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

С другой стороны, доступ к любому конкретному узлу в связанной структуре данных требует следования цепочке ссылок, которые хранятся в каждом узле. Если структура имеет n узлов, и каждый узел содержит не более b связей, то будут некоторые узлы, до которых невозможно добраться менее чем за log _b n шагов, что замедляет процесс доступа к этим узлам - иногда это представляет собой значительное замедление, особенно в случае структур, содержащих большое количество узлов. Для многих структур некоторым узлам может потребоваться наихудший случай до n -1 шагов. Напротив, многие структуры данных массива допускают доступ к любому элементу с постоянным количеством операций, независимо от количества записей.

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

Общие недостатки

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

В массивах доступ к n-му элементу возможен немедленно, тогда как в связанной структуре данных нам приходится следовать нескольким указателям, поэтому время доступа к элементу варьируется в зависимости от того, в каком месте структуры находится элемент.

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

См. также

• Список структур данных