What data structure is used in the List collection?

The List collection uses different data structures depending on the specific implementation of the interface.

The most common implementations and their data structures:

• ArrayList: Uses a dynamic array.
• LinkedList: Uses a doubly linked list.
• Vector: (Deprecated, synchronized version of ArrayList) Uses a dynamic array.

Example of ArrayList implementation:

// Contains elements in an array
private transient Object[] elementData; 

Example of LinkedList implementation:

// Reference to the first node
transient Node<E> first; 

// Reference to the last node
transient Node<E> last; 

// Inner class for a node
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;
    }
}