List и Set в Java

ArrayList против LinkedList: что показал замер

ArrayList - динамический массив. Доступ по индексу это арифметика над адресом, отсюда 0,27 мс на две тысячи обращений. Добавление в конец амортизированно дешёвое: когда место кончается, массив растёт в полтора раза с копированием. Я подсмотрел вместимость на первых сорока вставках: 10, 15, 22, 33, 49 - тот самый множитель.

LinkedList - двусвязный список. До i-го элемента он идёт по ссылкам, поэтому 274 мс на тех же двух тысячах обращений. Дело тут даже не в количестве шагов: узлы разбросаны по куче, и каждый переход - промах кэша процессора. Видно это на полном обходе: там счёт по ссылкам идёт по порядку, и разрыв падает до 5,48 мс против 6,69.

Но честный замер показывает и обратную сторону. Вставка в начало у LinkedList - перевесить две ссылки, у ArrayList - сдвинуть весь хвост. 100 000 вставок: 17 мс против 476. То есть LinkedList выигрывает там, где позиция уже в руках.

// Практический вывод всё равно в пользу ArrayList: в реальном коде до позиции сначала надо дойти, а это те самые 274 мс. Для очереди и стека берут ArrayDeque - он тоже на массиве и быстрее LinkedList в обеих ролях.

амортизированная стоимость

редкое дорогое расширение, размазанное по дешёвым вставкам

промах кэша

данные не рядом в памяти, процессор ждёт

Set-семейство: три способа быть уникальным

HashSet внутри это HashMap, где элементы играют роль ключей: проверка принадлежности в среднем за постоянное время, порядок обхода не гарантирован. LinkedHashSet добавляет к этому предсказуемый порядок вставки. TreeSet держит элементы отсортированными в красно-чёрном дереве: все операции за логарифм, зато можно спрашивать диапазоны.

Кто решает, что элемент - дубликат? В hash-структурах пара equals и hashCode. А в TreeSet - метод compareTo или переданный компаратор, equals там не зовут вовсе.

// Отсюда неочевидное следствие: объект, у которого compareTo несогласован с equals, в HashSet и TreeSet живёт по-разному. Один и тот же набор даёт разное число элементов, и BigDecimal с его 1.0 и 1.00 - живой тому пример.

LinkedHashSet

уникальность плюс предсказуемый порядок вставки

TreeSet

отсортированное множество, дубликат определяет compareTo

Три ловушки API, которые я проверил запуском

Первая: метод remove у списка перегружен. Взял список из 10, 20, 30 и вызвал remove(1) - получил [10, 30], то есть удалился элемент по ИНДЕКСУ один. Чтобы удалить по значению, нужен remove(Integer.valueOf(30)) - тогда получается [10]. Для списка чисел эти два вызова выглядят одинаково, а делают разное.

Вторая: неизменяемые обёртки ведут себя по-разному. У Arrays.asList метод set РАБОТАЕТ - список изменился на [9, 2, 3], потому что это вид поверх массива фиксированного размера. А add у него уже даёт UnsupportedOperationException. У List.of запрещено и то и другое, а ещё он не принимает null - падает с NullPointerException прямо в конструкторе.

Третья и самая интересная: удаление внутри foreach. Взял список из четырёх элементов и удалял по очереди каждый. Три случая из четырёх дали ConcurrentModificationException. А удаление ТРЕТЬЕГО элемента из четырёх прошло молча, список стал [a, b, d], никакого исключения.

// Это значит, что защита от изменения на обходе - детектор, а не гарантия. Он проверяет счётчик модификаций перед следующим шагом, а после удаления предпоследнего обход просто заканчивается раньше проверки. Законные способы - iterator.remove() и removeIf.

List<Integer> l = new ArrayList<>(List.of(10, 20, 30));
l.remove(1);                   // [10, 30] - по ИНДЕКСУ
l.remove(Integer.valueOf(30)); // [10]     - по значению

CME

ConcurrentModificationException - изменение во время обхода

вид поверх массива

Arrays.asList: set можно, add нельзя

Как отвечать: «ArrayList или LinkedList - что выберешь и почему?»

Почти всегда ArrayList, и я могу сказать почему на числах. Мерил на двухстах тысячах элементов: две тысячи обращений по индексу у ArrayList заняли 0,27 миллисекунды, у LinkedList - 274. Разница в тысячу раз, потому что список идёт по ссылкам, а каждый переход это ещё и промах кэша процессора - данные лежат вразброс. Честно скажу и обратное: на вставках в начало LinkedList действительно выигрывает, 17 миллисекунд против 476. Но в реальном коде до места вставки надо сначала дойти, и весь выигрыш съедается поиском. Плюс у ArrayList данные лежат непрерывно, а добавление в конец амортизированно дешёвое: массив растёт в полтора раза, я смотрел последовательность вместимостей - 10, 15, 22, 33, 49. Если нужна очередь или стек, беру ArrayDeque, он тоже на массиве и обходит LinkedList в обеих ролях. Реальный сценарий именно для LinkedList мне назвать сложно, и это нормальный ответ.

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

На чём валят

• −Берут LinkedList «для быстрых вставок». Доступ по индексу у меня вышел в тысячу раз медленнее.
• −Зовут list.remove(1) на списке чисел и удаляют по индексу вместо значения. Классическое «что напечатает».
• −Мутируют Arrays.asList или List.of. У первого set работает, а add уже нет; у второго запрещено всё.
• −Удаляют элемент в foreach. Обычно это ConcurrentModificationException, но у меня один случай из четырёх прошёл молча.
• −Кладут в HashSet объекты без equals и hashCode. Множество честно хранит оба «одинаковых» элемента.