DS08 - 선형리스트의 구현

선형리스트의 구현 방식                    

 선형 리스트는 배열을 사용해 순차 자료구조 방식을 구현한다. 배열은  <인덱스, 원소>  쌍으로 구성되어 메모리에 연속적으로 할당 되는데, 이때 인덱스는 배열 원소의 순서를 나타낸다. 배열은 순서를 가진 배열 원소들을 메모리에 연속하여 순차적으로 구성하므로, 프로그래밍 언어에서 제공하는 배열을 사용하면 순차 자료구조 방식의 선형 리스트를 쉽게 구현할 수 있다.

1차원 배열을 이용한 구현        

  수학에서 1차원은 선으로 이루어진 차원 공간을 의미한다. 1차원 배열또한 선형의 형태를 띄고 있다. 모든 원소는 하나의 직선 위에 존재하기 때문에 하나의 인덱스 값을 이용하여 모든 원소에 접근할 수 있다.

다음은 4개의 정수를 저장하는 배열과 이를 저장한 메모리를 나타낸 것이다.

int array = {216, 209, 251, 312};

array	216	371	121	782
memory	0xab3826	0xab3830	0xab3834	0xab3838

int arr[4] = {216, 209, 251, 312};

int형 배열 arr는 int형의 원소를가진다. int type은 4 byte의 크기를 가지므로, 배열의 인덱스가 1 증가할 때 마다 메모리 주소는 4 byte씩 증가하게 된다.

배열에서 첫번째 원소의 인덱스는 0 이고, 두번째 원소의 인덱스는 1, n 번째 원소의 인덱스는 (n-1)이다. 따라서 원소의 크기가 s이고 첫번째 원소의 메모리 주소가 a일때 n번째 원소의 메모리 주소는 a + (n-1) * s가 된다.

  다음 코드는 위의 배열을 실제로 C 코드로 구현한 뒤 배열의 각 요소들과 그 메모리 주소를 출력하는 코드이다.

#include <iostream>

using namespace std;

int main()
{
	int arr[4] = { 216, 209, 251, 312 };

	for (int i = 0; i < 4; i++)
	{
		cout << "value : " << arr[i] << " address : " << &arr[i] << endl;
    }
}

필자의 컴퓨터에서 이 코드의 실행 결과는 다음과 같다.

value : 216 address : 003AFE10

value : 209 address : 003AFE14

value : 251 address : 003AFE18

value : 312 address : 003AFE1C

실행 결과도 이론과 같이 메모리가 4 byte씩 증가하는 것을 볼 수 있다.

2차원 배열을 이용한 구현                  

 수학에서 2차원은 면으로 이루어진 차원 공간을 의미한다. 2차원 배열또한 면의 형태를 띄고 있다. 모든 원소는 하나의 평면위에 존재하기 때문에, 행을 나타내는 인덱스 값과 열을 나타내는 인덱스 값을 이용하여 모든 원소에 접근할 수 있다.

다음은 3행 5열로 이루어진 15개의 원소를 가지는 2차원 배열과 배열이 저장된 메모리를 나타낸 그림이다.

int arr[3][5] = {{96,84,83,82,77}, {65, 59, 72, 81, 90},{37, 77, 65, 42, 75}};

0	1	2	3	4	5
1	96	84	83	82	77
2	65	59	72	81	90
3	37	77	65	42	75

0xab3840	0xab3844	0xab3848	0xab384c	0xab3850
0xab3854	0xab3858	0xab385c	0xab3860	0xab3864
0xab3868	0xab386c	0xab3870	0xab3874	0xab3878

  int형 2차원 배열 arr는 int형의 원소를가진다. int type은 4 byte의 크기를 가지므로, 배열의 인덱스가 1 증가할 때 마다 메모리 주소는 4 byte씩 증가하게 된다. 

여기서 주목할 점은 C 언어는 2차원 배열을 메모리에 저장할 때 1차원배열 처럼 저장한다는 점이다. 즉 첫째행의 마지막 요소가 저장된 메모리의 다음 공간에는 둘째행의 첫번째 요소가 저장되어 있다는 말이다.

즉 2차원 배열은 1차원 배열의 배열이라고 볼 수 있다. 따라서 2차원 배열은 메모리에 1차원배열과 같이 선형으로 저장되게 된다.

  다음 코드는 위의 배열을 실제로 C 코드로 구현한 뒤 배열의 각 요소들과 그 메모리 주소를 출력하는 코드이다.

#include <iostream>

using namespace std;

int main()
{
	int arr[3][5] = { { 96,84,83,82,77 },{ 65, 59, 72, 81, 90 },{ 37, 77, 65, 42, 75 } };

	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 5; j++)
		{
			cout << "value " << i << ", " << j << " : " << arr[i][j] << " address : " << &arr[i][j] << endl;
		}
	}
}

필자의 컴퓨터에서 이 코드의 실행 결과는 다음과 같다.

value 0, 0 : 96 address : 001CFDC8

value 0, 1 : 84 address : 001CFDCC

value 0, 2 : 83 address : 001CFDD0

value 0, 3 : 82 address : 001CFDD4

value 0, 4 : 77 address : 001CFDD8

value 1, 0 : 65 address : 001CFDDC

value 1, 1 : 59 address : 001CFDE0

value 1, 2 : 72 address : 001CFDE4

value 1, 3 : 81 address : 001CFDE8

value 1, 4 : 90 address : 001CFDEC

value 2, 0 : 37 address : 001CFDF0

value 2, 1 : 77 address : 001CFDF4

value 2, 2 : 65 address : 001CFDF8

value 2, 3 : 42 address : 001CFDFC

value 2, 4 : 75 address : 001CFE00

 0번 행의 마지막 원소인 77의 메모리 주소는 001CFDD8이다. 1번 행의 첫번째 원소인 65는 001CFDDC의 메모리 주소를 가지는 것을 확인 할 수 있다.

다차원 배열을 이용한 구현                 

 2차원 배열이 1차원 배열의 배열임을 우리는 확인 할 수 있었다. 그렇다면 3차원 배열과 그 이상의 고차원 배열들은 어떠할까?

  3차원 이상의 고차원 배열들 또한 마찬가지로 자신의 차원보다 한단계 낮은 차원의 배열의 배열로 이루어져 있다.

즉 3차원 배열은 2차원 배열의 배열이고 4차원 배열은 3차원을, n차원 배열은 n-1 차원을 배열의 요소로 가진다는 말이다. 결론적으로 모든 고차원 배열은 쪼개어 보면 1차원 배열의 배열로 이루어져 있다.

따라서 모든 n차원 배열은 차원에 상관없이 메모리상에 1차원 배열과 같이 선형으로 저장된다.

논리적으로는 3차원 이상의 배열을 상상하고 설명할 수 없지만, 배열의 성질을 이용한다면 3차원 이상의 고차원 배열을 이용한 선형 리스트를 손쉽게 구현할 수 있다.