[Java] List... 그리고 ArrayList, LinkedList, Vector 데이터 추가

개요

안녕하세요. 이번시간에는 List 자료구조에 대해 알아보겠습니다.

 

기본적으로 List 인터페이스를 구현받아 사용하는 대표적인 클래스는 ArrayList, LinkedLIst 그리고 Vector가 존재합니다.

 

이번시간에는 각 클래스에 차이점과 활용방법에 대해 알아보겠습니다.

 

또한 List 인터페이스는 기본적으로 Collection 인터페이스 확장하여 사용합니다. Collection 인터페이스에 대한 개념이 없거나 놓치고 오신 분들은 아래 링크를 통해 학습하고 오시는 걸 추천드리겠습니다.

[언어(Programming Language)/Java] - [Java] Collection 개념

[Java] Collection 개념

 

 

개념

기본적으로 ArrayList, LinkedList 그리고 Vector는 사용하는 메서드는 비슷합니다.

 

Collection을 확장한 다른 Interface와 다르게 List Interface의 가장 큰 차이점은 배열처럼 "순서"가 있다는 것입니다.

즉, ArrayList와 LinkedList 그리고 Vector는 순서가 존재합니다.

 

이번 시간에는 데이터를 추가 메서드를 살펴보며 차이점에 대해 알아보겠습니다.

 

추가 add()

ArrayList

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

 

ArrayList에 새로운 데이터를 추가할 때 위 메서드 로직이 실행됩니다.

 

첫 번째 코드를 확인하면 매개 변수 값으로 element(요소) 추가하려는 데이터를 전달받습니다. 

그리고 modCount++; 을 실행하고 두 번째 add(e, elementDate, size) 메서드를 호출합니다.

 

여기서 modeCount는 ArrayList 자료구조가 얼마나 수정이 되었는지에 대한 횟수를 체크하는 필드입니다.

ArrayList가 AbstractList라는 클래스를 상속받으며 해당 필드는 AbstractiList에서 가져옵니다.

 

두 번째 메서드를 파악해 보겠습니다. elementData는 ArrayList의 요소가 저장되는 배열 버퍼입니다. 실제 ArrayList 내부 필드에 선언되어 있습니다.

 

transient Object[] elementData; // non-private to simplify nested class access

 

transient는 Serializable 클래스에 직렬화 대상에 제외시키겠다는 뜻입니다. (해당 주제는 나중에 설명하도록 하겠습니다.)

 

size는 ArrayList의 크기를 말합니다. 그럼 두 번째 코드를 마저 해석하면 현재 ArrayList 크기가 저장된 데이터 길이가 같다면 새롭게 데이터를 추가하는 로직입니다. 하지만 여기서 grow() 메서드를 알아야 합니다.

 

grow() 메서드를 살펴보겠습니다.

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 * @throws OutOfMemoryError if minCapacity is less than zero
 */
private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData,
                                       newCapacity(minCapacity));
}

private Object[] grow() {
    return grow(size + 1);
}

 

 

grow() 메서드 주석을 해석하면 다음과 같습니다. 최소 용량 인수로 지정된 요소 수 이상을 보유할 수 있도록 용량을 늘립니다.

 

grow 영어 단어 뜻만 해석해도 "커지다"라는 뜻을 가지고 있습니다. 즉, 해당 ArrayList에 데이터를 추가해 늘린다는 뜻입니다.

 

Arrays.copyOf(T[], newLength) 메서드는 현재 elementData의 값을 복사하고, newCapacity(minCapacity)값을 통해 새로운 길이를 가지는 배열을 생성합니다.

새로 생성한 배열을 기존의 elementDate에 새롭게 덮어씌우고 반환합니다. 

 

/**
 * Returns a capacity at least as large as the given minimum capacity.
 * Returns the current capacity increased by 50% if that suffices.
 * Will not return a capacity greater than MAX_ARRAY_SIZE unless
 * the given minimum capacity is greater than MAX_ARRAY_SIZE.
 *
 * @param minCapacity the desired minimum capacity
 * @throws OutOfMemoryError if minCapacity is less than zero
 */
