Какие структуры данных существуют и для чего они нужны
Что проверяют
Умеете ли вы группировать структуры по свойствам и выбирать под операцию, а не перечислять названия.
Как отвечать
Отвечайте группами, называя, что структура даёт и чем за это платит.
Линейные:
- массив: элементы подряд, доступ по индексу за постоянное время, отличная работа с кэшем процессора. Вставка в середину линейна;
- динамический массив: то же плюс рост, добавление в конец амортизированно постоянное;
- связный список: вставка по известному узлу за постоянное время, но доступ по индексу линейный, а прыжки по памяти плохо ложатся на кэш. На практике проигрывает массиву чаще, чем кажется;
- стек и очередь: доступ с одного или с двух концов;
- дек: постоянное время с обоих концов.
Ассоциативные:
- хеш-таблица: доступ по ключу в среднем за постоянное время, порядка нет, нужна хорошая хеш-функция;
- сбалансированное дерево поиска: логарифм, зато ключи упорядочены, доступны диапазоны и поиск ближайшего.
Деревья: двоичное дерево поиска и его сбалансированные варианты, куча для извлечения минимума за логарифм, префиксное дерево для поиска по префиксу строки, B-дерево для дисковых индексов, где узел равен странице.
Графы: список смежности против матрицы, выбор зависит от плотности.
Специальные: фильтр Блума для вероятностной проверки принадлежности при малом расходе памяти, кэш с вытеснением давно неиспользованных, система непересекающихся множеств.
Главное, что стоит сказать в конце: выбор делается от операций. Нужны частые проверки вхождения, значит множество; нужен порядок и диапазоны, значит дерево; нужен доступ по индексу и проход подряд, значит массив.
Где спотыкаются
Перечисляют названия без свойств и стоимости операций.
Считают связный список быстрее массива по вставке, забывая про поиск позиции.
Не знают, зачем нужно дерево, если есть хеш-таблица.
Выбирают структуру по привычке, а не по набору операций.