Array

array: 값 또는 변수 엘리먼트의 집합으로 구성된 구조로, 하나 이상의 인덱스 또는 키로 식별된다.

array는 메모리 공간 기반의 연속 방식의 가장 기본이 되는 자료형이다.

연결 방식의 가장 기본이 되는 자료형은 linked list이다.

추상 자료형 Abstract Data Type의 실제 구현 대부분은 array 또는 linked list를 기반으로 한다.

stack은 linked list로 구현하고, queue는 array로 구현하는 식이다.

배열은 크기를 지정하고 해당 크기 만큼의 연속된 메모리 공간을 할당받는 작업을 수행하는 자료형을 말한다. 크기가 고정되어 있으며, 한번 생성한 배열은 크기를 변경하는 것이 불가능 하다.

배열은 어느 위치에나 시간 복잡도가 O(1)이다.

배열은 고정된 크기만큼의 연속된 메모리 할당이지만 실제 데이터에서는 자동으로 크기를 조정할수 있는 배열인 동적 배열이 존재한다.

자바에서는 ArrayList 파이썬에서는 List 가 동적 배열 자료형이다. 다만 파이썬에서는 정적 배열 자료형을 따로 제공하지는 않는다.

https://github.com/python/cpython/blob/main/Objects/listobject.c
CPython에서는 동적 배열인 리스트의 구현을 listobject.c에 정의해 놨는데 growth pattern이 0, 4, 8, 16, 24, 32, 40… 인 것을 확인 할 수 있다.

java에서는 java.util.ArrayList.java를 확인해보자

private static final int *DEFAULT_CAPACITY* = 10;

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)];
        }
    }

java.internal.util.ArraysSupport.java

int prefLength = oldLength + Math.*max*(minGrowth, prefGrowth);

정적 멤버로 디폴트 용량이 10으로 설정되어 있으며 growth는 minCapacity - oldCapacity, oldCapacity/2 중 하나로 설정된다.
minCapacity는 oldCapacity + 1이다.

즉 ArrayList의 용량은 1개만 늘어나거나, 1.5배가 된다는 의미