O(1)
만큼의 시간이 걸린다.O(n)
만큼의 시간이 소요된다.기존에 있던 ArrayList의 크기보다 더 큰(일반적으로 2배) 새로운 ArrayList을 생성하고 기존 ArrayList의 요소 값들을 하나씩 새로운 ArrayList로 복사한다.
기존 ArrayList에 있는 모든 요소에 이러한 연산을 진행하므로 O(n)
의 시간만큼 소요된다.
즉, 작은 크기의 ArrayList을 사용할 경우 메모리를 절약할 수 있지만 resize
하는 과정에서 많은 시간이 걸리게되는 trade-off
가 발생한다.
마지막 요소에 대한 연산이 빈번할 때 사용하거나 인덱스 기반으로 요소를 접근할 때 사용하는 것이 좋다.
ArrayList의 가득찼을 경우 resize
연산이 동반되기 때문에 성능 저하를 가져올 수 밖에 없다.
같은 타입의 요소들만 저장할 수 있다.
O(1)
만큼 소요된다는 것이다.노드
에 대한 참조 값만을 갱신하면 된다.Random Access
가 불가능하므로 LinkedList의 모든 요소를 탐색해야 하기 때문에 O(n)
만큼의 시간이 소요된다.포인터
를 갖고 있으므로 해당 위치에서 연산을 수행할 땐 O(1)
만큼의 시간이 걸린다.O(n)
만큼의 시간이 걸린다.Random Access
가 불가능하기 때문에 요소를 탐색하는데에는 시간이 오래걸린다.public static void main(String[] args) {
long start = System.currentTimeMillis();
ArrayList<Integer> arrayList = new ArrayList<>();
for (int i = 1; i <= 500000; i++) {
arrayList.add(0, i);
}
System.out.println("ArrayList : " + (System.currentTimeMillis() - start));
start = System.currentTimeMillis();
LinkedList<Integer> linkedList = new LinkedList<>();
for (int i = 1; i <= 500000; i++) {
linkedList.addFirst(i);
}
System.out.println("LinkedList : " + (System.currentTimeMillis() - start));
}
[출력 결과]
ArrayList : 12226
LinkedList : 16
ArrayList
와 그렇지 않은 LinkedList
간의 성능 차이가 많이 나는 것을 확인할 수 있다.