[자료구조] 배열 (Array)

배열의 개념

배열(array)은 같은 타입의 변수들을 모아서 관리하기 위해 사용하는 유한 집합으로 정의할 수 있다.
변수가 하나의 데이터를 저장하기 위한 것이라면 배열은 여러 개의 데이터를 저장하기 위한 것이라고 할 수 있다.

배열을 구성하는 각각의 값을 요소(element)라고 하고, 배열에서의 위치를 가리키는 숫자는 인덱스(index)라고 한다. (배열의 index는 0부터 시작한다.)

배열의 특징은 다음과 같다.

• 연속적인 메모리 공간에 순차적으로 데이터를 저장한다.
• 배열은 선언할 때 크기를 정하면, 그 크기로 고정이 된다.
• 선언된 값은 다시 배열을 선언하지 않으면 변경할 수 없다.
• 배열은 같은 타입의 데이터를 여러개 나열한 선형 자료구조이다.
  (주로 동일한 데이터 유형을 가지지만 이질형 데이터도 지원 가능한 프로그래밍 언어도 있다. 이질형 데이터들이 모인 집합체는 주로 레코드라고 함.)
• 데이터에 대한 인덱스의 값이 고정되어 삭제된 element 공간이 그대로 남아있게 되는데 이는 컴퓨터 메모리의 낭비로 이어진다.

배열은 인덱스가 존재하기 때문에 indexing 및 slicing이 가능하다.

• indexing : index를 사용해 특정 요소를 리스트로 부터 읽어들이는 것
• slicing : 요소에 특정 부분을 따로 분리해 조작하는 것

시간복잡도

인덱스를 알고 있다면, 인덱스에 접근하는 시간복잡도는 $O(1)$이다.
데이터를 배열에 삽입을 하려면 기존에 있는 데이터를 한 칸 shift 한 후 데이터를 넣어야 하기에 시간복잡도는 $O(n)$이 걸린다.
마찬가지로 배열에서 데이터를 삭제하는 작업 또한 삭제한 뒤, 나머지 데이터들을 한 칸 shift 해줘야 해서 삽입과 마찬가지로 시간복잡도가 $O(n)$이 걸리게 된다.

배열의 장단점

장점

• 구현이 쉽다.
• 참조를 위한 추가적인 메모리가 필요하지 않는다.
• 연속적이므로 메모리 관리가 편하다.
• 인덱스를 통해 접근하므로 검색이 빠르다.

단점

• 배열의 크기를 변경할 수 없다.
  크기를 변경하려면 새로운 배열을 만든 후, 기존의 데이터를 옮겨야 한다.
• 메모리 낭비가 발생하게 된다.
  배열을 선언한다 하더라도 사용하지 않는 공간은 배열을 선언할 때 공간이 할당되어 있어서 낭비가 된다.

배열을 사용하는 경우

• 순차적인 데이터를 저장하며 값보다는 순서가 중요할 때
• 다차원 데이터를 다룰 때
• 어떤 특정 요소를 빠르게 읽어야 할 때
• 데이터 사이즈가 자주 바뀌지 않으며 요소가 자주 추가되거나 삭제되지 않을 때

구현

java

int arr[] = new int[10];

for(int i = 0; i < 10; i++) {
	arr[i] = i+1;
}

for(int i = 0; i < 10; i++) {
	System.out.print(arr[i]);
}

C

#include <stdio.h>

int main()
{
    int numArr[10] = { 11, 22, 33, 44, 55, 66, 77, 88, 99, 110 }; 

    printf("%d\n", numArr[0]);
    printf("%d\n", numArr[5]); 
    printf("%d\n", numArr[9]); 
    return 0;
}

C++

#include <iostream>
using namespace std;

int main(){
    int arr[5];

    for(int i = 0; i < sizeof(arr)/sizeof(int); i++){
        arr[i] = i+1;
        cout << arr[i] << "\n";
    }
}