[자료구조] 배열(array)

자료구조 - 배열

자료구조론의 가장 기초적이고 가장 간단한 형태인 배열이다.

배열은 같은 크기, 같은 형태의 데이터를 나열해놓은 데이터를 말한다.

좌표, 행렬 등에 활용되며,

1차원 배열, 2차원 배열, 희소행렬 등 다양한 형태로 응용가능하다.

데이터형태 및 활용예

배열은 메모리의 연속된 공간에 데이터를 저장한다.

인덱스를 통해 데이터 위치를 확인하고 접근(액세스)한다.

//C사용 예

int sample[5] = { 11, 22, 33, 44, 55 };  // int형의 크기가 5인 배열을 선언하고 값을 초기화 한다. 인덱스는 0~4까지 사용가능

printf("%d\n", sample[0]);  //인덱스 0번 값을 출력(배열의 첫번째 값) -> 출력값 : 1
printf("%d\n", sample[3]);  //인덱스 3번 값을 출력(배열의 네번째 값) -> 출력값 : 4

32비트 환경에서(int의 크기가 4바이트(32비트)) 메모리 상에 아래 그림과 같이 적재되게 된다.

인덱스를 이용하여 액세스하기 위해 연속된 공간에 저장된다.

(주소값은 설명을 돕기 위해 간략화한 값을 사용하였음)

자료 액세스 시 주소를 얻는 방식 : 

배열의 시작주소 + 자료형의크기×인덱스값의 주소를 액세스

ex)

sample[3]의 값을 액세스 하는 경우

배열의시작주소(1000) + int의크기(4) × 인덱스값(3) = 1012

1012의 주소에 있는 값 액세스 : 44

장단점

장점

 1. 인덱스를 통해 모든 데이터에 직접 액세스하기 때문에 액세스 속도가 빠르다.

리스트나 그래프와 같은 자료구조 형태와 달리 탐색없이 인덱스를 통해 직접 액세스 하기 때문에

액세스 속도가 빠르다.

리스트의 경우 10,000번째 값을 액세스 하기 위해서는 첫번째 값부터 10,000번 탐색해야 하지만

배열의 경우 해당 인덱스 위치의 주소값을 얻는 단 한번의 연산만으로 액세스가 가능하다.

자료구조의 크기가 크면 클수록 이 차이는 더욱 커짐

 2. 포인터 등 부가적인 정보가 없어 기록 밀도가 1이다.

리스트, 그래프 등은 데이터 외에 포인터 등 부가정보를 가지기 때문에 기록밀도가 1이 되지 않지만,

배열은 부가정보 없이 데이터만 저장하기 때문에 기록밀도가 1이다.

리스트나 그래프는 메모리에 분산시켜 데이터를 저장하고 포인터로 연결시킨 형태라 데이터외 부가 정보를 가지게 된다.

반대로 배열은 메모리의 연속된 공간에 데이터를 저장하고 인덱스를 이용한 연산을 통해 액세스 하기 때문에 부가정보가 필요 없다.

 3. 가장 간단하며 사용하기 쉽다.

단점

 1. 삽입, 삭제가 어렵다(삽입, 삭제가 어렵기 때문에 삽입삭제가 없는 경우에만 사용한다.)

데이터가 연속되게 저장되어 있어야 하므로 중간에 데이터를 삽입하거나 삭제할 경우

뒤의 데이터를 모두 한칸씩 당겨와야 하기 때문에 부하가 많이 걸린다.

(만약 삭제하지 않고 그냥 둔다면 인덱스를 이용한 주소값 계산을 할 수 없기 때문에 자료를 연속된 공간에 두기 위해 이동이 필요함)

예를들어 위의 예제에서 sample[2]를 삭제하면 그 뒤의 값들을 한칸씩 당겨와야한다.

▽▼▽

삭제 연산 후 sample배열은 크기가4인 배열이 된다.

이 예에서는 크기가 5라 연산이 많지 않았지만 크기가 커질수록 이동이 많아져 부하가 커진다.

크기가 10,000인 배열에서 정중앙의 값을 삭제하면 5,000번의 값 이동이 필요함.

(참고) 삽입, 삭제시 평균 자료 이동 횟수

 2. 메모리에 종속적이다

위의 예에서 계속해서 봤듯이 배열은 연속된 메모리 공간에 값을 저장하기 때문에

배열을 선언하기 위해서는 그 크기 만큼의 연속된 메모리 공간이 필요하다.

이를 메모리에 종속적이다 라고 한다.

이와 반대로 리스트, 그래프 등은 포인터를 이용하여 분산된 메모리 공간에도 저장이 가능하다.

(기타 참고) 2차원 배열에서 행우선, 열우선 문제

배열은 좌표 등을 표시하기 위해 2차원 배열을 사용하기도 하는데

개발 언어마다 다음 값 연산시 행이 먼저 증가하는 경우도 있고, 열이 우선 증가하는 경우도 있다.

2차원 배열 sampleTwo[3][5]가 있다고 할 때

sampleTwo++;가 행이 증가하는지, 열이 증가하는지 차이를 말함.

사실 위와같은 연산을 사용하지 않는 경우라면 거의 상관이 없지만,

정보처리기사나 자격증 시험에서는 가끔 나오는 내용이니 참고하길 바람.

행우선 2차원 배열인 언어 : COBOL, C, PASCAL, PL/1

(1,1) (1,2) (1,3) => 열이 먼저 증가함

열우선 2차원 배열인 언어 : FORTRAN

(1,1) (2,1) (3,1) => 행이 먼저 증가함