[JAVA] Array vs ArrayList vs LinkedList

데이터를 저장할 수 있는 자료구조에는 배열(Array), 리스트(List), 맵(Map), Set  등이 있다. 여기서 내가 자주 사용하는 배열과 리스트에 대한 차이점에 대해 간략하게 정리해두겠다.

 

 

 

 

		List
	Array	ArrayList	LinkedList
선형 vs 비선형	선형	선형	선형
순차 vs 연결	순차	순차	연결
크기	고정	가변	가변
접근	O(1)	O(1)	O(N)
삭제, 추가	중간 O(N) / 마지막 원소 O(1)	중간 O(N) / 마지막 원소 O(1)	접근하는 시간 O(N) / 삭제 및 추가 O(1)
빈 엘리먼트 허용	O	O	X

 

 

 

 

배열

 

배열의 특징은 다음과 같다.

 

- 메모리상에 선형 순차적으로 저장되고 0 부터 순서에 해당하는 번호가 붙는다.

- 한 번 생성된 배열의 길이는 변경할 수 없다.

- heap에 저장된다.

- 데이터가 순차적으로 저장되어 있는 선형 자료구조이다.

- Cashe hit rate이 높다.

 

 

Cache Hit Rate은 요청할 데이터를 캐시 메모리에서 찾을 확률을 말한다.

 

캐시 메모리 : CPU와 메모리의 속도 간극을 줄이기 위해 사용하는 고속 버퍼 메모리

 

자주 사용하는 데이터를 캐시 메모리에 저장하여 상대적인 속도가 상당히 느린 메모리에 접근하는 횟수를 줄이고자 사용한다. CPU가 메모리에 접근하기 전 캐시에서 데이터 존재 여부를 먼저 살펴보고 데이터가 있으면(hit) 메모리에 접근하지 않고 해당 데이터를 사용하고, 없으면 (miss) 메모리에 접근하여 필요한 데이터를 찾는다.  

 

캐시 메모리는 참조 지역성(Locality Of Reference)에 근거한다.

 

- 시간 지역성 : 최근에 참조된 주소는 빠른 시간 내에 다시 참조되는 특성

- 공간 지역성 : 참조된 주소와 인접한 주소의 내용이 다시 참조되는 특성

- 순차 지역성 : 데이터가 순차적으로 엑세스 되는 특성. 공간 지역성에 편입되어 설명되기도 한다. 

 

배열은 데이터가 메모리 상에 순차적으로 저장되기 때문에 공간 지역성이 좋아 높은 Cache Hit Rate을 가진다.

 

 

 

 

리스트 

 

리스트의 경우에도 heap에 저장되고 ArrayList와 LinkedList의 특징은 아래와 같다.

 

ArrayList

 

- 크기가 가변적인 배열 개념

- 탐색, 추가, 변경, 삭제 등의 작업에 드는 시간이 배열과 비슷한 모습

 

다만, ArrayList는 데이터를 추가할 때 배열과 달리 크기를 키운 후 새로운 공간에 기존 요소를 복사하고 원소를 추가한다. 따라서 평균적으로 데이터를 추가하는 경우가  Array보다 느리다. 이를 방지하기 위해서 ArrayList도 크기를 정해놓고 사용하곤한다. 

 

 

LinkedList

 

- 데이터가 선형적으로, 그러나 비순차적(연결)으로 저장되어 있음

- 이전 요소 포인터가 다음 요소 포인터를 가리킴

 

LinkedList의 경우 메모리 상에 비연속적으로 데이터가 저장되어 있기 때문에 앞에서 설명한 Cache Hit Rate이 낮다. 

 

 

 

 

 

 

 

 

 

참고

[자료구조] Array(배열) vs List(리스트)

 

[자료구조] 배열과 연결리스트 비교