[자료구조] 배열 | Array

배열은 가장 기본적인 자료구조입니다.

동일한 자료형의 유한한 집합을 말하며, 배열의 각 요소는 0부터 시작하는, 인덱스[index]를 통해 나타냅니다.

 

배열은 크게 동적배열과 정적배열 [dynamic Array/ static Array]로 구분할 수 있으며, 

정적 배열은 반드시 컴파일 시기에 크기를 지정해주어야 하나, 동작 배열은 크기의 변경이 가능합니다.

배열의 메모리 저장 방식

 

1차원부터 2,3,... n차원 배열을 구현할 수 있으며, (각 차원별 길이의 곱 * 자료형 크기)만큼의 byte를 필요로 합니다.

 

 

C언어에서의 배열 선언은 다음과 같습니다.

#정적배열 선언
// 자료형 배열이름[크기];
int array[5]; // 길이 5칸짜리 int형 배열을 선언 (20bytes)
int array[5] = {0,} // 0으로 채워진 길이 5칸짜리 int형 배열을 선언 
int array[] = {1,2,3,4,5}; //1,2,3,4,5의 값을 가지는 5칸짜리 배열을 선언

#동적 배열 선언 --> malloc 사용
// 자료형* 배열이름 = (자료형*)malloc(sizeof(자료형) * 배열 길이);
int* dynamicArray = (int*)malloc(sizeof(int)*10);
~~~~
free(dynamicArray) // #메모리 해제를 해주어야 함

위와 같이, 배열은 선언과 동시에 초기화가 가능하며, 초기값을 지정해주면 크기를 따로 명시하지 않고도 선언이 가능합니다.

 

다만, 정의되지 않은 인덱스[ex | array[5]]에 접근하더라도 에러 메시지를 반환하지 않아 주의가 필요합니다.

 

배열의 크기와 길이는 다음과 같이 구할 수 있습니다.

int arraySize = sizeof(array); #배열의 크기
int arrayLength = sizeof(array) / sizeof(array[0]) #배열의 길이

 

배열의 각 연산에 대한 시간 복잡도는 다음과 같습니다.

요소 접근[Access] | O(1)
요소 수정[Edit] | O(1)
요소 삭제[Delete] | O(N)