Недавно обнаружил подборку из более чем 90 вопросов на эту тему. Решил попробовать ответить на все из них.

Если обнаружите какую-либо ошибку либо захотите дополнить - напишите мне, пожалуйста, в комментариях либо на почту.

2 часть.
3 часть.

Общая иерархия

1. Расположите в виде иерархии следующие интерфейсы: List, Set, Map, SortedSet, SortedMap, Collection, Iterable, Iterator, NavigableSet, NavigableMap.

2. Почему Map — это не Collection, в то время как List и Set являются Collection?

Коллекция (List и Set) представляет собой совокупность некоторых элементов (обычно экземпляров одного класса). Map - это совокупность пар "ключ"-"значение".
Соответственно некоторые методы интерфейса Collection нельзя использовать в Map.
Например, метод remove(Object o) в интерфейсе Collection предназначен для удаления элемента, тогда как такой же метод remove(Object key) в интерфейсе Map - удаляет элемент по заданному ключу.

3. Как одной строчкой преобразовать HashSet в ArrayList?

public static void main(String... args) {
  Set<String> set = new HashSet<>(); 
  set.add("A"); 
  set.add("B");
  // Преобразование. 
  List<String> list = new ArrayList<>(set); 
}

4. Как одной строчкой преобразовать ArrayList в HashSet?

public static void main(String... args) {
  List<String> list = new ArrayList<>();
  list.add("A");
  list.add("B");
  // Преобразование.
  Set<String> set = new HashSet<>(list);
}

5. Как перебрать все ключи Map учитывая, что Map — это не Iterable?

Использовать метод keySet(), который возвращает множество (Set<K>) ключей.

6. Как перебрать все значения Map учитывая, что Map — это не Iterable?

Использовать метод values(), который возвращает коллекцию (Collection<V>) значений.

7. Как перебрать все пары ключ-значение в Map учитывая, что Map — это не Iterable?

Использовать метод entrySet(), который возвращает множество (Set<Map.Entry<K, V>) пар "ключ"-"значение".

8. В чем проявляется «сортированность» SortedMap, кроме того, что toString() выводит все по порядку?

Естественное упорядочивание (natural ordering) отражается при итерации по коллекции ключей или значений хэш-таблицы (возвращаемых методами keySet(), values() и entrySet()).

9. Как одним вызовом копировать элементы из любой Collection в массив?

public static void main(String... args) {
  List<String> list = new ArrayList<>();
  list.add("A");
  list.add("B");

  String[] strArray = list.toArray(new String[list.size()]);
  // Либо
  Object[] objArray = list.toArray();
}

10. Реализуйте симметрическую разность двух коллекций используя методы Collection (addAll(), removeAll(), retainAll()).

Симметрическая разность двух коллекций - это множество элементов, одновременно не принадлежащих обоим исходным коллекциям.

public static <T> Collection<T> symmetricDifference(Collection<T> a, Collection<T> b) {
  // Создаем новую коллекцию, чтобы не изменять исходные.
  Collection<T> intersection = new ArrayList<>(a);
  // Получаем пересечение коллекций.
  intersection.retainAll(b);
  Collection<T> result = new ArrayList<>(a);
  // Объединяем коллекции.
  result.addAll(b);
  // Удаляем элементы, расположенные в обоих коллекциях.
  result.removeAll(intersection);

  return result;
}

public static void main(String[] args) {
  List<String> a = new ArrayList<>(Arrays.asList("1", "2", "3", "4", "5"));
  List<String> b = new ArrayList<>(Arrays.asList("3", "4", "5", "6", "7"));
  Collection<String> c = symmetricDifference(a, b);
  System.out.println("Collection a: " + Arrays.toString(a.toArray())); // Collection a: [1, 2, 3, 4, 5]
  System.out.println("Collection b: " + Arrays.toString(b.toArray())); // Collection b: [3, 4, 5, 6, 7]
  System.out.println("Collection c: " + Arrays.toString(c.toArray())); // Collection c: [1, 2, 6, 7]
}

Iterator, Iterable

1. Сравните Enumeration и Iterator.

Оба интерфейса предназначены для обхода коллекций. Интерфейс Iterator был введен несколько позднее в Java Collections Framework и его использование предпочтительнее.

Основные различия Iterator по сравнению с Enumeration:

• наличие метода remove() для удаления элемента из коллекции при обходе;
• исправлены имена методов для повышения читаемости кода.

Источник - http://docs.oracle.com/javase/7/docs/api/java/util/Iterator.html

2. Как между собой связаны Iterable и Iterator?

Интерфейс Iterable имеет только один метод - iterator(), который возвращает итератор коллекции для её обхода.

3. Как между собой связаны Iterable, Iterator и «for-each» введенный в Java 5?

Экземпляры классов, реализующих интерфейс Iterable, могут использоваться в конструкции foreach.

4. Сравните Iterator и ListIterator.

ListIterator расширяет интерфейс Iterator, позволяя клиенту осуществлять обход коллекции в обоих направлениях, изменять коллекцию и получать текущую позицию итератора.

При этом важно помнить, что ListIterator не указывает на конкретный элемент, а его текущая позиция располагается между элементами, которые возвращают методы previous() и next(). Таким образом, модификация коллекции осуществляется для последнего элемента, который был возвращен методами previous() и next().

5. Что произойдет, если я вызову Iterator.next() не «спросив» Iterator.hasNext()?

Если итератор указывает на последний элемент коллекции, то возникнет исключение NoSuchElementException, иначе будет возвращен следующий элемент.

