Array와 List

Array

• 논리적인 주소와 물리적인 주소가 같다 -> O(1)
• 시작점만 알면 연속적인 주소이므로 바로 찾을 수 있다. (연속된 메모리 공간)
• 여러 데이터를 하나의 이름으로 그룹핑해서 관리
• index(값에 대한 식별자)와 값의 쌍으로 구성
• 길이 바꾸기 불가

 장점

• index를 통해 검색 용이
• 메모리 관리 편리 (연속적이기 때문)

 단점

• 메모리 낭비 (크기 고정 → 삭제된 인덱스 자리는 빈공간으로 남아있음)
• 정적이므로 컴파일 이전에 배열 크기 부여해야 함
• 컴파일 후 배열 크기 변경 불가

---

List

• 빈 엘리먼트 허용하지 않음 = 빈틈없는 데이터의 적재
• 포인터를 통한 접근 → 특정 인덱스 값을 찾을 때 Array보다 오래 걸림
• 인덱스 : 몇 번째 데이터인가 정도(순서)의 의미를 가짐. 식별자 X
• 순차성을 보장하지 못함 -> spacial locality보장되지 않아서 cash hit 어려움
• 불연속적으로 메모리 공간 차지

 장점

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

 단점

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

    [ 		Value	 	|	 	*next 		]
    	   (현재 값)  		(다음 값의 주소)

---

Array vs List

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

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

---

참고 자료