spatial locality, time locality 개념에 대해 설명

메인메모리의 데이터를 더 빠르게 동작하는 캐시메모리에 적재할 때 사용되는 원리이다. time locality는 한번 사용된 데이터는 바로 다시 사용될 확률이 높다는 의미이고, 따라서 한번 사용된 메모리는 바로 캐시메모리에 적재된다. spatial locality는 한번 사용된 데이터의 주변 데이터들도 곧바로 사용될 가능성이 높다는 의미이고, 따라서 한번 데이터가 사용될 때 해당 데이터의 주변 데이터들까지 캐시메모리에 적재된다.

배열에서 인덱싱이 구체적으로 어떻게 일어나는지 설명해주세요

배열은 내부적으로 데이터들이 메모리에 인접하게 위치하고, 모든 데이터의 타입이 같다는 특성이 있다. 따라서 접근하고자 하는 데이터가 몇번째인지 인덱스만 알면 주소값을 계산할 수 있다. 데이터가 아무리 많아도 이러한 산술계산은 매우 빠른시간에 끝나기 때문에, 데이터에 바로 접근이 가능하다.

동적배열에 대해서 설명해주세요

배열은 인덱스 접근이 매우 빠르다는 장점이 있지만, 최초 할당시에 고정된 메모리를 사용해야 한다는 한계가 있다. 동적배열은 배열의 두번째 한계를 극복한 것이다. 데이터의 갯수가 많아지거나 적어질 때, 내부배열의 크기를 2배로 늘리거나 2배로 줄여서 “데이터의 갯수에 맞춰 내부배열의 크기를 변경” 시키는 동작을 한다. 이렇게 함으로써 인덱스 접근은 배열을 사용해 매우빠르게 가져가고, 메모리 낭비를 줄이고, 저장가능한 데이터갯수를 동적으로 변경시키는 것이 가능하다.

동적배열의 삽입삭제를 빅오노테이션으로 표현하면?

데이터가 가득 찼을 때 데이터 갯수를 2배로 늘린다. 즉, N번의 삽입연산을 하면 N번의 데이터옮기기 연산을 한다. 평균을 내보면 한번의 삽입연산당 1이라는 연산횟수가 나온다. 데이터 갯수가 매우 크다는 가정을 하면, 이러한 경우는 매우 드물게 일어나기 때문에 O(1)이라고 말할 수 있다.

배열과 링크드리스트 비교해주세요

배열
배열은 데이터가 메모리공간에서 연속적으로 위치한다. 따라서, 캐시의 공간 지역성 원리에 의해 조회시에 높은 성능을 가질 확률이 높다.
그러나, 첫 할당시에 전체 메모리공간을 미리 할당해야 하며, 이 때문에 메모리 비효율적인 현상이 발견된다
링크드리스트
그때그때 메모리를 동적할당하여 데이터를 추가하므로 필요한 메모리공간만 사용 가능하다. 그러나 모든 메모리가 인접하게 위치하지 않아 인덱스접근이 순차적이라는 한계가 있다.
또한 데이터갯수가 많을 경우, 힙메모리에 여기저기 데이터주소가 분산되어 있기 때문에 캐쉬 친화적이지 않다.