자료구조-배열(Array)

배열이란?

같은 타입의 변수들이 이루어져 있고 크기가 정해져 있으며 인접한 메모리 위치에 있는

데이터 집합이다.

또한 중복을 허용하고 순서가 있다.

속도

여기서 설명하는 배열은 정적 배열(크기가 정해진) 배열을 기반으로 설명하는데

탐색에는 O(1)이 되어 랜덤 접근이 가능하다.

삽입과 삭제는 O(n)이 걸린다.

따라서 데이터 추가와 삭제를 많이 하는것은 연결리스트

탐색을 많이 하는것은 배열로 하는 것이 좋다.

 

 

랜덤 접근과 순차적 접근

직접 접근이라고 하는 랜덤 접근은 동일한 시간에 배열과 같은 순차적인 데이터가

있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능이다.

이는 데이터를 저장된 순서대로 검색히 야한 순차적 접근과는 반대이다.

 

 

동적 배열 벡터(vector)

동적배열은 동적으로 요소를 할당할 수 있는 배열이다.

컴파일 시점에 개수를 모른다면 벡터를 써야한다.

또한 중복을 허용하고 순서가 있고 랜덤 접근이 가능하다.

 

탐색과 맨 뒤에 요소를 삭제하거나 삽입하는데 O(1)이 걸리며

맨 뒤나 맨 앞이 아닌 요소를 삭제하고 삽입하는데 O(n)의 시간이 걸린다.

 

참고로 push_back()의 경우 처음 벡터의 용량이 4일 때

계속 push_back으로 데이터를 삽입하다.

가득 찼을 경우에 1개의 용량이 증가되는 것이 아니라

해당 용량의 두 배가 채워지게 된다.

즉 4의 두 배인 8의 용량이 생기고 5번째 공간에 데이터가 들어가게 된다.