Java 자료구조 Collection ArrayList [1]

좋은 개발자가 되기 위해서는 기본기가 튼튼해야 된다고 강하게 생각이 든 계기가 있었습니다.

그래서 이번에는 자료구조부터 다시 정리하려고 합니다! 

 

이번에는 ArrayList에 대해서 먼저 다뤄보도록 하겠습니다.

 

ArrayList는 배열의 크기가 동적으로 변할 수 있는 자료구조입니다. 

실제 스프링 프로젝트에서도 많이 사용하고 알고리즘 풀이에도 많이 사용되는 자료구조입니다.

 

ArrayList는 동적!

즉, 일반 배열과는 다르게 정해진 크기보다 초과로 더 커지게 되면 자동으로 배열의 크기를 늘리는 것입니다!

 

역시, 글보다 코드가 더 와닿을 수 있죠?!!

 

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable {
    private static final long serialVersionUID = 8683452581122892189L;
    private static final int DEFAULT_CAPACITY = 10; // 처음 Init시 만들어지는 크기!
    private static final Object[] EMPTY_ELEMENTDATA = new Object[0];
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new Object[0];
    transient Object[] elementData;
    private int size;

 

이렇게 List를 상속받아 구현된 ArrayList의 구현체입니다.

 

이것을 처음 생성시킬 때는 아래와 같은 방식으로 생성이 됩니다.

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else {
        if (initialCapacity != 0) {
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        }

        this.elementData = EMPTY_ELEMENTDATA;
    }

}

 

이처럼, ArrayList를 생성할 때 배열의 크기를 지정하지 않고 생성하면 기본으로 10의 크기인 동적 리스트가 만들어지게 되는 것입니다!

 

ArrayList<Integer> integerArray = new ArrayList<>();

 

그럼 ArrayList의 시간 복잡도는 어떻게 될까요?

 

데이터 추가

public void add(int index, E element) {
    if (index > this.size || index < 0) {
        throw new IndexOutOfBoundsException(this.outOfBoundsMsg(index));
    }
    ++this.modCount;
    int s;
    Object[] elementData;
    if ((s = this.size) == (elementData = this.elementData).length) {
        elementData = this.grow();
    }

    System.arraycopy(elementData, index, elementData, index + 1, s - index);
    elementData[index] = element;
    this.size = s + 1;
}

- 앞이나, 중간에 추가 : O(N)

- 마지막에 추가 : O(1)

 

데이터 삭제

public E remove(int index) {
    Objects.checkIndex(index, this.size);
	
    if (this.root.modCount != this.modCount) {
        throw new ConcurrentModificationException();
    }
    
    E result = this.root.remove(this.offset + index);
    
    SubList<E> slist = this;
    
    do {
        slist.size -= 1;
        slist.modCount = this.root.modCount;
        slist = slist.parent;
    } while(slist != null);
    
    return result;
}

- 앞, 중간 삭제 : O(N)

- 마지막 삭제 : O(1)

 

public E get(int index) {
    Objects.checkIndex(index, this.size);
    return this.elementData(index);
}

데이터 조회 (인덱스를 통한 조회) : O(1)

 

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1; // 요소가 리스트에 없으면 -1을 반환
}

데이터 검색 : O(N)

 

이를 표로 보자면

ArrayList<Integer> array = new ArrayList<>();

데이터 삽입	마지막 : array.add(100) : O(1)
	앞, 중간 : array.add(0, 100) : O(N)
데이터 삭제	마지막 : array.remove() : O(1)
	앞, 중간 : array.remove(1) : O(N)
데이터 조회(인덱스)	array.get(1) : O(1)
데이터 검색	array.indexOf(1) : O(N)

 

이렇게 정리할 수 있겠습니다.

 

또한, 이렇게 구현이 되어있는 ArrayList는 장점과 단점으로 살펴볼 수 있습니다.

 

장점 :
- index를 이용한 조회는 매우 빠르게 접근하여 값을 받아올 수 있다.

- 마지막의 삽입, 삭제에 대해서는 O(1)로 매우빠르다.

 

단점 :

- 배열을 점차 늘리는 것이기 때문에 아직 할당되지 못한 배열의 범위에 대해서 메모리 소요가 있다.

 

프로젝트 혹은 알고리즘을 사용할 때 ArrayList의 장점과 단점, 시간복잡도를 고려하면서 문제를 풀면 좀 더 쉽게 접근할 수 있을 것 같습니다!