Комментарии (1)
🐱
claude-haiku-4.5PrepBro AI22 мар. 2026 г.(ред.)
Ответ сгенерирован нейросетью и может содержать ошибки
Устройство List в Java
List — это интерфейс, определяющий упорядоченную коллекцию элементов, где каждый элемент имеет индекс. Java предоставляет несколько реализаций с разными характеристиками производительности.
Иерархия List
Collection
└─ List (интерфейс)
├─ ArrayList (динамический массив)
├─ LinkedList (двусвязный список)
├─ Vector (синхронизированный ArrayList)
├─ CopyOnWriteArrayList (thread-safe для read-heavy)
└─ Collections.synchronizedList() (обертка)
ArrayList — Динамический массив
Внутреннее устройство:
public class ArrayList<E> implements List<E> {
private static final int DEFAULT_CAPACITY = 10;
// Основной массив
transient Object[] elementData;
// Текущее количество элементов
private int size;
// Версия коллекции (для fail-fast итератора)
protected transient int modCount;
}
Как это работает:
ArrayList<String> list = new ArrayList<>();
// При создании выделяется массив на 10 элементов
// elementData = new Object[10]
// size = 0
list.add("first"); // size = 1, elementData[0] = "first"
list.add("second"); // size = 2, elementData[1] = "second"
// При 11-м элементе происходит resize
// Создается новый массив size * 3/2 = 15 элементов
// Копируются все элементы
list.add("eleventh");
Операции и их сложность:
// O(1) — быстро
list.get(5); // Доступ по индексу
list.set(5, "value"); // Замена элемента
list.add("value"); // Добавление в конец (обычно)
// O(n) — медленно
list.add(0, "value"); // Вставка в начало
list.remove(0); // Удаление из начала
list.contains("x"); // Поиск элемента
list.indexOf("x"); // Поиск индекса
Пример добавления в начало (O(n)):
ArrayList<Integer> list = new ArrayList<>(Arrays.asList(
1, 2, 3, 4, 5));
list.add(0, 0); // Результат: [0, 1, 2, 3, 4, 5]
// Внутри:
// 1. Проверка места: нужен ли resize?
// 2. Сдвиг всех элементов: [1,2,3,4,5,?] -> [1,2,3,4,5,?] -> ... -> [?,1,2,3,4,5]
// 3. Вставка нового элемента на место [0]
LinkedList — Двусвязный список
Внутреннее устройство:
public class LinkedList<E> implements List<E>, Deque<E> {
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
transient int size = 0;
transient Node<E> first; // Голова списка
transient Node<E> last; // Хвост списка
}
Визуальное представление:
null <-> [Item1] <-> [Item2] <-> [Item3] <-> null
first last
Операции и их сложность:
LinkedList<String> list = new LinkedList<>();
// O(1) — очень быстро
list.add("value"); // Добавление в конец
list.addFirst("value"); // Добавление в начало
list.addLast("value"); // Добавление в конец
list.removeFirst(); // Удаление с начала
list.removeLast(); // Удаление с конца
// O(n) — медленно
list.get(5); // Поиск по индексу требует прохода
list.set(5, "value"); // Требует поиска по индексу
list.add(5, "value"); // Требует поиска по индексу
list.remove(5); // Требует поиска по индексу
list.contains("x"); // Требует прохода по всему списку
Пример добавления в начало (O(1)):
LinkedList<Integer> list = new LinkedList<>(Arrays.asList(
1, 2, 3, 4, 5));
list.addFirst(0); // Результат: [0, 1, 2, 3, 4, 5]
// Внутри:
// 1. Создаем новую Node: new Node(null, 0, first)
// 2. Старый first.prev = newNode
// 3. first = newNode
// Сложность: константна, не зависит от размера
Сравнение ArrayList vs LinkedList
// Таблица сложностей:
/*
Операция ArrayList LinkedList
add(E) O(1) amort O(1)
add(int, E) O(n) O(n)
get(int) O(1) O(n)
remove(int) O(n) O(n)
contains(Object) O(n) O(n)
iterator() O(1) O(1)
*/
// Оптимизация: если часто получаешь элементы по индексу
// -> ArrayList
for (int i = 0; i < list.size(); i++) {
String item = list.get(i); // O(1) для ArrayList, O(n) для LinkedList
}
// Оптимизация: используй iterator для LinkedList
for (String item : list) { // O(1) за элемент, O(n) всего
System.out.println(item);
}
Vector — Синхронизированный ArrayList
public class Vector<E> extends AbstractList<E> implements List<E> {
protected Object[] elementData; // Как в ArrayList
protected int elementCount; // Текущий размер
protected int capacityIncrement; // Шаг увеличения
// Все методы синхронизированы
public synchronized void addElement(E obj) {
// ...
}
}
// Vector -> ArrayList с synchronized
// Не используй Vector в новом коде!
Vector<String> vector = new Vector<>();
vector.add("item"); // Синхронизировано
// Лучше использовать CopyOnWriteArrayList
List<String> list = new CopyOnWriteArrayList<>();
list.add("item"); // Thread-safe, быстрее при чтении
CopyOnWriteArrayList — Для read-heavy
public class CopyOnWriteArrayList<E> implements List<E> {
private transient volatile Object[] array;
// При добавлении: копируем ВЕСЬ массив
public boolean add(E e) {
synchronized(lock) {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
}
}
// При чтении: просто возвращаем
public E get(int index) {
return (E) getArray()[index]; // Без синхронизации!
}
}
// Использование:
List<String> listeners = new CopyOnWriteArrayList<>();
// Много читателей
for (String listener : listeners) { // Очень быстро
notifyListener(listener);
}
// Редкие писатели
listeners.add("newListener"); // Медленно (копирование)
Итератор и Fail-Fast
ArrayList<String> list = new ArrayList<>(Arrays.asList(
"a", "b", "c", "d"));
Iterator<String> iterator = list.iterator();
iterator.next(); // "a"
iterator.next(); // "b"
list.add("e"); // modCount++
iterator.next(); // ConcurrentModificationException!
// Внутри итератора проверяется:
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
Правильное удаление во время итерации
// НЕПРАВИЛЬНО - ConcurrentModificationException
ArrayList<String> list = new ArrayList<>(Arrays.asList(
"a", "b", "c", "d"));
for (String s : list) {
if (s.equals("b")) {
list.remove(s); // Ошибка!
}
}
// ПРАВИЛЬНО - используй iterator.remove()
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
if (iterator.next().equals("b")) {
iterator.remove(); // OK, modCount обновляется
}
}
// ПРАВИЛЬНО - создай новый список
list = list.stream()
.filter(s -> !s.equals("b"))
.collect(Collectors.toList());
Практические рекомендации
- ArrayList — default выбор, используй для большинства случаев
- LinkedList — только если часто добавляешь/удаляешь в начало (Deque)
- Vector — не использовать (deprecated pattern)
- CopyOnWriteArrayList — для многопоточного read-heavy сценария
- Collections.synchronizedList — лучше CopyOnWriteArrayList или ConcurrentHashMap
List — фундаментальная структура, выбор реализации критичен для производительности.