Абстрактный тип данных лишь описывает, какие действия можно совершать с переменными конкретного типа. Он определяет список операций, но не объясняет, как они выполняются. Со структурами данных — обратная ситуация: они описывают, как данные организованы и как к ним получить доступ в памяти компьютера. Структуры данных обеспечивают реализацию АТД в модулях обработки данных.
Есть множество разных способов реализации АТД, потому что существуют самые разные структуры данных. Выбор реализации АТД, которая использует структуру данных, лучше соответствующую вашим потребностям, имеет существенное значение для создания эффективных компьютерных программ. Далее мы рассмотрим наиболее распространенные структуры данных и узнаем об их сильных и слабых сторонах.
Массив
Массив (array) — это самый простой способ хранения набора элементов в памяти компьютера. Он заключается в выделении единого пространства в памяти и последовательной записи в него ваших элементов. Конец последовательности отмечается специальным маркером NULL (рис. 4.1).
Рис. 4.1. Массив в памяти компьютера
Каждый объект в массиве занимает такой же объем памяти, что и любой другой. Представим массив, начинающийся с адреса ячейки памяти s, где каждый элемент занимает b байт. Чтобы получить n-й элемент, нужно извлечь b байт, начиная с позиции в памяти s + (b × n).
Это позволяет напрямую обращаться к любому элементу массива. Массив наиболее полезен для реализации стека, однако он может также использоваться для списков и очередей. Массивы легко программируются и имеют преимущество, позволяя мгновенно обращаться к любым элементам. Но есть у них и недостатки.
Может оказаться практически нецелесообразным выделять большие непрерывные блоки памяти. Если вам нужно наращивать массив, то в памяти может не оказаться смежного с ним достаточного большого пространства. Удаление элемента из середины массива сопряжено с определенными проблемами: вам придется сдвинуть все последующие элементы на одну позицию к началу либо отметить пространство памяти удаленного элемента как свободное. Ни один из этих вариантов не желателен. Аналогично вставка элемента внутрь массива вынудит вас сдвинуть все последующие элементы на одну позицию к концу.
Связный список
Cвязный список (linked list) позволяет хранить элементы в цепи ячеек, которые не обязательно должны находиться в последовательных адресах памяти. Память для ячеек выделяется по мере необходимости. Каждая ячейка имеет указатель, сообщающей об адресе следующей в цепи. Ячейка с пустым указателем (NULL) отмечает конец цепи (рис. 4.2).
Связные списки используются для реализации стеков, списков и очередей. При наращивании связного списка не возникает никаких проблем: любая ячейка может храниться в любой части памяти. Таким образом, размер списка ограничен только объемом имеющейся свободной памяти. Также не составит труда вставить элементы в середину списка или удалить их — достаточно просто изменить указатели ячеек (рис. 4.3).
Рис. 4.2. Связный список в памяти компьютера
Рис. 4.3. Добавление элемента между B и C. Удаление C
Связный список тоже имеет свои недостатки: мы не можем сразу получить n-й элемент. Сначала придется прочитать первую ячейку, извлечь из нее адрес второй ячейки, затем прочитать вторую ячейку, извлечь из нее указатель на следующую ячейку и т. д., пока мы не доберемся до n-й ячейки.
Кроме того, когда известен адрес всего одной ячейки, не так просто ее удалить или переместиться по списку назад. Не имея другой информации, нельзя узнать адрес предыдущей ячейки в цепи.
Двусвязный список
Двусвязный список (double linked list) — это связный список, где ячейки имеют два указателя: один на предыдущую ячейку, другой — на следующую (рис. 4.4).
Рис. 4.4. Двусвязный список в памяти компьютера
Он обладает тем же преимуществом, что и связный список: не требует предварительного выделения большого блока памяти, потому что пространство для новых ячеек может выделяться по мере необходимости. При этом дополнительные указатели позволяют двигаться по цепи ячеек вперед и назад. В таком случае, если известен адрес всего одной ячейки, мы сможем быстро ее удалить.
И тем не менее мы по-прежнему не имеем прямого доступа к n-му элементу. Кроме того, для поддержки двух указателей в каждой ячейке требуется более сложный код и больше памяти.
Массивы против связных списков
Языки программирования с богатым набором средств обычно включают встроенные реализации списка, очереди, стека и других АТД. Эти реализации часто основаны на некоторой стандартной структуре данных. Некоторые из них могут даже автоматически переключаться с одной структуры данных на другую во время выполнения программ, в зависимости от способа доступа к данным.
Когда производительность не является проблемой, мы можем опереться на эти универсальные реализации АТД и не переживать по поводу структур данных. Но когда производительность должна быть оптимальной либо когда вы имеете дело с низкоуровневым языком, не имеющим таких встроенных средств, вы сами должны решать, какие структуры данных использовать. Проанализируйте операции, посредством которых вы будете обрабатывать информацию, и выберите реализацию с надлежащей структурой данных. Связные списки предпочтительнее массивов, когда:
• нужно, чтобы операции вставки и удаления выполнялись чрезвычайно быстро;
• не требуется произвольный доступ к данным;
• приходится вставлять или удалять элементы между других элементов;
• заранее не известно количество элементов (оно будет расти или уменьшится по ходу выполнения программы).
Массивы предпочтительнее связных списков, когда:
• нужен произвольный доступ к данным;
• нужен очень быстрый доступ к элементам;
• число элементов не изменяется во время выполнения программы, благодаря чему легко выделить непрерывное пространство памяти.
Дерево
Как и связный список, дерево (tree) использует элементы, которым для хранения объектов не нужно располагаться в физической памяти непрерывно. Ячейки здесь тоже имеют указатели на другие ячейки, однако, в отличие от связных списков, они располагаются не линейно, а в виде ветвящейся структуры. Деревья особенно удобны для иерархических данных, таких как каталоги с файлами или система субординации (рис. 4.5).
В терминологии деревьев ячейка называется узлом, а указатель из одной ячейки на другую — ребром. Самая первая ячейка — это корневой узел, он единственный не имеет родителя. Все остальные узлы в деревьях должны иметь строго одного родителя[47].
Два узла с общим родителем называются братскими. Родитель узла, прародитель, прапрародитель (и т. д. вплоть до корневого узла) — это предки. Аналогично дочерние узлы, внуки, правнуки (и т. д. вплоть до нижней части дерева) называются потомками.
Узлы, не имеющие дочерних узлов, — это листья (по аналогии с листьями настоящего дерева ). Путь между двумя узлами определяется множеством узлов и ребер.
Уровень узла — это длина пути от него до корневого узла, высота дерева — уровень самого глубокого узла в дереве (рис. 4.6). И, наконец, множество деревьев называется лесом.
Рис. 4.5. Дерево происхождения индоевропейских языков
Рис. 4.6. Листья этого дерева представляют современные языки
Двоичное дерево поиска
Двоичное дерево поиска (binary search tree) — это особый тип дерева, поиск в котором выполняется особенно эффективно. Узлы в двоичном дереве поиска могут иметь не более двух дочерних узлов. Кроме того, узлы располагаются согласно их значению/ключу. Дочерние узлы слева от родителя должны быть меньше него, а справа — больше (рис. 4.7).
Рис. 4.7. Пример двоичного дерева поиска
Если дерево соблюдает это свойство, в нем легко отыскать узел с заданным ключом/значением:
function find_node(binary_tree, value)
node ← binary_tree.root_node
····while node
········if node.value = value
············return node
········if value > node.value
············node ← node.right
········else
············node ← node.left
····return "NOT FOUND"
Чтобы вставить элемент, находим последний узел, следуя правилам построения дерева поиска, и подключаем к нему новый узел справа или слева:
function insert_node(binary_tree, new_node)
····node ← binary_tree.root_node
····while node
········last_node ← node
········if new_node.value > node.value
············node ← node.right
········else
············node ← node.left
····if new_node.value > last_node.value
········last_node.right ← new_node
····else
········last_node.left ← new_node
Балансировка дерева. Если вставить в двоичное дерево поиска слишком много узлов, в итоге получится очень высокое дерево, где большинство узлов имеют всего один дочерний узел. Например, если последовательно вставлять узлы с ключами/значениями, которые всегда больше предыдущих, в итоге получится нечто, похожее на связный список. Однако мы можем перестроить узлы в дереве так, что его высота уменьшится. Эта процедура вызывается балансировкой дерева. Идеально сбалансированное дерево имеет минимальную высоту (рис. 4.8).
Рис. 4.8. Одно и то же двоичное дерево поиска с разной балансировкой: сбалансированное плохо, средне и идеально
Большинство операций с деревом требует обхода узлов по ссылкам, пока не будет найден конкретный узел. Чем больше высота дерева, тем длиннее средний путь между узлами и тем чаще приходится обращаться к памяти. Поэтому важно уменьшать высоту деревьев. Идеально сбалансированное двоичное дерево поиска можно создать из сортированного списка узлов следующим образом:
function build_balanced(nodes)
····if nodes is empty
········return NULL
····middle ← nodes.length/2
····left ← nodes.slice(0, middle — 1)
····right ← nodes.slice(middle + 1, nodes.length)
····balanced ← BinaryTree.new(root=nodes[middle])
····balanced.left ← build_balanced(left)
····balanced.right ← build_balanced(right)
····return balanced
Рассмотрим двоичное дерево поиска с n узлами и с максимально возможной высотой n. В этом случае оно похоже на связный список. Минимальная высота идеально сбалансированного дерева равняется log2n. Сложность поиска элемента в дереве пропорциональна его высоте. В худшем случае, чтобы найти элемент, придется опускаться до самого нижнего уровня листьев. Поиск в сбалансированном дереве с n элементами, следовательно, имеет O(log n). Вот почему эта структура данных часто выбирается для реализации множеств (где предполагается проверка присутствия элементов) и словарей (где нужно искать пары «ключ — значение»).
Однако балансировка дерева — дорогостоящая операция, поскольку требует сортировки всех узлов. Если делать балансировку после каждой вставки или удаления, операции станут значительно медленнее. Обычно деревья подвергаются этой процедуре после нескольких вставок и удалений. Но балансировка от случая к случаю является разумной стратегией только в отношении редко изменяемых деревьев.
Для эффективной обработки двоичных деревьев, которые изменяются часто, были придуманы сбалансированные двоичные деревья (self-balancing binary tree)[48]. Их процедуры вставки или удаления элементов гарантируют, что дерево остается сбалансированным. Красно-черное дерево (red-black tree) — это хорошо известный пример сбалансированного дерева, которое окрашивает узлы красным либо черным цветом в зависимости от стратегии балансировки[49]. Красно-черные деревья часто используются для реализации словарей: словарь может подвергаться интенсивной правке, но конкретные ключи в нем по-прежнему будут находиться быстро вследствие балансировки.
AVL-дерево (AVL tree) — это еще один подвид сбалансированных деревьев. Оно требует немного большего времени для вставки и удаления элементов, чем красно-черное дерево, но, как правило, обладает лучшим балансом. Это означает, что оно позволяет получать элементы быстрее, чем красно-черное дерево. AVL-деревья часто используются для оптимизации производительности в сценариях, для которых характерна высокая интенсивность чтения.
Данные часто хранятся на магнитных дисках, которые считывают их большими блоками. В этих случаях используется обобщенное двоичное B-дерево (B-tree). В таких деревьях узлы могут хранить более одного элемента и иметь более двух дочерних узлов, что позволяет им эффективно оперировать данными в больших блоках. Как мы вскоре увидим, B-деревья обычно используются в системах управления базами данных.
Двоичная куча
Двоичная куча (binary heap) — особый тип двоичного дерева поиска, в котором можно мгновенно найти самый маленький (или самый большой) элемент. Эта структура данных особенно полезна для реализации очередей с приоритетом. Операция получения минимального (или максимального) элемента имеет сложность O(1), потому что он всегда является корневым узлом дерева. Поиск и вставка узлов здесь по-прежнему стоят O(log n). Кучи подчиняются тем же правилам размещения узлов, что и двоичные деревья поиска, но есть одно ограничение: родительский узел должен быть больше (либо меньше) обоих своих дочерних узлов (рис. 4.9).
Рис. 4.9. Узлы, организованные как двоичная куча max-heap (вверху) и двоичная куча min-heap (внизу)[50]
Обращайтесь к двоичной куче всегда, когда планируете часто иметь дело с максимальным (либо минимальным) элементом множества.
Граф
Граф (graph) аналогичен дереву. Разница состоит в том, что у него нет ни дочерних, ни родительских узлов (вершин) и, следовательно, нет корневого узла. Данные свободно организованы в виде узлов (вершин) и дуг (ребер) так, что любой узел может иметь произвольное число входящих и исходящих ребер.
Это самая гибкая из всех структур, она используется для представления почти всех типов данных. Например, графы идеальны для социальной сети, где узлы — это люди, а ребра — дружеские связи.
Хеш-таблица
Хеш-таблица (hash table) — это структура данных, которая позволяет находить элементы за O(1). Поиск занимает постоянное время вне зависимости от того, ищете вы среди 10 млн элементов или всего среди 10.
Так же, как массив, хеш для хранения данных требует предварительного выделения большого блока последовательной памяти. Но, в отличие от массива, его элементы хранятся не в упорядоченной последовательности. Позиция, занимаемая элементом, «волшебным образом» задается хеш-функцией. Это специальная функция, которая на входе получает данные, предназначенные для хранения, и возвращает число, кажущееся случайным. Оно интерпретируется как позиция в памяти, куда будет помещен элемент.
Это позволяет нам получать элементы немедленно. Заданное значение сначала пропускается через хеш-функцию. Она выдает точную позицию, где элемент должен находиться в памяти. Если элемент был сохранен, то вы найдете его в этой позиции.
Однако с хеш-таблицами возникают проблемы: иногда хеш-функция возвращает одинаковую позицию для разных входных данных. Такая ситуация называется хеш-коллизией. Когда она происходит, все такие элементы должны быть сохранены в одной позиции в памяти (эта проблема решается, например, посредством связного списка, который начинается с заданного адреса). Хеш-коллизии влекут за собой издержки процессорного времени и памяти, поэтому их желательно избегать.
Хорошая хеш-функция должна возвращать разные значения для разных входных данных. Следовательно, чем шире диапазон значений, которые может вернуть хеш-функция, тем больше будет доступно позиций для данных и меньше вероятность возникновения хеш-коллизии. Поэтому нужно гарантировать, чтобы в хеш-таблице оставалось незанятым по крайней мере 50 % пространства. В противном случае коллизии начнут происходить слишком часто и производительность хеш-таблицы значительно упадет.
Хеш-таблицы часто используются для реализации словарей и множеств. Они позволяют выполнять операции вставки и удаления быстрее, чем структуры данных, основанные на деревьях.
С другой стороны, для корректной работы хеш-таблицы требуют выделения очень большого блока непрерывной памяти.
Подведем итоги