[Java] Array와 List 상황별 성능 비교

Array(배열)

• 여러 데이터를 하나의 이름으로 그룹핑해서 관리 하기 위한 자료구조. index와 값의 쌍으로 구성
• index는 값에 대한 유일무이한 식별자(마치 주민번호)( 리스트에서 인덱스는 몇 번째 데이터인가 정도의 의미를 가짐)
• 논리적 저장 순서와 물리적 저장 순서가 일치 => index로 해당 원소에 접근할 수 있다. (O(1))
• 연속된 메모리의 공간으로 이루어져 있다
• 배열은 정의와 동시에 길이를 지정하며 길이를 바꿀 수 없다.

 

장점

• 인덱스를 통한 검색이 용이함.
• 연속적이므로 메모리 관리가 편하다.

단점

• 크기가 고정되어 있기 때문에 어떤 엘리먼트가 삭제되면, 삭제된 상태를 빈 공간으로 남으므로 삽입/삭제 연산에 불리함.
• 정적이므로 배열의 크기를 컴파일 이전에 정해주어야 한다.
• 컴파일 이후 배열의 크기를 변동 할 수 없다.

 

 

List

• 리스트는 순서가 있는 엘리먼트의 모임으로 배열과는 다르게 빈 엘리먼트는 절대 허용하지 않는다.
• 리스트는 배열이 가지고 있는 인덱스라는 장점을 버리고 대신 빈틈없는 데이터의 적재 라는 장점을 취함
• 리스트에서 인덱스는 몇 번째 데이터인가 정도(순서)의 의미를 가진다. (배열-Array에서의 인덱스는 값에 대한 유일무이한 식별자)
• 빈 엘리먼트는 허용하지 않는다. => java에서는 허용하는 경우가 있음
• 순차성을 보장하지 못하기 때문에 spacial locality 보장이 되지 않아서 cash hit가 어렵다.(데이터 갯수가 확실하게 정해져 있고, 자주 사용된다면 array가 더 효율적이다.)
• 불연속적으로 메모리 공간을 차지.
• 포인터를 통한 접근

장점

• 포인터를 통하여 다음 데이터의 위치를 가르켜고 있어 삽입/삭제의 용이.
• 동적이므로 크기가 정해져 있지 않다.
• 메모리의 재사용 편리
• 불연속적이므로 메모리 관리의 편리

단점

• 검색 성능이 좋지 않다.
• 포인터를 통해 다음 데이터를 가르키므로 추가적인 메모리 공간 발생.

 

 

비교 정리

	삽입 / 삭제	조회	메모리 관리	검색	크기변경
Array 배열	느림	빠름	어려움	쉬움	불가능
List	빠름	느림	쉬움	어려움	가능

 

• 배열 : 데이터의 크기가 정해져 있고, 추가적인 삽입 삭제가 일어 나지 않으며 검색을 필요로 할 때 유리.

 

• 리스트 : 데이터의 크기가 정해져 있지 않고, 삽입 삭제가 많이 일어나며, 검색이 적은 경우 유리.