학습계획

---

• ArrayList

Today I Learned

---

Array List의 주요 메소드들의 시간 복잡도는?

size(), isEmpty(), get(), set, iterator → O(n)

list에 담긴 요소의 수만큼의 시간 복잡도가 걸린다.

java.util 패키지의 컬렉션 프레임워크

• List, Set은 객체를 추가, 삭제, 검색하는 방법에 있어 공통점을 가지고 있어 Collection 인터페이스를 상속하고 있다.
• Collection 인터페이스는 요소들을 탐색하는 Iteratable 인터페이스를 상속받았다.

https://medium.com/javarevisited/how-to-create-an-immutable-list-list-and-map-in-java-5ac1254c128

ArrayList의 내부 구현 방식과 배열과의 차이점

ArrayList에 객체를 추가하면 내부배열에 객체가 저장된다.

일반 배열과의 차이는 ArrayList는 제한없이 객체를 추가할 수 있다.

Array

동일한 타입의 지정한 개수만큼 저장할 수 있는 object이다. Array 생성 시 지정한 size 만큼의 크기를 할당 할 수 있으며, 메모리의 연속적인 위치에 저장된다.

int array[] = new int[3];

ArrayList

ArrayList는 크기 조정 가능한 배열 자료구조이다.

add() 메소드를 통해 요소가 추가되거나 삭제 되면, list 객체 요소가 앞으로 당겨지거나 뒤로 밀어진다.

내부구현

ArrayList는 내부적으로 Object[] Object 타입의 배열로 구성되어있다.

transient Object[] elementData;

private static final int DEFAULT_CAPACITY = 10;

생성자를 통해 배열의 capacity를 설정할수 있으며, 설정하지 않은 경우 기본 DEFAULT_CAPACITY값이 적용된다.

An application can increase the capacity of an ArrayList instance before adding a large number of elements using the ensureCapacity operation. This may reduce the amount of incremental reallocation.

arrayList 생성시 기본 capacity는 있지만 큰 사이즈의요소를 저장할때는 사이즈를 선언하여 list를 선언하는것이 재할당의 양을 줄일 수 있다.

List는 동기화가 되지 않아서 멀티쓰레드 환경에서 동기화를 위해서는 아래와같이 동기화 할 수 있다.

List list = Collections.synchronizedList(new ArrayList());

❓ArrayList의 크기가 변경되면 내부 배열을 어떻게 재할당하나요? 이 과정에서 어떤 상황에서 성능이 저하되나요? 또한, ArrayList에 primitive type을 저장하고 싶다면 어떻게 해야 하나요?

ArrayList에 데이터를 추가하고 어떤 메서드가 호출되는지 확인해보자

public class StringBufferTest {
	public static void main(String[] args) {
		ArrayList<String> list = new ArrayList();
		list.add("test!");
		list.add("test1!");
		list.add("test2!");
		list.add("test3!");
		System.out.println("list.size() = " + list.size());
		list.add("test");
		list.add("test2");
		list.add("test3");
	}
}

1. new ArrayList();가 선언되면 Object[] 배열이 elementData에 할당된다.

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

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

1. ArryaList에 add()메서드로 추가될때 add(e, elementData, size)가 호출된다.
2. add(e, elementData, size)메서드에서 list의 size s와 list가 가지고있는 데이터 elementData의 size가 같을 경우 if문을 탄다. size가 같지 않을 경우 elementData배열에 추가되고 size를 늘린다.
3. if문을 탈 경우 grow메서드를 호출하면서 size+1 파라미터로 전달한다.
4. Arrays.copyOf()메서드를 호출시 elementData,새로 구한 길이값을 전달하여 배열을 복사한다.
5. 넘긴 배열 파라미터가 Object[]과 타입이 같으면 copy라는 변수에 Object[]초기화 하고, 아닌 경우 새로운 타입의 배열을 선언한다. 마지막으로는 System.arraycopy 메서드를 통해 배열의 0번째부터 복사한다.

public boolean add(E e) {
        modCount++;//변경된 element가 들어온 만큼 증가 
        add(e, elementData, size);
        return true;
    }

private void add(E e, Object[] elementData, int s) {
//list의 size s와 list가 가지고있는 데이터 elementData의 size가 같을 경우 if문을 탄다
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;//size가 같지 않을 경우 elementData배열에 추가되고 size를 늘린다.
        size = s + 1;
    }

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

private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }

private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        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);
    }

@HotSpotIntrinsicCandidate
    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

ArrayList의 추가, 삭제로 인해 resize시 새로운array로의 복사이므로 데이터 복사가 빈번히 발생하여 성능이 저하될수있다.

빈번한 객체 삭제와 삽입이 일어난다면 LinkedList를 사용하는것이 좋다.

ArrayList는 내부적으로 Object[]배열이므로 primitive type을 저장할 수없다. 하지만 java의 Autoboxing기능으로 인해 primitive type도 저장이 가능하다.

int → Integer , boolean → Boolean , double → Double, byte → Byte