private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length; // 0
    
    // >> 해당 연산자는 비트 연산자입니다.
	// 즉, oldCapacity >> 1 은 2로 나눈 몫을 반환하고 만약 나머지가 홀수이면 소수점은 버립니다.
    // 항상 값이 1입니다.
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    if (newCapacity - minCapacity <= 0) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return minCapacity;
    }
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
        // hugeCapacity(): newCapacity의 값을 최대 Integer.MAX_VALUE로 보정한다.
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE)
        ? Integer.MAX_VALUE
        : MAX_ARRAY_SIZE;
}

 

엄청 복잡하죠?... 하지만 우리는 주석을 한번 읽어보면 어느 정도 유추할 수 있습니다. 주석에 내용을 해석하면 다음과 같습니다.

 

주어진 최소 용량만큼의 용량을 반환합니다. 충분할 경우 현재 용량에서 50% 증가한 용량을 반환합니다. 주어진 최소 용량이 MAX_ARAY_SIZE 보다 크지 않는 한 MAX_ARRAY_SIZE 보다. 큰 용량은 반환하지 않습니다.라고 설명하고 있습니다.

 

저는 해석을 해도. 유추하기 어렵네요... 중요한 건 현재 배열의 크기를 늘리고 데이터를 추가한다고 이해하면 됩니다!!

 

Vector

 

Vector는 메서드 로직이 ArrayList와 동일합니다. 하지만 다른 부분이 하나 있습니다. 

/**
 * Adds the specified component to the end of this vector,
 * increasing its size by one. The capacity of this vector is
 * increased if its size becomes greater than its capacity.
 *
 * <p>This method is identical in functionality to the
 * {@link #add(Object) add(E)}
 * method (which is part of the {@link List} interface).
 *
 * @param   obj   the component to be added
 */
public synchronized void addElement(E obj) {
    modCount++;
    add(obj, elementData, elementCount);
}

 

위 코드를 보면 메서드 선언 시 synchronized를 선언했습니다. ArrayList와 다른 부분이 바로 synchronized입니다. 해당 키워드를 통해 Vector는 ArrayList 보다 Thread safe 합니다. Thread safe는 멀티 스레드 환경에서 안전하다는 뜻입니다.

 

고로 Vector는 Thread safe 하고 ArrayList는 Thread safe 하지 않습니다. 즉 멀티 스레드가 동시에 데이터를 변경하려고 할 때 문제가 발생합니다.

 

LinkedList

 

LinkedList는 ArrayList와 성격이 다릅니다.

ArrayList는 내부적으로 배열을 사용해서 데이터를 저장합니다. LinkedList는 내부적으로 Node와 링크(포인터)를 사용해서 데이터를 저장합니다.

 

아래 코드에서 Node 클래스를 확인하면 item 저장 시 이전 노드와 다음 노드에 대한 정보를 저장합니다.

 

public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

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;
    }
}

 

위 자료구조는 속도 그리고 메모리적인 측면에서 여러 가지 차이가 있습니다.

 

조회하는 부분에 대해서 설명은 다음 포스팅에서 설명하겠습니다.

메모리를 사용하는 부분에 있어서 다릅니다.

1. ArrayList는 객체를 새롭게 추가하거나 삭제할 때 할당받은 힙 메모리 용량을 늘렸다 줄였다 하면서 데이터를 저장합니다.

2. LinekdList는 새로운 Node를 생성할 때마다 각 노드가 힙 메모리에 독립적으로 할당되고, 이 노드들은 서로 연결되어 있습니다.
    노드 간의 연결이 객체 참조를 통해 이루어져 있기 때문에 데이터의 추가나 삭제가 발생할 때 해당 노드만 수정하면 되므로, 전체 데이터를 복사하거나 이동할 필요가 없습니다.

 

이번 시간에는 List 인터페이스 하위에 존재하는 ArrayList, Vectoer, LinekdList에 추가 기능에 대해 알아봤습니다.

이해가 가지 않으시는 분들은 댓글을 남겨 주시면 감사하겠습니다.