Array
- 논리적 저장 순서와 물리적 저장 순서가 일치.
- 특정 자료형들이 메모리 공간에 연속적으로 존재.
- 인덱스를 통해 .Random Access 가능 -> O(1)
- 삽입, 삭제 시에는 해당 인덱스 이후의 자료들이 Shift 됨 -> O(n)
- 일반적으로 Array 선언 시, Compile Time 에 정적 메모리 할당.
+ 가변 배열이 아닌 이상, 선언시의 Array Size 는 immutable.
=> 메모리 공간 활용 제약, 크기 초과시, 변경 시에 다른 주소에 재할당 필요!
Linked List
- 저장 공간상에 자료들이 흩어져 있고, 각 노드가 자신의 다음 노드의 주소를 지닌다 -> 자료 외에 별도의 포인터 저장 공간 필요.
=> 논리적 저장 순서와 물리적 저장 순서가 불일치. - 첫 노드의 주소만을 저장 했다가 필요 시 Sequential Access 를 통해 접근.
- 검색, 삽입, 삭제 시 모두 O(n) 소요.
=> 해당 위치를 찾는 데에 O(n) 소요되고, Array와 달리 Shift는 불필요하다.
=> 따라서, 삽입과 삭제가 맨 앞 노드에서만 이루어지게되는 특성의 링크드리스트라면, 삽입 삭제는 O(1)이 될 수 있다. - Run Time 에 동적 메모리 할당
Array VS Linked List
- 데이터 접근이 많이 일어나는 경우에는 배열 사용.
- 삽입 삭제가 많이 일어나는 경우에는 링크드 리스트 사용.
- 가변 배열 - 벡터, 리스트와 같은 자료형으로, 배열의 공간 활용 제약의 단점을 극복!
=> 공간에 여유가 있으면, append()를 사용하여 자료형 1개 크기 만큼 동적으로 사이즈 할당이 가능하고,
공간 활용에 제약이 생기면, resize()를 통해 크기 재할당 후 모든 원소를 이주할 수 있다(비용이 발생).
