Stack считается «устаревшим». Чем его рекомендуют заменять? Почему?

Stack был добавлен в Java 1.0 как реализация стека LIFO (last-in-first-out) и является расширением коллекции Vector, хотя это несколько нарушает понятие стека (например, класс Vector предоставляет возможность обращаться к любому элементу по индексу). Является частично синхронизированной коллекцией (кроме метода добавления push()) с вытекающими отсюда последствиями в виде негативного воздействия на производительность. После добавления в Java 1.6 интерфейса Deque, рекомендуется использовать реализации именно этого интерфейса, например ArrayDeque.

 

45. List vs. Set.

Разница между списком и множеством в Java

Список - это упорядоченная последовательность элементов, тогда как Set - это отдельный список элементов, который не упорядочен

Список допускает дублирование, а Set не допускает дублирование элементов.

Список разрешает любое количество нулевых значений в своей коллекции, а Set разрешает только одно нулевое значение в своей коллекции.

Список может быть вставлен как в прямом, так и в обратном направлении с помощью Listiterator, тогда как Set можно просматривать только в прямом направлении с помощью итератора

 

46. Map не в Collection.

Интерфейс Map реализован классами:

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

-HashMap — хэш-таблица. Позволяет использовать null в качестве значения или ключа и не является упорядоченной.

-LinkedHashMap — упорядоченная реализация хэш-таблицы.

-TreeMap — реализация основанная на красно-черных деревьях. Является упорядоченной и предоставляет возможность управлять порядком элементов в коллекции при помощи объекта Comparator, либо сохраняет элементы с использованием «natural ordering».

-WeakHashMap — реализация хэш-таблицы, которая организована с использованием weak references для ключей (сборщик мусора автоматически удалит элемент из коллекции при следующей сборке мусора, если на ключ этого элемента нет жёстких ссылок).

 

47. Collection vs. Collections.

В чем разница между классами java.util.Collection и java.util.Collections?

java.util.Collections - набор статических методов для работы с коллекциями.

java.util.Collection - один из основных интерфейсов Java Collections Framework.

 

 

48. ArrayList vs. LinkedList.

Чем отличается ArrayList от LinkedList? В каких случаях лучше использовать первый, а в каких второй?

ArrayList это список, реализованный на основе массива, а LinkedList — это классический двусвязный список, основанный на объектах с ссылками между ними.

ArrayList:

● доступ к произвольному элементу по индексу за константное время O(1);

● доступ к элементам по значению за линейное время O(N);

● вставка в конец в среднем производится за константное время O(1);

● удаление произвольного элемента из списка занимает значительное время т.к. при этом все элементы находящиеся «правее» смещаются на одну ячейку влево (реальный размер массива (capacity) не изменяется);

● вставка элемента в произвольное место списка занимает значительное время т.к. при этом все элементы находящиеся «правее» смещаются на одну ячейку вправо;

● минимум накладных расходов при хранении.

LinkedList:

● на получение элемента по индексу или значению потребуется линейное время O(N);

● на добавление и удаление в начало или конец списка потребуется константное O(1);

● вставка или удаление в/из произвольного место линейное O(N);

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

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

 

Что работает быстрее ArrayList или LinkedList?

Смотря какие действия будут выполняться над структурой.

см. Чем отличается ArrayList от LinkedList

 

Какое худшее время работы метода contains() для элемента, который есть в LinkedList?

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

 

Какое худшее время работы метода contains() для элемента, который есть в ArrayList?

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

 

Какое худшее время работы метода add() для LinkedList?

O(N). Добавление в начало/конец списка осуществляется за время O(1).

 

Какое худшее время работы метода add() для ArrayList?

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

 

Необходимо добавить 1 млн. элементов, какую структуру вы используете?

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

см. Чем отличается ArrayList от LinkedList

 

Как происходит удаление элементов из ArrayList? Как меняется в этом случае размер ArrayList?

При удалении произвольного элемента из списка, все элементы находящиеся «правее» смещаются на одну ячейку влево и реальный размер массива (его емкость, capacity) не изменяется никак. Механизм автоматического «расширения» массива существует, а вот автоматического «сжатия» нет, можно только явно выполнить «сжатие» командой trimToSize().