[201 Created] 1주차 Java Collection - Array와 ArrayList의 차이

 코딩테스트 준비를 하면서 자주 사용했던 Array와 ArrayList의 차이가 무엇일까? 생각나는건 Array 배열은 크기가 고정되어있고, ArrayList는 크기가 유동적이라는 것이다. 둘의 차이가 이 뿐이진 않을거 같아서 찾아봤다.

 

Array와 ArrayList의 차이

• Array : 같은 데이터 타입의 변수들로 이루어진 자료구조
• ArrayList 
  
  • 자바에서 다수의 데이터를 쉽고 효과적으로 처리할 수 있는 표준화된 방법을 제공하는 클래스의 집합을 Collection Framework라고 한다. 이러한 Collection Framework 자바의 인터페이스를 사용하여 구현되며, List는 Collection Framework의 주요 인터페이스 중 하나이다.
  • List 인터페이스는 순사거 있는 데이터 집합으로, 데이터의 중복을 허용한다.
  • Collection Framework에 속하는 인터페이스를 구현한 클래스를 Collection Class라고 부른다. List Collection Class 중 하나가 ArrayList이다.

 

 결론부터 말하면 Array와 ArrayList의 차이는 다음과 같다.

	Array	ArrayList
Static / Dynamic	정적	동적
Resizable	고정된 크기	유동적인 크기, 필요할 때 resize 가능
Performance	resize시 ArrayList보다 속도가 빠름.	ArrayList는 resizing 하는 동안 내부적으로 Array의 지원을 받음.
Primitive / Generic type	Primitive type, Object	Object
Iteration Values	for loop 또는 for each loop를 통해 Array를 순회	Iterator를 사용해 ArrayList를 순회
Type-Safety	특정 데이터 타입의 Primitives나 Objects만을 저장	Generic을 통해 Type-safety를 보장
Length	Array의 길이를 반환하는 length 변수	size() 메소드
Adding Elements	Assignment operator(=)를 사용하여 요소를 추가	add() 메소드를 사용하여 요소를 추가
Single / Multi-Dimnesional	Multi-Dimensional	Single-Dimensional

 

 ArrayList에서 값을 추가할 때 어떻게 사이즈가 변하는지 궁금하여 ArrayList.java 클래스에 들어가봤다.

 ArrayList.add()에는 다음과 같은 세가지 add() 메소드가 있다.

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

public void add(int index, E element) {
        rangeCheckForAdd(index);
        modCount++;
        final int s;
        Object[] elementData;
        if ((s = size) == (elementData = this.elementData).length)
            elementData = grow();
        System.arraycopy(elementData, index,
                         elementData, index + 1,
                         s - index);
        elementData[index] = element;
        size = s + 1;
}

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

 

 보면 size()를 호출할 때 return 하는 size의 값의 변화만 있을 뿐 ArrayList의 사이즈 변화는 보이지 않았다.

 이번엔 grow() 메소드들과 그와 관련된 메소드들을 ArraysSupport.java 클래스에서 찾아봤다.

//ArrayList.java
private Object[] grow() {
        return grow(size + 1);
}

private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        	//newCapacity : 크기를 늘릴 때 사용되는 변수
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else {
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
}

//ArraysSupport.java
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
        // preconditions not checked because of inlining
        // assert oldLength >= 0
        // assert minGrowth > 0
		
        //prefLength는 원래 배열의 크기에 1.5배 값을 가진다.
        int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
        if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
        	//prefLength가 정상 범위 내에 있다면 원래 배열의 크기에 1.5배
            return prefLength;
        } else {
            // put code cold in a separate method
            return hugeLength(oldLength, minGrowth);
        }
}

private static int hugeLength(int oldLength, int minGrowth) {
        int minLength = oldLength + minGrowth;
        if (minLength < 0) { // overflow
            throw new OutOfMemoryError(
                "Required array length " + oldLength + " + " + minGrowth + " is too large");
        } else if (minLength <= SOFT_MAX_ARRAY_LENGTH) {
            return SOFT_MAX_ARRAY_LENGTH;
        } else {
            return minLength;
        }
}

newcapacity, prefLength 변수와 newLength 메소드를 유심히 살펴보자. 

예를 들어, 사이즈가 6인 ArrayList 가득 차있다고 하자. 여기에 element 4를 추가하려 할 때, capacity가 1.5배로 늘어나게 되고 크기가 늘어난 배열에 기존 ArrayList의 값들을 copy한다. 이러한 원리로 ArrayList가 동적으로 크기가 늘어날 수 있는 것이다.

 

 즉, 실제로 가지고 있던 용량이 꽉 찼을 때, 용량이 기존의 1.5배를 늘린 새로운 배열에 기존 배열을 copy하는 것이다.

 

 

출처 & 참고

https://mong9data.tistory.com/132

https://zorba91.tistory.com/287

https://velog.io/@humblechoi/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Array-vs-ArrayList

https://www.javatpoint.com/difference-between-array-and-arraylist