이 글은 Java 자료구조 - Collection 의 구성 중 하나 입니다.

Java 배열이 가지는 문제와 대안책

Java 에서는 초기에에 Array라는 배열을 사용하였고 Array의 배열의 길이를 동적으로 변경할 수 없는 단점을 보완하기 위해 Java 1.0 부터 Vector를 이용해왔습니다. 하지만 Vector도 기본 Capcity가 10으로 정해져있었고 리스트의 개수가 해당 Capacity 이상이 되면 2배씩 용량을 늘리는 전략을 사용과 함께 동기화를 보장해 주기 때문에 성능 이슈가 발생 할 가능성이 있었습니다. 이와 같은 성능 이슈 때문에 스레드 안전을 보장하지 않지만 동적으로 배열이 변경되며 성능상에서 이점을 가져갈 수 있는 ArrayList와 LinkedList가 Java 1.2부터 등장하게 됩니다.

List

List는 여러 언어에서 유용하게 사용되는 자료구조중 하나입니다. Java에서의 List는 인터페이스로 되어있으며 대표적인 List의 인터페이스를 상속받는 객체는 Vector, ArrayList, LinkedList 가 있습니다.

List Interface

List Interface의 주요 메서드는 다음과 같이 구현되어 있습니다.

package java.util;

import java.util.function.UnaryOperator;

public interface List<E> extends Collection<E> {
    
    int size();
   
    boolean isEmpty();
    
    boolean contains(Object o);
    
    Iterator<E> iterator();
    
    Object[] toArray();
   
    boolean add(E e);
    
    boolean remove(Object o);
    
    boolean containsAll(Collection<?> c);
    
    boolean addAll(Collection<? extends E> c);
    
    boolean addAll(int index, Collection<? extends E> c);
    
    boolean removeAll(Collection<?> c);
   
    boolean retainAll(Collection<?> c);

    default void replaceAll(UnaryOperator<E> operator) 
   
    default void sort(Comparator<? super E> c) 
    
    void clear();
    
    boolean equals(Object o);
    
    int hashCode();
    
    E get(int index);

    E set(int index, E element);

    void add(int index, E element);
   
    E remove(int index);
    
    int lastIndexOf(Object o);
    
    ListIterator<E> listIterator();

    ListIterator<E> listIterator(int index);

    List<E> subList(int fromIndex, int toIndex);
}

ArrayList

ArrayList는 데이터들을 배열과 같이 관리하며, 추가 및 삭제가 발생할 때 임시 배열을 생성하여 데이터를 복사하여 동적으로 크기(Capacity)를 늘리는 방법을 사용하고 있습니다. 하지만 이런 방법은 많은 양의 데이터를 추가, 삭제 하는 경우에 그만큼 데이터의 복사가 많이 일어나게 되어 성능 저하를 일으킬 수 있습니다.

반면 ArrayList는 Index를 가지고 있기 때문에 검색시 Index를 통한 한번의 참조가 가능해 데이터에 검색에는 유리한 장점이 있습니다.

LinkedList

LinkedList는 각 노드가 이전 노드와 다음 노드의 포인터(상태)를 가지고 한 줄로 연결되어있는 방식으로 데이터를 저장하는 자료 구조입니다. ArrayList와 달리 추가,삭제시 데이터의 복사 없이 추가, 삭제 가능하여 성능상 이점을 가져갈 수 있습니다.

반면 LinkedList는 데이터를 검색하는데에 있어서는 첫번쨰 노드부터 순차적으로 탐색해야 하기 때문에 데이터 검색에는 불리한 단점이 있습니다.

성능비교

삽입, 삭제

ArrayList의 경우 다른 데이터를 복사해야 하기 때문에 O(n)의 시간복잡도를 가집니다.

LinkedList의 경우 이전 노드와 다음 노드의 참조하는 상태만 변경하면 되기 때문에 O(1)의 시간 복잡도를 가집니다.

검색

ArrayList의 경우 Index 기반의 자료구조이기 때문에 get(int index) 함수를 통해서 찾을 경우 O(1)의 시간 복잡도를 가집니다.

LinkedList의 경우 검색 시 모든 요소를 탐색해야 하기 때문에 O(n)의 시간 복잡도를 가집니다.

출처

• Oracle

• 안녕 프로그래밍