선형데이터구조, 배열(Array) #1 배열의 소개

요약 및 정리

1. 배열(Array)이란 무엇인가?
   • 배열은 메모리 위에서 연속적으로 위치하고 같은 데이터 타입의 모음
2. 배열의 특징
   • 배열안의 각각의 요소가 데이터 타입이 동일함
   • 배열의 0번째 위치는 배열을 가리키는 주소값
   • 배열은 고정된 크기를 가짐
   • 랜덤 엑세스(Random Access) 허용
3. 배열의 장점
   • 랜덤 엑세스로 인한 빠른 탐색 속도
4. 배열의 단점
   • 삽입과 삭제 연산에 많은 비용이 소모됨

 

1. 배열(Array)의 소개

배열은 메모리 위에서 연속적으로 위치하고 같은 데이터 타입의 모음입니다. 이는 배열을 가리키는 주소값에 추가적인 값을 더하여 각 요소의 위치를 계산하기 쉽게 합니다. 즉, 배열을 가리키는 주소값이란 배열의 첫번째 요소의 메모리 위치입니다. 첫번째 요소의 인덱스는 0번째이고 두 인덱스간의 차이는 오프셋입니다.

위의 그림을 보면 배열의 메모리 위치는 200부터 시작하는 것을 볼 수 있습니다. 그리고 0번째 요소에는 알파벳 'U'가 저장되어 있습니다. 

 

1.1 배열의 크기(Array's size)

C언어의 경우에는 배열은 크기가 지정되면 고정된 크기를 의미합니다. 이것은 배열의 크기를 줄일수도 또는 확대할수도 없는 것을 의미합니다. 배열의 크기를 변경할 수 없는 이유는 크기를 변경할 경우 확장하거나 축소한 메모리의 위치가 비어있는지 매번 확인할 수 없기 때문이다. 그래서 메모리가 정적으로 할당될 때 배열은 축소되지 않고 컴파일러만이 해당 배열을 해제할 수 있습니다.

 

1.2 배열의 인덱싱 타입(Indexing Type)

• 0 (zero-based indexing) : 배열의 첫번째 요소는 0번째 부터 시작
• 1 (one-based indexing) : 배열의 첫번째 요소는 1번째 부터 시작
• n (n-based indexing) : 배열의 베이스 인덱스를 자유롭게 선택, 일반적으로 n-based indexing을 허용하는 프로그래밍 언어는 음의 인덱스 값을 허용하며 열거형이나 문자와 같은 다른 스칼라(크기만 있고 방향은 없는 수) 데이터 형식을 배열 인데스로 사용할 수 있다.

 

#include <stdio.h>

int main()
{

    // 크기 10을 가지는 정수형 타입 배열 생성
    int arr[10];
    // 0번째 배열 요소에 상수값 5 저장
    arr[0] = 5;
	
    // 0번째 배열 요소에 저장되어 있는 5를 참조하고 출력
    printf("%d", arr[0]);

    return 0;
}

Output

5

 

1.3 배열(Array)의 장점

• 배열은 요소에 대한 랜덤 엑세스(Random Access)를 허용합니다. 따라서 인덱스를 사용하여 요소에 더 빨리 접근할 수 있습니다.
• 배열의 캐시 인접성(Cache Locality)이 향상되어 성능에 큰 차이가 있습니다.
• 배열은 하나의 이름을 사용하여 같은 타입을 가지는 여러개의 데이터 요소들을 표현이 가능합니다.

랜덤 엑세스(Random Access)란 무엇인가?

배열 안에 각각의 요소들은 메모리 위에서 연속적인 위치에 존재하기 때문에 배열의 주소와 인덱스 값을 이용하여 임의로 배열 안의 아무 요소에나 접근이 가능하다. 추후에 소개될 연결 리스트같은 경우 어떤 값을 찾기 위해서는 첫번째 노드부터 차례차례 탐색을 수행하여 접근해야 하지만 배열 같은 경우 배열의 주소만 알고 있다면 한번에 원하는 위치를 가리켜 값에 접근할 수 있습니다.

 

캐시 인접성(Cache Locality)란 무엇인가?

캐시 인접성이란 자주 사용하는 데이터에 다시 접근하는 경향을 의미한다. 대표적으로 시간 지역성과 공간 지역성이 존재합니다. 시간 지역성은 최근 접근한 데이터에 다시 접근하는 경향을 의미합니다. 공간 지역성은 최근 접근한 데이터의 주변 공간에 다시 접근하는 경향을 의미합니다.

 

1.4 배열(Array)의 단점

• 배열의 크기를 변경하지 못합니다. 왜냐하면 배열의 선언은 정적 메모리 할당이기 때문입니다.
• 배열의 삽입과 삭제에 비용이 많이 소모됩니다. 이유는 배열의 중간에 요소를 삽입을 하거나 삭제를 하게 되면 배열의 순차적 특징을 맞추어야 하기 때문에 배열 요소들의 이동(Shift)가 요구되기 때문입니다.

1.5 배열의 예제

// C/C++/Java에서의 문자형 배열
char arr1[] = {'g', 'e', 'e', 'k', 's'};

// C/C++/Java에서의 정수형 배열
int arr2[] = {10, 20, 30, 40, 50};

// 배열에서 i번째 요소에 arr[i]와 같이 접근이 가능합니다.
// 예를 들어 arr1[0]은 'g'이고 arr2[3]은 40입니다.

1.6 배열의 응용

• 배열은 같은 데이터 타입의 데이터 요소들을 저장하는데 사용됩니다.
• 배열은 CPU 스케줄링에 사용됩니다.
• 배열은 다른 데이터구조인 스택(Stack), 큐(Queue), 힙(Heaps), 해쉬 테이블(Hash Table) 등의 구현에 사용됩니다.

References

source code : https://github.com/yonghwankim-dev/DataStruct
https://www.geeksforgeeks.org/introduction-to-arrays/