[Java] 1주차 스터디 - 파이썬 list 자바 Array, ArrayList 에 대해!

1. Array

• 연관된 data를 메모리상에 연속적이며 순차적(ordered)으로 미리 할당된 크기(fixed-size)만큼 저장하는 자료구조
• 장점: 조회가 매우 빠름
• 단점: 미리 할당된 크기를 선언해야하므로 메모리 낭비 또는 할당된 사이즈를 넘는 경우 문제 발생
• 시간복잡도
  • 조회: O(1)
  • 추가: O(1)
  • 삽입, 삭제: O(n)

2. Python - list와 Java - ArrayList

1) Python의 list와 Java의 ArrayList 내부 로직 - Dynamic Array

• 거의 동일하므로 [ Java-ArrayList = Python - list ]로 생각하면 세상 쉽다!
  • [차이점] Python-list에서는 Object의 주소값이 들어가서 타입 제한 없이 요소가 될 수 있다.
• 내부로직(Dynamic Array): Array의 fixed-size 단점을 보완하기 위한 자료구조이다. 간단하게 설명하면 Java-ArrayList가 동적배열이긴 하나 기본적으로 설정된 크기(default-capacity)가 존재하는데 요소가 추가될 때마 size가 1씩 증가한다. capacity와 size가 같아져 더 이상 공간이 없을 경우 Resize를 한다. Resize에는 여러 방법이 존재하는데 대표적인 방법으로는 Doubling이 존재한다. 메모리를 초과하게 되면 기존 배열의size보다 두배 큰 배열을 선언하고 데이터를 일일이 옮긴다.
• Resize가 발생할 때의 시간복잡도는 어떻게 될까?
  • 평균적으로 O(1)의 시간복잡도를 가진다.
    • Doubling을 가정하고 길이 N을 2^x 라고 할 때, add를 N번 시행하면 할당 연산이 총 N번, 복사 연산은 2N번 발생 한다
    • 1+2+4+8 ... 2^x(N) = 2^(x+1) = N * 2  
    • N번 시행에 총 3N의 연산 발생. 회당 평균 시간 복잡도는 O(3N/N) = O(3) = O(1)

2) ArrayList의 add 아는 선에서 최대한 뜯어보기!

// ArrayList 내부 
private static final int DEFAULT_CAPACITY = 10;

private int size;

// 요소가 추가될 때..
public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}


/**
 * This helper method split out from add(E) to keep method
 * bytecode size under 35 (the -XX:MaxInlineSize default value),
 * which helps when add(E) is called in a C1-compiled loop.
 */
private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

private Object[] grow() {
    return grow(size + 1);
}
//
/**
 * 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) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        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)];
    }
}

public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
    // preconditions not checked because of inlining
    // assert oldLength >= 0
    // assert minGrowth > 0

    int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
    if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
        return prefLength;
    } else {
        // put code cold in a separate method
        return hugeLength(oldLength, minGrowth);
    }
}

• prefLength = oldLength + Math.max(minGrowth, prefGrowth)인데 prefGrowth는 'oldCapacity >> 1' 즉, 절반(비트연산)에 해당한다. 따라서 resize된 크기는 prefLength가 반환될 시에 기존 크기의 최대 1.5배만큼 늘어나게 된다.
• 크기가 최대 1.5배가 된 배열이 생성이 되고 elementData의 요소들이 복사된다.
• 그 후 elementData[s] = e로 요소가 추가된다.
• size 를 1 증가시키고 add 종료된다. 

3. Array와 ArrayList 

• ArrayList 왜 권장할까?
  • Python-list를 사용하다가 Java-Array 만나면 굉장히 답답하다. 그 이유는 append, remove, pop, del, clear, index 등의 메서드가 너무~너무 부족하다. 
  • 컬렉션 ArrayList 만나면 이미 구현해놓은 메서드가 많아져서 사용하기 매우 간편하다. 
  • 따라서 Array 보다 ArrayList 쓰는 가장 근본적 이유는 메서드가 많아서 쓰기 편해서 그런 것 같다.
• ★메서드 종류(https://happy-ryan.tistory.com/34)★

	Array	ArrayList
성격	정적배열	동적배열
요소의 개수	length()	size()
요소 추가	인덱스로 접근해서 추가	add()

4. 학습 필요

 1) " 배열은 제네릭 사용 불가능, ArrayLis 제네릭 사용 가능"

    → 제네릭이 무엇인가?