일반적으로 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()를 통해 크기 재할당 후 모든 원소를 이주할 수 있다(비용이 발생).
