Как вы оцениваете временную сложность операций с коллекциями в Java?

Временная сложность операций определяется внутренней реализацией коллекции. Знание этих характеристик необходимо для выбора оптимальной структуры данных под конкретную задачу.

Основные примеры:

• ArrayList:
  • get(int index), set(int index, E element) — O(1).
  • add(E element) — O(1) амортизированно.
  • add(int index, E element), remove(int index) — O(n) (сдвиг элементов).
• LinkedList:
  • addFirst(E e), addLast(E e) — O(1).
  • get(int index), remove(int index) — O(n) (требуется последовательный проход).
• HashMap:
  • get(Object key), put(K key, V value) — O(1) в среднем случае, O(n) в худшем (при вырождении бакетов).
• TreeMap:
  • get(Object key), put(K key, V value) — O(log n), так как основана на красно-черном дереве.

Практический пример с HashMap:

Map<String, Integer> map = new HashMap<>();
map.put("key", 42);  // ~O(1)
int value = map.get("key"); // ~O(1)