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

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

Наиболее распространенные реализации и их структуры данных:

• ArrayList: Использует динамический массив.
• LinkedList: Использует двусвязный список.
• Vector: (Устаревшая, синхронизированная версия ArrayList) Использует динамический массив.

Пример реализации ArrayList:

// Содержит элементы в массиве
private transient Object[] elementData; 

Пример реализации LinkedList:

// Ссылка на первый узел
transient Node<E> first; 

// Ссылка на последний узел
transient Node<E> last; 

// Внутренний класс для узла
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;
    }
}