[DataStructure] ArrayList (Java)

ArrayList

참고링크

public class ArrayList<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, Serializable

설명

일반 배열과 다르게 크기를 지정하지 않아도 되며
제너릭으로 타입을 지정할 수 있는 장점이 있는 자료구조이다.

순서가 보장되며, 처음 디폴트 사이즈는 10이고 지정한 사이즈를 초과하게되면 내부적으로 Object 배열을 사용해서 더 큰 사이즈의 배열을 만들고 기존 Object 배열을 복사해서 사이즈를 자동적으로 늘립니다.

사용법

import java.util.ArrayList;
ArrayList arrayList = new ArrayList();
arrayList.add(Object);
arrayList.get(0);

시간복잡도

n개의 요소에서 add할때 = 보통은 O(1)이지만 최악의 경우 배열을 새로 만들어서 복사할 때는 O(n)
n개의 요소에서 get할때 = O(1)
참고링크

공간복잡도

대부분의 Collection들은 O(n)
참고링크
참고링크