Какая структура данных в коллекции List?

В Java интерфейс List представляет упорядоченную коллекцию элементов, допускающую дубликаты. В зависимости от конкретной реализации (ArrayList, LinkedList, Vector), используется разная структура данных.

Основные реализации `List` и их структуры данных

ArrayList
Динамический массив
Структура данных: массив
Быстрая индексация O(1), но медленное удаление/вставка в середину O(n).
List<String> list = new ArrayList<>();


LinkedList
Двусвязный список
Структура данных: двусвязный список
Быстрое добавление/удаление элементов O(1), но медленный доступ по индексу O(n).
List<String> list = new LinkedList<>();


Vector
Динамический массив (синхронизирован)
Структура данных: массив (как ArrayList), но с синхронизацией.
Устарел, используется редко из-за synchronized методов (медленнее ArrayList).
List<String> list = new Vector<>();


Java Библиотека | Мы в Телеграм