в какой структуре данных вставка и удаление происходят на одном конце
Важнейшие структуры данных, которые вам следует знать к своему собеседованию по программированию
Никлаус Вирт, швейцарский ученый-информатик, в 1976 году написал книгу под названием «Алгоритмы + Структуры данных = Программы».
Через 40 с лишним лет это тождество остается в силе. Вот почему соискатели, желающие стать программистами, должны продемонстрировать, что знают структуры данных и умеют их применять.
Практически во всех задачах от кандидата требуется глубокое понимание структур данных. При этом не столь важно, выпускник ли вы (закончили университет или курсы программирования), либо у вас за плечами десятки лет опыта.
Иногда в вопросах на интервью прямо упоминается та или иная структура данных, например, «дано двоичное дерево». В других случаях задача формулируется более завуалированно, например, «нужно отследить, сколько у нас книг от каждого автора».
Изучение структур данных — незаменимое дело, даже если вы просто стараетесь профессионально совершенствоваться на нынешней работе. Начнем с основ.
Переведено в Alconost
Что такое структура данных?
Если коротко, структура данных — это контейнер, информация в котором скомпонована характерным образом. Благодаря такой «компоновке», структура данных будет эффективна в одних операциях и неэффективна — в других. Наша цель — разобраться в структурах данных таким образом, чтобы вы могли выбрать из них наиболее подходящую для решения конкретной стоящей перед вами задачи.
Зачем нужны структуры данных?
Поскольку структуры данных используются для хранения информации в упорядоченном виде, а данные — самый важный феномен в информатике, истинная ценность структур данных очевидна.
Не важно, какую именно задачу вы решаете, так или иначе вам придется иметь дело с данными, будь то зарплата сотрудника, биржевые котировки, список продуктов для похода в магазин или обычный телефонный справочник.
В зависимости от конкретного сценария, данные нужно хранить в подходящем формате. У нас в распоряжении — ряд структур данных, обеспечивающих нас такими различными форматами.
Наиболее распространенные структуры данных
Сначала давайте перечислим наиболее распространенные структуры данных, а затем разберем каждую по очереди:
Массивы
Массив — это простейшая и наиболее распространенная структура данных. Другие структуры данных, например, стеки и очереди, производны от массивов.
Здесь показан простой массив размером 4, содержащий элементы (1, 2, 3 и 4).
Каждому элементу данных присваивается положительное числовое значение, именуемое индексом и соответствующее положению этого элемента в массиве. В большинстве языков программирования элементы в массиве нумеруются с 0.
Существуют массивы двух типов:
Простейшие операции с массивами
Вопросы по массивам, часто задаваемые на собеседованиях
Стеки
Всем известна знаменитая опция «Отмена», предусмотренная почти во всех приложениях. Задумывались когда-нибудь, как она работает? Смысл такой: в программе сохраняются предшествующие состояния вашей работы (количество сохраняемых состояний ограничено), причем, они располагаются в памяти в таком порядке: последний сохраненный элемент идет первым. Одними массивами такую задачу не решить. Именно здесь нам пригодится стек.
Стек можно сравнить с высокой стопкой книг. Если вам нужна какая-то книга, лежащая около центра стопки, вам сначала придется снять все книги, лежащие выше. Именно так работает принцип LIFO (Последним пришел — первым вышел).
Так выглядит стек, содержащий три элемента данных (1, 2 и 3), где 3 находится сверху — поэтому будет убран первым:
Простейшие операции со стеком:
Вопросы о стеке, часто задаваемые на собеседованиях
Очереди
Очередь, как и стек — это линейная структура данных, элементы в которой хранятся в последовательном порядке. Единственное существенное отличие между стеком и очередью заключается в том, что в очереди вместо LIFO действует принцип FIFO (Первым пришел — первым вышел).
Идеальный реалистичный пример очереди — это и есть очередь покупателей в билетную кассу. Новый покупатель становится в самый хвост очереди, а не в начало. Тот же, кто стоит в очереди первым, первым приобретет билет и первым ее покинет.
Вот изображение очереди с четырьмя элементами данных (1, 2, 3 и 4), где 1 идет первым и первым же покинет очередь:
Простейшие операции с очередью
Вопросы об очередях, часто задаваемые на собеседованиях
Связный список
Связный список — еще одна важная линейная структура данных, на первый взгляд напоминающая массив. Однако, связный список отличается от массива по выделению памяти, внутренней структуре и по тому, как в нем выполняются базовые операции вставки и удаления.
Связный список напоминает цепочку узлов, в каждом из которых содержится информация: например, данные и указатель на следующий узел в цепочке. Есть головной указатель, соответствующий первому элементу в связном списке, и, если список пуст, то он направлен просто на null (ничто).
При помощи связных списков реализуются файловые системы, хеш-таблицы и списки смежности.
Вот так можно наглядно изобразить внутреннюю структуру связного списка:
Существуют такие типы связных списков:
Простейшие операции со связными списками:
Вопросы о связных списках, часто задаваемые на собеседованиях:
Графы
Граф — это множество узлов, соединенных друг с другом в виде сети. Узлы также называются вершинами. Пара (x,y) называется ребром, это означает, что вершина x соединена с вершиной y. Ребро может иметь вес/стоимость — показатель, характеризующий, насколько затратен переход от вершины x к вершине y.
Вопросы о графах, часто задаваемые на собеседованиях:
Деревья
Дерево — это иерархическая структура данных, состоящая из вершин (узлов) и ребер, которые их соединяют. Деревья подобны графам, однако, ключевое отличие дерева от графа таково: в дереве не бывает циклов.
Деревья широко используются в области искусственного интеллекта и в сложных алгоритмах, выступая в качестве эффективного хранилища информации при решении задач.
Вот схема простого дерева и базовая терминология, связанная с этой структурой данных:
Существуют деревья следующих типов:
Вопросы о деревьях, часто задаваемые на собеседованиях:
Найдите высоту двоичного дерева
Найдите k-ное максимальное значение в двоичном дереве поиска
Найдите узлы, расположенные на расстоянии “k” от корня
Найдите предков заданного узла в двоичном дереве
Бор, также именуемый «префиксное дерево» — это древовидная структура данных, которая особенно эффективна при решении задач на строки. Она обеспечивает быстрое извлечение данных и чаще всего применяется для поиска слов в словаре, автозавершений в поисковике и даже для IP-маршрутизации.
Вот как три слова «top» (верх), «thus» (следовательно), and «their» (их) хранятся в бору:
Слова располагаются в направлении сверху вниз, и зеленые узлы «p», «s» и «r» завершают, соответственно, слова «top», «thus» и «their».
Вопросы о борах, часто задаваемые на собеседованиях:
Хеш-таблица
Хеширование — это процесс, применяемый для уникальной идентификации объектов и сохранения каждого объекта по заранее вычисленному индексу, именуемому его «ключом». Таким образом, объект хранится в виде «ключ-значение», а коллекция таких объектов называется «словарь». Каждый объект можно искать по его ключу. Существуют разные структуры данных, построенные по принципу хеширования, но чаще всего из таких структур применяется хеш-таблица.
Как правило, хеш-таблицы реализуются при помощи массивов.
Производительность хеширующей структуры данных зависит от следующих трех факторов:
Вопросы о хешировании, часто задаваемые на собеседованиях:
Удачи и интересного обучения! 🙂
Перевод статьи выполнен в Alconost.
Alconost занимается локализацией игр, приложений и сайтов на 68 языков. Переводчики-носители языка, лингвистическое тестирование, облачная платформа с API, непрерывная локализация, менеджеры проектов 24/7, любые форматы строковых ресурсов.
Мы также делаем рекламные и обучающие видеоролики — для сайтов, продающие, имиджевые, рекламные, обучающие, тизеры, эксплейнеры, трейлеры для Google Play и App Store.
Структуры данных: список, который умеет всё*
* Под всё имеется в виду относительно быстрое выполнение операций над единичным элементом массива.
Структур данных, которые реализуют список полно. У всех есть свои достоинства и недостатки. Например в мире Java — в зависимости от необходимых операций — можно использовать:
Возможно, кто-то догадался, что можно взять TreeList, который умеет быстро вставлять/удалять элементы в середине списка и добавить к нему HashMap из объекта в индекс в TreeList для быстрого выполнения indexOf(obj). И это будет простое, изящное, но неверное решение. Ведь при добавлении в середину или удалении из середины нужно будет пересчитать индексы, в среднем, для половины элементов. Это ухудшит производительность до O(n).
Дальше я расскажу о структуре данных, которая может всё из перечисленного выше. Которая выполняет любую операцию над одним элементом за O(log(n)) времени. Ну почти — за логарифм выполняется в том случае, когда все объекты в списке различны. Если в списке есть одинаковые объекты, то возможно проседание производительности вплоть до O(log(n) ^ 2).
Предупрежу сразу, что я не буду здесь расписывать код. Он может быть достаточно сложен для статьи. Но он есть, написан на Java. За основу взят класс TreeList из apache common-collections. Pull request уже есть, но на момент написания статьи ещё не влит.
Также я не буду описывать общеизвестные алгоритмы. Например, алгоритмы балансировки дерева. Большинству может быть достаточно принять на веру тот факт, что дерево можно держать сбалансированным. На понимание общей идеи это никак не влияет. Те, кто захотят узнать больше, без проблем найдут информацию. Но о некоторых базовых вещах очень коротко расскажу, т. к. без знания основ нельзя будет понять многие ключевые элементы.
Ссылки будут в конце.
Зачем это нужно
В самом деле, не так-то просто придумать ситуации, когда от списка нужно вот прям вообще всё. Вряд ли это какая-то супер необходимая структура, иначе о ней знали бы все. Однако несколько примеров, где такой список мог быть полезен можно привести.
Я осознаю, что многие из примеров надуманные. Всё или почти всё можно решить другим способом.
Кэширование и сжатие
Моя первоначальная задача, из-за которой я начал исследовать вопрос. Игрался со сжатием специфических данных и понадобился список для кэша объектов.
Идея следующая: при обработке очередного объекта ищем его в списке. Если не нашли — сохраняем объект и добавляем его в начало списка. Если нашли, то берём его индекс в списке и вместо объекта сохраняем только его индекс, после чего перемещаем объект в начало списка. Таким образом, объекты, которые встречаются часто будут получать маленькие индексы, а объекты, которые встретились всего один раз, со временем перемещаются в конец списка и удаляются.
Очередь
Если вместо обычной FIFO очереди для каких-то задач использовать подобную структуру, то можно делать следующие операции:
Таблица рекордов
Допустим, мы хотим хранить время, за которое игроки проходят уровень в какой-то игре. Игроков много и все они соревнуются, пытаясь показать минимальное время. Данные игроков можно положить в массив и отсортировать по времени. Пользуясь данной структурой можно:
Структура данных
Структура основана на дереве с неявным ключом. Именно на этом подходе основан, например, TreeList в apache common-collections. Для того чтобы двигаться дальше, надо понять как работает эта структура.
Дерево с неявным ключом
Дерево состоит из узлов (Nodes). Каждый узел содержит ссылку на объект, который хранится в узле и 2 ссылки на другие узлы: левый и правый. Самый верхний узел называется корневым. В самом простом случае узел выглядит примерно так:
В классическом бинарном дереве для каждого узла в левом поддереве все объекты меньшие, чем в текущем узле, а в правом — большие. Например:
Но для нашей цели такое дерево не подходит. Нам не надо хранить объекты отсортированными, но надо иметь к ним доступ по индексу, как в массиве.
Как можно поместить массив в дерево? Давайте выберем элемент с индексом i из середины массива. Поместим в корневой узел i-й элемент из массива. Из корневого узла выходят 2 поддерева. В левое поддерево помещаем половину массива с индексом i. Как это сделать? Точно так же: выбираем в подмассиве какой-то элемент из середины, помещаем этот элемент в узел, получаем еще 2 подмассива поменьше. И так пока не поместим все элементы массива в узлы дерева.
Например, так может выглядеть массив с элементами [“q”, “w”, “e”, “r”, “t”, “y”, “u”]:
Средний элемент в массиве “r”, его помещаем в корневой узел. Два подмассива [“q”, “w”, “e”] и [“t”, “y”, “u”] помещаются в левое и правое поддерево. Для этого из подмассивов выбираются центральные элементы, в нашем случае это “w” и “y”, они и попадают в узлы следующего уровня. И т. д.
В нашем случае дерево сбалансировано, глубина всех поддеревьев одинаковая. Но это не обязательно должно быть так.
На картинке выше каждый узел помимо элемента и ссылок на левый и правые узлы содержит количество элементов всего поддерева. Эту информацию надо правильно обновлять при изменении дерева.
Давайте посмотрим, как в таком дереве найти, например, элемент с index = 4.
Мы начинаем обход с корневого узла (root, в нашем случае с элементом “r”). У нас есть 3 варианта: мы уже находимся на нужном узле, нужный узел слева, нужный узел справа. Для того чтобы понять, где искать нужный элемент, нужно сравнить размер левого поддерева (в нашем случае left.size = 3) и текущий индекс (в нашем случае 4). Если эти 2 числа равны, то мы нашли необходимый узел и искомый элемент в нём. Если размер левого поддерева больше, то необходимый узел в левом поддереве. Если меньше, то надо искать в правом поддереве, но нужно уменьшить искомый индекс: index = index — left.size — 1.
Поскольку в нашем случае left.size 0 то ищем в левом поддереве, перемещаемся к узлу с элементом “t”.
В этом узле нет левого поддерева, и его размер равен 0. index = left.size, а значит мы нашли узел с индексом 4 и можем достать из него искомый элемент “t”.
В псевдокоде это выглядит примерно так:
Я постарался описать ключевой принцип как поместить массив в дерево. Работает такая структура, конечно, медленнее классического массива, за O(log(n)) против O(1). Но у неё есть важное преимущество: добавление элемента в середину или удаление из середины работает тоже за O(log(n)) против O(n) у массива. Конечно, при условии, что дерево более-менее сбалансировано. Существует много алгоритмов поддержания дерева в почти сбалансированном виде. Например, красно-чёрное дерево, AVL дерево, Декартово дерево. Я не буду расписывать подробности балансировки дерева, для нас подойдёт любой алгоритм. Давайте просто считать, что дерево в среднем сбалансировано и его максимальная глубина не сильно отличается от минимальной.
Небольшая оптимизация
Подход описанный выше, с проверкой размера дерева слева удобен для восприятия, но можно сделать чуть более эффективно. Для того, чтобы не заглядывать каждый раз в левое поддерево можно вместо размера дерева хранить в узле его позицию относительно позиции его узла-родителя. Корневой узел хранит абсолютную позицию, которая совпадает с размером левого поддерева.
Эта оптимизация помимо более быстрого поиска элемента в списке даст более быстрый и простой поиск индекса у узла. Но, конечно, правильно обновлять позицию при изменении дерева стало чуть сложнее.
Добавляем индексирование
Итак, в дереве мы умеем брать элемент по индексу, менять его значение, добавлять элементы в середину и удалять. По сути, нам осталось добавить быстрый поиск индекса по значению, indexOf(obj). Тогда contains(obj) и remove(obj) будут решаться тривиально.
Но для начала давайте немного упростим задачу. Давайте сделаем структуру, которая хранит только уникальные элементы.
Для того чтобы что-то быстро искать обычно используют таблицу. В мире Java таблицы называются Map, у неё есть 2 основные реализации: HashMap и TreeMap. Ключом таблицы будет ссылка на объект, а значением ссылка на его узел:
Т.е. структура состоит из двух частей: само дерево-список и таблица со ссылками на объекты и узлы этого дерева. При обновлении дерева надо обновлять и таблицу. Детально расписывать процесс не буду. Интуитивно он должен быть понятен: добавили узел — положили его же в таблицу, удалили узел — удалили из таблицы. На практике же есть нюансы с балансировкой дерева: алгоритм должен менять ссылки между узлами, а не перемещать объекты между узлами. Иначе придётся делать много обновлений в таблице и упадёт производительность.
Ок, будем считать, что мы умеем быстро находить узел по элементу, который в нём содержится. И что? Нам нужно найти его индекс, а сделать этого пока нельзя. Но мы можем усложнить класс узла так, чтобы он содержал не только ссылки на левый и правый узлы, но и на своего родителя:
Конечно, обновление дерева ещё немного усложняется, ведь нам теперь нужно аккуратно обновлять ссылку на родителя. Зато теперь, зная узел, мы можем пройти по дереву вверх и вычислить индекс любого узла. Если мы использовали оптимизацию из предыдущей главы, то нам надо просто посчитать сумму позиций от текущего узла до корневого.
Для списка, содержащего уникальные элементы задачу можно считать решенной.
Правда, у нас появилась небольшая проблемка. Допустим, мы вызываем set(index, obj). Мы можем легко заменить один элемент в узле на другой, но только в том случае, если нового элемента в списке еще нет. А если есть, то что делать? Удалить лишний элемент из старой позиции и положить в новую? Или наоборот, сначала добавить, а потом удалить? Результат может быть разным. А можно вообще ничего не делать или бросать исключение. Идеального решения нет.
Отсортировать стандартными методами такой список тоже, скорее всего, не получится. Ведь алгоритм сортировки не будет знать про необходимость уникальности объектов и при перемещении элементов в списке будет создавать дубликаты.
Убираем уникальность
Ок, усложняем ещё, разрешим хранить одинаковые объекты. Очевидно, что надо что-то делать с таблицей. Первая идея хранить в ней список узлов кажется не очень хорошей: с увеличением длины списка будет ухудшаться производительность. Вплоть до O(n), если все элементы списка будут одинаковыми.
Тогда давайте попробуем хранить в таблице вместо списка отсортированное дерево узлов. Отсортированное по позиции в списке.
Тогда вставка/удаление в/из TreeSet размера m будет происходить за log(m) сравнений позиций узлов, а каждое сравнение будет происходить за log(n) времени. Итоговая сложность вставки или удаления в подобную структуру будет происходить за O(log(n) * (1 + log(m))), где n это общее количество элементов в списке, а m это количество элементов в списке равных вставляемому/удаляемому. В худшем случае, когда все элементы равны друг другу, получим сложность O(log(n) ^ 2).
Внимательный читатель наверняка возразит: а как же иммутабельность? Мы ведь не можем изменять объекты, если они являются ключами таблицы? В общем случае так и есть. Однако для дерева, которое хранит в ключах отсортированные объекты, помимо стандартных правил для сравнений, достаточно сохранять инвариант: если a Код под спойлером
Для начала я сравнил скорость доставания случайного элемента из списка. Предупрежу сразу, что в данном тесте накладные расходы очень существенны. Результаты, приближающиеся к 100000 * 1000 операций в секунду сильно искажены.
Тут, как ни странно, самый большой интерес вызывает стандартный ArrayList. Теоретически скорость доставания из него должна быть константой и не зависеть от количество элементов. На практике производительность сначала держится около 90000 * 1000 операций в секунду (помним про накладные расходы), но при длине списка в несколько тысяч элементов начинает проседать. Виной тому всё более частый cache miss: в кэше процессора не оказывается нужных данных и нужно всё чаще ходить за данными в оперативную память. При миллионе элементов скорость прохождения теста ниже в 10 раз, но на практике проседание производительности еще больше.
TreeList, IndexedTreeList и IndexedTreeListSet ожидаемо показывают схожий результат. Ожидаемо сильно медленнее, чем ArrayList. Даже при маленьком количестве элементов TreeList в несколько раз медленнее, чем ArrayList, хотя тест показывает разницу всего в 2 раза.
Следующий тест addRemoveRandom. Здесь в каждом тесте я вставляю в случайную позицию элемент и удаляю из случайной позиции элемент.
Можно было предположить, что ArrayList работает быстрее на маленьких списках. Однако то, что он выигрывает в этом тесте на списках вплоть до 10000 элементов выглядит интересно. Видимо, System.arrayCopy очень хорошо оптимизирован и использует все возможности современных процессоров. Начиная с 10000 элементов специализированные структуры данных начинают выигрывать. При 1000000 элементов разница скорости в 30-50 раз.
IndexedTreeList и IndexedTreeListSet ожидаемо медленнее, чем TreeList. Примерно в 1.5 — 2 раза.
Оставшиеся 2 теста indexOfKnown и indexOfUnknown как раз должны продемонстрировать основную особенность данной структуры. Различие тестов в том, что в одном случае мы ищем элемент, который есть в списке, а в другом случае ищем элемент, которого в списке нет.
Здесь у ArrayList и TreeList почти без сюрпризов. С увеличением размера скорость падает практически линейно. Поиск элемента не из списка ожидаемо в 2 раза медленнее, чем поиск элемента из списка, т.к. надо пройти весь массив вместо половины в среднем.
А вот IndexedTreeList и IndexedTreeListSet здесь показывают ожидаемо хороший результат. Эти структуры данных показывают сравнимую с ArrayList скорость выполнения indexOf даже при 10 элементах. При 1000 элементах эти структуры быстрее в 10 раз, при 1000000 быстрее в 1000 раз. При поиске элемента, которого нет в списке они ожидаемо дают лучшую скорость, чем при поиске элемента из списка.
На что еще интересно обратить внимание, так это на проседание производительности у IndexedTreeList и IndexedTreeListSet в тесте indexOfUnknown. Тут ситуация аналогичная той, что была в тесте с ArrayList.get. Теоретически мы не должны были получить падение производительности, а на практике, из-за cache miss получили, причём существенно.
Вместо заключения
Я до сих пор не знаю, есть ли в предложенной структуре новизна или нет. С одной стороны, идея не сложная, если знать как работает дерево по неявному ключу. С другой стороны, описания структуры со такими свойствами я не встречал. А раз так, то есть смысл сделать структуру более известной, возможно, кому-то пригодится.
Но даже если это ещё один велосипед, то я постарался сделать его полезным. Pull request в common-collections создан, но на момент написания статьи ещё не влит. Зная, как медленно всё может происходить в open source, не удивлюсь, если процесс затянется на месяцы.
Несколько удивил результат сравнения производительности ArrayList и TreeList. Тесты показали, что TreeList нет смысла использовать на размерах списка до 10000 элементов. Было бы интересно попробовать b-tree вместо бинарного дерева. Эта структура должна более бережно использовать память и, скорее всего, быстрее работать. И под неё можно адаптировать идею с индексированием.
В любом случае, прикольно иметь в арсенале инструмент, который может (почти) всё с предсказуемой сложностью.
Часть 0.1. Поясняю за структуры данных (часть 1)
Привет, меня зовут Артем и я люблю программировать. Надеюсь, вы прочитали предыдущую, нулевую статью.
Что бы стать хорошим программистом (не веб-разработчиком, а хорошим программистом), вы в первую очередь должны понять, что программирование – это манипуляция данными. И то, насколько вы хорошо умеете обращаться с данными в зависимости от поставленной задачи, определяет, сможете ли вы создавать хорошие программы или нет. В интернете уже есть куча материала на тему структур данных и алгоритмов, но я попробую расписать весь этот материал по-своему. Возможно, это поможет кому-то лучше понять эту тему.
Начнем с определения понятия «сложность алгоритма» — это нам пригодится тут и в следующей статье про алгоритмы.
Если говорить простыми словами – то сложность алгоритма – это то, сколько действий нужно совершить данному алгоритму, чтобы выполнить определенную задачу. Чем больше действий нужно алгоритму, тем он сложнее, и тем он хуже (если существуют альтернативные алгоритмы с меньшей сложностью).
Например, представим ряд чисел – 12345. Нам нужно инвертировать порядок этих чисел (переставить числа так, чтобы вышло 54321). Представим, что алгоритму №1 нужно совершить 5 действий, чтобы переставить числа, а алгоритму №2 – 10. Из этого можем сделать вывод, что в данном случае алгоритм №1 будет предпочтительней для нас.
Но это говоря простыми словами. В реальности на выбор алгоритма также влияет то, сколько памяти он занимает в процессе работы (например, у алгоритма высокая сложность, но он кушает мало памяти, и для устройств с малым количеством оперативной памяти лучше реализовать его), сложность реализации алгоритма (например, мы знаем, что алгоритм «быстрой сортировки» быстрее, чем алгоритм «сортировки пузырьком». Но у вас в компании работают только веб-программисты, которые написать алгоритм быстрой сортировки не смогут. Поэтому вам ничего не остается, кроме реализации алгоритма «сортировки пузырьком») и требования алгоритма к железу (в основном это алгоритмы для нейросетей, которые работают на видеокартах. Например, что бы прогнать картинку 512х512 пикселей через нейросеть типа ESRGAN, вам потребуется видеокарта, у которой не менее 2 ГБ видеопамяти).
Лично мне нравиться эта табличка, которую я нашел в группе /dev/null в ВК
Другой взгляд на О большое:
Как это связано со структурами данных? Структуры данных и алгоритмы очень тесно связаны, и у каждой структуры есть свои алгоритмы обхода элементов структуры, их добавление\удаление, поиск в структуре и т.д. И поэтому важно знать сложность алгоритмов, которые дают нам возможность управлять этой структурой, что бы выбрать подходящую для решения нашей задачи.
Со сложностью алгоритмов вроде разобрались. На практике для каждой задачи есть несколько решений, и вы сами, как программист, вольны выбрать то, которое подходит именно под вашу ситуацию.
В следующей статье я попробую рассказать о структурах данных, зачем они нужны и рассмотреть такие структуры, как стек, очередь и связанный список.