ArrayList vs LinkedList

1. 접근

ArrayList :  요소의 위치를 알면 인덱스로 바로 접근해서 시간복잡도가 O(1)이다.

 

LinkedList : 첫 노드부터 순차적으로 접근해야 되므로 시간 복잡도가 O(n)이다.

 

 

 

2. 삽입 및 삭제

ArrayList : 리스트 끝에 삽입하거나 삭제할 때의 시간복잡도는 O(1)이지만 그 외에는 다른 요소들을 복사해 이동시켜줘야 하므로 O(n)이다. (이와 같은 특징 때문에 Stack을 구현하기에 적합하다)

 

LinkedList : 첫 노드를 삽입하거나 제거할 때의 시간복잡도는 O(1)이지만 맨 끝에 삽입하거나 제거할 때는 맨 마지막 노드까지 접근해야 하므로 O(n)의 시간복잡도를 갖는다. (이와 같은 특징 때문에 Queue를 구현하기에 적합하다)

 

리스트 중간에 요소를 제거하거나 삽입할 때는 대체로 LinkedList의 처리속도가 더 빠르다.

 

 

 

4. 메모리 사용

ArrayList : 배열의 크기는 고정되어있으므로 요소가 배열의 크기를 벗어나면 더 큰 배열을 새로 생성해 기존 배열의 내용을 복사해 줘야 된다. 그렇다고 배열의 크기를 너무 크게 잡으면 메모리가 낭비된다.

 

LinkedList : 크기가 가변적이므로 요소들을 계속 추가해도 상관없다. 다만 배열리스트와는 다르게 next 포인터를 가지고 있어 배열리스트보다 더 많은 용량을 차지한다.