[자료구조] 순차 자료구조 - 선형 리스트의 구현

선형 리스트를 순차구조로 구현하기 위해서 배열을 사용한다. 배열은 <인덱스,
원소 > 의 쌍으로 구성되어 메모리에 연속적으로 할당되는데, 이때 인덱스는

배열 원소의 순서를 타나낸다. 배열은 순서를 가진 배열 원소들을 메모리에 연

속하여 구성하므로 프로그램 언어에서 제공하는 배열을 그대로 사용하여 구현

할 수가 있다.

그럼 가장 간단한 1차원 배열의 순차 표현을 알아보자.

1차원 배열은 인덱스를 하나만 사용하는 배열이다. 원소의 순서를 하나의 값으

로 구별할 수 있는 간단한 선형 리스트는 1차원 배열을 사용하여 표현할 수 있

다.

예를 들어 학교의 학생수에 대해서 생각해보자.

1학년에 4반이 있는데, 각 반에는 35명, 36명, 39명, 37명 이렇게 있다고 치자.

이 것을 배열을 통해 나타내면,

int student[4] =  { 35, 36, 39, 37 } ;

이렇게 표현할 수 있다.

1차원 배열 student는 int로 선언 되었으므로, 각 원소의 길이는 4바이트가 된

다. C 프로그래밍에서 배열의 인덱스는 0부터 시작하므로 배열 sale의 각 원소

의 위치는 시작 주소가 a일 때 a + ( 인덱스 * 4바이트 ) 가 된다.

이번엔 2차원 배열의 순차 표현을 알아보자. 

위의 1차원 배열과 마찬가지로 2차원배열은 학교의 학생수 분류에서 학년을 추

가해 보자.

1학년에 4반, 2학년에 4반, 3학년에 4반이 있다.

그렇게 되면, 

int student[3][4] = { { 35, 36, 39, 37 }, 
                             { 37, 36, 38, 39 }, 

                             { 34, 37 ,38 ,37 } } ;
이렇게 표현 할 수 있다.

2차원 배열의 구조를 논리적으로 표현할 때는 행과 열의 구조로 나타내지만, 실

제로 메모리에 저장될 때에는 1차원의 순서로 저장된다. 2차원의 논리적 순서

가 1차원의 물리적 순서로 변환되는 방법은 첫 번째 인덱스를 기준으로 하는 행
우선 순서와 마지막 인덱스를 기준으로 하는 열 우선 순서 방법이 있다.

간단히 말해서 행 우선 방법은 student[0][0] -> student[0][1]->student[0]

[2] 이런식으로 우선 0 의 0~3까지 그다음은 1의 0~3까지. 이런식으로 앞의 행

의 값을 쭉 넣고, 다음 행의 값을 넣는 방식이다.

그리고 열 우선 방법은 student[0][0] ->student[1][0]->student[2][0] 이렇

게 먼저 앞의 0의 0 값, 1의 0값, 2의 0값을 넣고 다음에 0의 1값, 1의 1값, 2의 1

값 이렇게 차례대로 넣는 방식이다. 

행 우선 방법과 열 우선 순서 방법에 따라 물리적 저장 순서가 다르기 때문에

배열의 원소 위치를 계산하는 방법도 달라져야 한다. 행의 갯수가 n1 이고, 열

의 갯수가 n2인 2차원 배열 A[n1][n2]의 시작 주소가 a고, 원소의 길이가 L 일

때, i행 j 열의 원소, 즉 A[i][j]의 위치는 행 우선 구조에서는 a + ( i * n2 + j ) *
L 이 되고, 열 우선 순서 구조에서는 a + (j * n1 + i) * L 이 된다.

논리 순서를 물리 순서로 변환하는 방법은 프로그래밍 언어의 컴파일러에 의해

서 결정되는데, C 컴파일러는 행 우성 순서 방법을 사용한다.

3차 배열도 이와 유사한 방법을 사용한다. 단지 배열의 크기가 지금은 행과 열

이였다면, 거기에 면이 하나 추가되는 개념이며, 논리적 구조를 물리적 구조로

바꾸는 공식은 조금만 생각하면 유추할 수 있으므로, 자세한 설명은 생략한다.