Что такое структура данных

Что проверяют

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

Как отвечать

Структура данных это способ организации данных вместе с набором операций над ними и стоимостью этих операций. Определение без второй половины пустое: ценность структуры ровно в том, что одни операции она делает дёшево, а другие дорого.

В Java разговор удобно сразу перевести на контракты и реализации. List, Set, Map, Deque это контракты, а ArrayList, LinkedList, HashMap, TreeMap, ArrayDeque это реализации с разной ценой операций.

Дальше по стоимости. ArrayList даёт доступ по индексу за константу и вставку в середину за линейное время, LinkedList наоборот, но поиск позиции у него всё равно линейный. HashMap в среднем даёт константу на вставку и поиск, требует согласованных equals и hashCode, а длинная цепочка коллизий в современных версиях перестраивается в дерево. TreeMap даёт логарифм и, в отличие от хеш-таблицы, порядок обхода.

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

Где спотыкаются

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

Кладут в HashMap ключ без корректных equals и hashCode либо меняют поле, участвующее в вычислении хеша, уже после вставки. Запись в таблице остаётся, но найти её больше нельзя.

Останавливаются на асимптотике. Она не видит ни размера объекта, ни упаковки чисел в Integer, ни промахов кэша, а на реальных объёмах именно это определяет разницу.