6. Что произойдет, если я вызову Iterator.next() перед этим 10 раз вызвав Iterator.hasNext()? Я пропущу 9 элементов?

Нет, hasNext() осуществляет только проверку наличия следующего элемента.

7. Если у меня есть коллекция и порожденный итератор, изменится ли коллекция, если я вызову iterator.remove()?

Вызов метода iterator.remove() возможен только после вызова метода iterator.next() хотя бы раз, иначе появится исключение IllegalStateException().

Если iterator.next() был вызван прежде, то iterator.remove() удалит элемент, на который указывает итератор.

8. Если у меня есть коллекция и порожденный итератор, изменится ли итератор, если я вызову collection.remove(..)?

Итератор не изменится, но при следующем вызове его методов возникнет исключение ConcurrentModificationException.

List: ArrayList, LinkedList

1. Зачем добавили ArrayList, если уже был Vector?

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

Класс Vector был введен в JDK 1.0 и не является частью Java Collection Framework. Методы класса Vector синхронизированы, что обеспечивает потокобезопасность, но это приводит к снижению производительности, поэтому и был введен класс ArrayList, методы которого не синхронизированы.

2. В реализации класса ArrayList есть следующие поля: Object[] elementData, int size. Объясните, зачем хранить отдельно size, если всегда можно взять elementData.length?

Размер массива elementData представляет собой вместимость (capacity) ArrayList, которая всегда больше переменной size - реального количества хранимых элементов. С добавлением новых элементов вместимость автоматически возрастает при необходимости.

3. LinkedList — это односвязный, двусвязный или четырехсвязный список?

Двухсвязный список: каждый элемент LinkedList хранит ссылку на предыдущий и следующий элементы.

4. Какое худшее время работы метода contain() для элемента, который есть в LinkedList (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?

O(N). Время поиска элемента линейно пропорционально количеству элементов с списке.

5. Какое худшее время работы метода contain() для элемента, который есть в ArrayList (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?

O(N). Время поиска элемента линейно пропорционально количеству элементов с списке.

6. Какое худшее время работы метода add() для LinkedList (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?

O(1). Вставка в конец списка осуществляется за время O(1).

7. Какое худшее время работы метода add() для ArrayList (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?

O(N). Вставка элемента в конец списка осуществляется за время O(1), но если вместимость массива недостаточна, то происходит создание нового массива с увеличенным размером и копирование всех элементов из старого массива в новый.

8. Сколько выделяется элементов в памяти при вызове ArrayList.add()?

Если в массиве достаточно места для размещения нового элемента, то дополнительное место в памяти не выделяется. Иначе происходит создание нового массива с размером:

int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);

Другими словами, создается новый массив, размер которого вычисляется как умножение старого размера на 1.5 (это верно для JDK 1.7, в более ранних версиях вычисления отличаются).

9. Сколько выделяется элементов в памяти при вызове LinkedList.add()?

Создается один новый экземпляр вложенного класса Node.

10. Оцените количество памяти на хранение одного примитива типа byte в LinkedList?

Каждый элемент LinkedList хранит ссылку на предыдущий элемент, следующий элемент и ссылку на данные. Для x32 систем каждая ссылка занимает 32 бита (4 байта). Сам объект типа Node занимает приблизительно 8 байт. Размер каждого объекта в Java кратен 8, соответственно получаем 24 байта. Примитив типа byte занимает 1 байт памяти, но в списке примитивы упаковываются: объекта типа Byte занимает в памяти 16 байт (8 байт на заголовок объекта, 1 байт на поле типа byte и 7 байт для кратности 8). Также напомню, что значения от -128 до 127 кэшируются и для них новые объекты каждый раз не создаются. Таким образом, в x32 JVM 24 байта тратятся на хранение одного элемента в списке и 16 байт - на хранение упакованного объекта типа Byte.

Для 64-битной JVM каждая ссылка занимает 64 бита (8 байт), размер заголовка каждого объекта составляет 16 байт (два машинных слова). Вычисления аналогичны.

11. Оцените количество памяти на хранение одного примитива типа byte в ArrayList?

ArrayList основан на массиве, для примитивных типов данных осуществляется автоматическая упаковка значения, поэтому 16 байт тратится на хранение упакованного объекта и 4 байта (8 для x64) - на хранение ссылки на этот объект в самой структуре данных. Таким образом, в x32 JVM 4 байта используются на хранение одного элемента и 16 байт - на хранение упакованного объекта типа Byte.

12. Я добавляю элемент в середину List-а: list.add(list.size()/2, newElem). Для кого эта операция медленнее — для ArrayList или для LinkedList?

Для ArrayList:

• проверка массива на вместимость. Если вместимости недостаточно, то увеличение размера массива и копирование всех элементов в новый массив ( O(N) );
• копирование всех элементов, расположенных правее от позиции вставки, на одну позицию вправо ( O(N/2) );
• вставка элемента ( O(1) ).

Для LinkedList:

• поиск позиции вставки ( O(N/2) );
• вставка элемента ( O(1) ).

В худшем случае вставка в середину списка эффективнее для LinkedList. В остальных - скорее всего, для ArrayList, поскольку копирование элементов осуществляется за счет системного метода System.arraycopy().

13. Как перебрать элементы LinkedList в обратном порядке, не используя медленный get(index)?

Использовать обратный итератор. Для этого в LinkedList есть метод descendingIterator().

14. Как одним вызовом из List получить List со всеми элементами, кроме первых и последних 3-х?

List<Integer> sourceList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9));
List<Integer> subList = sourceList.subList(3, sourceList.size() - 3); // 4, 5, 6