В чем разница между List и Set в Java, и какой из них упорядочен?

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

Знаете ли вы, что «упорядочен» неоднозначное слово, и различаете ли порядок вставки и сортировку.

Как отвечать

List это упорядоченная последовательность с доступом по индексу, дубликаты разрешены. Set это множество уникальных элементов, индекса нет.

Про порядок аккуратнее, потому что здесь и ловушка:

• List всегда сохраняет порядок вставки, это часть контракта;
• HashSet порядка не гарантирует вовсе;
• LinkedHashSet сохраняет порядок вставки;
• TreeSet хранит элементы отсортированными по Comparable или Comparator.

То есть правильный ответ на «какой упорядочен» звучит так: список всегда, множество в зависимости от реализации.

Уникальность в Set определяется через equals и hashCode (у TreeSet через compareTo), поэтому объект без корректной реализации этих методов попадёт в множество дважды. И наоборот: изменение поля, участвующего в хеше, у объекта, уже лежащего в HashSet, делает его недостижимым.

Как выбирать: нужен порядок и повторы, значит список; нужна уникальность и быстрая проверка вхождения, значит множество. Проверка contains у ArrayList линейная, у HashSet за постоянное время, и на больших объёмах это решает.

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

Говорят «Set неупорядочен», не уточняя реализацию.

Кладут в Set объекты без equals и hashCode.

Используют List.contains в цикле и получают квадратичную сложность.

Не знают, что TreeSet не примет null.