List

List는 인덱스 순서로 저장이 되며, 중복된 데이터가 저장이 가능하다.
객체를 저장하면 자동으로 인덱스가 부여되고 인덱스를 통해 데이터의 검색 및 삭제가 가능하다.
대표적인 구현체로는 ArrayList, Vector, LinkedList가 있다.

ArrayList

ArrayList는 초기에 설정된 저장용량(capacity)보다 많은 데이터가 들어오면 자동으로 용량이 늘어난다.
기본적으로 10의 저장용량을 갖는다.
기본적으로 데이터를 추가할 때는 인덱스 순으로 자동 저장되고,
중간에 데이터를 추가하거나 삭제하면 인덱스가 한 칸씩 뒤로 밀리거나 당겨진다.

구현

내부적으로 Object 배열을 갖고있고 초기에 설정된 용량 또는 기본값 10으로 배열을 생성한다.

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access
    
    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;

배열의 최대 크기는 Integer의 max 정도이다.

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

초기 선언한 배열보다 더 많은 데이터가 삽입될 때 배열의 크기를 1.5배 증가시킨다.

 private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

Vector

Vector는 기본적으로 ArrayList와 동일한 구조를 갖는다.
ArrayList와 차이점은 Vector는 자동 동기화를 보장하므로 멀티 스레드 환경에서 사용이 가능하다.
단일 스레드에서는 ArrayList가 성능이 더 좋다.

구현

Vector는 기본적으로 ArrayList와 동일한 구조를 갖는다.
synchronized 키워드를 사용하여 Thread Safe를 보장한다.

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    /**
     * The array buffer into which the components of the vector are
     * stored. The capacity of the vector is the length of this array buffer,
     * and is at least large enough to contain all the vector's elements.
     *
     * <p>Any array elements following the last element in the Vector are null.
     *
     * @serial
     */
    protected Object[] elementData;

    /**
     * The number of valid components in this {@code Vector} object.
     * Components {@code elementData[0]} through
     * {@code elementData[elementCount-1]} are the actual items.
     *
     * @serial
     */
    protected int elementCount;

    /**
     * The amount by which the capacity of the vector is automatically
     * incremented when its size becomes greater than its capacity.  If
     * the capacity increment is less than or equal to zero, the capacity
     * of the vector is doubled each time it needs to grow.
     *
     * @serial
     */
    protected int capacityIncrement;

LinkedList

위 컬렉션들은 인덱스로 데이터를 관리하지만 LinkedList는 인접한 곳을 링크하여 체인처럼 관리한다.
LinkedList는 다른 컬렉션과 다르게 중간의 데이터를 삭제할 때 인접한 곳의 링크만 변경하면 되기 때문에 중간에 데이터 추가/삭제의 경우 처리속도가 빠르다.
대신 검색의 경우 인접 링크를 따라가며 찾아야하기 때문에 ArrayList보다 느리다.

구현

Node라는 객체로 연결 리스트를 관리하며, 앞뒤 노드를 멤버변수로 갖고있다.
데이터를 앞에 넣는 경우 first Node를 사용하고,
뒤에 넣는 경우 last Node를 사용한다.
따라서 Queue 컬렉션처럼 사용할 수도 있다.

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;