배열 (Array)

#논리적 저장 순서와 물리적 저장 순서의 일치

일차원 배열은 논리적 저장 순서와 물리적 저장 순서가 일치한다.
실제로 저장하고자 하는 배열의 순서대로 메모리에 연달아서 저장된다.

int형 일차원 배열을 선언하고 각 원소별 주소값을 출력해보았다.

#include <iostream>

using namespace std;

int main(int argc, const char * argv[]) {
    int arr[3];
    arr[0] = 0;
    arr[1] = 1;
    arr[2] = 2;
    
    cout << "arr: " <<  arr << '\n';
    cout << "&arr[0] :" << &arr[0] << '\n';
    cout << "&arr[1] :" << &arr[1] << '\n';
    cout << "&arr[2] :" << &arr[2] << '\n';
    return 0;
}

 

실행 결과는 다음과 같았다.

arr: 0x7ffeefbff590
&arr[0] :0x7ffeefbff590
&arr[1] :0x7ffeefbff594
&arr[2] :0x7ffeefbff598

arr에 저장된 값과 arr[0]의 주소값이 같은 것을 확인할 수 있다.
따라서 배열의 변수명에는 배열의 시작 주소가 저장된다는 것을 알 수 있다.

arr[1]의 주소값은 arr[0]의 주소값에서 4를 더한 값이고,
arr[2]의 주소값은 arr[1]의 주소값에서 4를 더한 값이다.
배열이 int형으로 선언되었는데, C++에서 int형에 4byte를 할당하기 때문이다.

실제로 배열의 원소의 주소는 시작 주소(base address) + 오프셋(offest) 값으로 계산된다.
여기서 시작 주소는 배열의 변수명에 저장된 값이 된다.
배열의 한 원소에 s byte가 할당된다고 할 때, 오프셋은 원소의 인덱스와 s를 곱한 값이 된다.

표 1. 메모리에 저장된 배열

 

#임의 접근(random access)

위에서 말한 논리적 저장 순서와 물리적 저장 순서가 일치하다는 특징 때문에, 찾고자 하는 원소의 index만 알고 있다면 원소에 직접 접근하는 것이 가능하다.
배열은 O(1)의 시간 복잡도에 원소에 random access할 수 있다.
따라서 읽기 속도가 빠르다고 할 수 있다.

#원소의 삽입과 삭제

배열에 원소를 삽입하거나 삭제할 경우, 연속적으로 저장되는 배열의 특성을 유지시키기 위해 배열의 원소들을 shift하는 과정이 필요하다.
삽입하는 경우에는 그 뒤의 원소들을 한 칸씩 밀어줘야 한다.
삭제하는 경우에는 그 뒤의 원소들을 한 칸씩 당겨줘야 한다.
따라서 O(n)의 시간 복잡도에 삽입과 삭제가 이루어진다.