Array, List가 메모리 상에서 어떤 식으로 동작하는지 생각하자.
Array
-
크기를 명시적으로 선언해야 한다.
ex. 선언시에 크기를 별도로 명시해 줘야 된다. / new int[4], new String[6] -
메모리 상에 데이터를 연속적으로 할당한다.인덱싱으로 Array에 할당된 데이터에 접근하기 때문에 O(1)의 시간이 걸린다.
-
Random Access로 탐색을 진행한다.
Random Access: 임의의 순서로 접근 탐색 / 시간 복잡도: O(1) -
삽입 / 삭제 시, 작업을 진행하려는 인덱스부터 마지막 원소까지 shift를 진행해야므로 삽입, 삭제 시에는 O(n)의 시간이 걸린다.
ArrayList
-
Array의 특징을 모두 갖는다. 단, 동적으로 크기를 선언 할 수 있다.
-
삽입 / 삭제 연산
-
맨 뒤에 원소 추가 / 삭제 시:
-
현재 ArrayList의 메모리 상에 다음 공간이 부족한 경우:
메모리에서 여유 있는 공간에 새로운 배열을 선언하여 이전 데이터 값을 복사하여 삽입 / 삭제 연산을 진행한다. -> O(n)의 시간 -
현재 ArrayList의 메모리 상에 다음 공간이 충분한 경우:
다음에 바로 값을 넣으면 되므로 O(1)의 시간
-
-
맨 뒤 외에 원소 추가 / 삭제 시:
- 연산을 진행하려는 위치 다음의 데이터를 shift 하므로 O(n)의 시간
-
-
내부적으로 Array 자료 구조를 이용하기에 O(1)의 시간이 걸린다.
LinkedList
-
동적인 크기를 가진다.
ex. 개발자의 편의대로 크기를 늘리거나 줄일 수 있다. -
메모리 상에서 이전 노드의 주소를 참조하고 있다.메모리에 빈틈 없이 데이터를 적재할 수 있다.
-
Sequential Access로 탐색을 진행한다.
Sequential Access: 순차적으로 앞에서부터 접근 탐색 / 시간 복잡도: O(n) -
삽입 / 삭제 시, 전체적인 데이터를 shift할 필요 없이 참조 주소만 갱신하면 되므로 O(1)의 시간이 걸린다.
Array vs ArrayList vs LinkedList 특징 정리
| 특징 | Array | ArrayList | LinkedList |
|---|---|---|---|
| 크기 선언 | 정적 | 동적 | 동적 |
| 메모리 데이터 분포 | 연속적 | 연속적 | 분산적 |
| 삽입 / 삭제 | O(n) | O(1) or O(n) 상황에 따라 다름 | O(1) |
| 탐색 | O(1) | O(1) | O(n) |
참고
