[자료구조] 기억장소 할당방법

안녕하세요? White Smile입니다.

오늘은 기억장소 할당방법의 종류에 대해 배워봅시다.

각 자료구조는 자료들의 순서(order) 및 저장방법(allocation)에 따라 다음과 같이 구분되어집니다.

앞서 말씀드렸던 선형구조와 비선형구조처럼 말이죠.

구조는 자료들의 관계, 할당방법은 순서및 저장방법에 따라!

선형구조 및 비선형구조의 리스트들은 모두 이러한 저장방법으로 각기 저장 할 수 있으나, 

각 저장방법의 장단점에 따라 사용범위 및 분야가 정해지고 있습니다.

선형구조 및 비선형구조의 리스트들은 어떤 할당방법이 더 효율적인지에 따라 나누어진다는 이야기입니다.

순서는 인간들이 인식 가능한 논리적 순서(Logical Order)와 

컴퓨터 메모리 주소로의 주소 저장순서인 물리적 순서(Physical Order)의 두가지 순서가 있고, 

저장벙법이란 이 두 종류의 순서간 관계성으로 정의 되어 집니다.

쉽게 말해서 논리적순서와 물리적 순서가 같을때 다를때에 따라 다르게 정의되어진다는 얘기입니다. 

그럼 본격적으로 할당방법에 대해 알아보죠.

순서할당이란?
순차 할당방법이라고도 하며, 자료의 논리적 순서와 물리적 순서가 동일한 경우의 저장방법을 의미합니다.
즉, 논리적순서(Logical Order)=물리적 순서(Physical Order)를 의미합니다.

예를들어 설명하자면, 학생들이 시험을 볼때처럼 번호순으로 앉는 것으로 예를 들수있습니다.

번호순으로 하게되면 단 한가지의 단점은 만약 번호 하나가 비어있다면, 

그 할당영역은 공백으로두고 다음영역부터 데이터를 채워야한다는 겁니다.

이렇게 하게되면 공간낭비가 심해지겠지요.

또 하나의 단점은 그 공백을 채우려고 자리이동을 하게되면, 

그 뒤에 있는 번호도 줄줄이 옮겨야하기때문에 자리이동수도 많아집니다.

자세한 이야기는 다음에 설명하죠.

연결할당이란?
링크할당방법이라고도 하며, 자료의 논리적 순서와 물리적 순서가 동일하지 않은 경우의 저장방법을 의미합니다.
즉, 논리적 순서(Logical Order)≠물리적 순서(Physical Order)를 의미합니다.

이것은 학생들이 번호순과 상관없이 아무렇게나 앉은 것을 말합니다.

그저 자신의 뒤에 누가 앉았는지만 알면되죠.

이렇게 자신의 뒤에 주소를 가리키는것 이것을 포인터라고도합니다.

이 연결할당은  자리옮김이 있을때 한 공간의 포인터만 바꾸어주면 공백이 채워지게됩니다.

이것도 나중에 자세히 설명하죠.

밑의 예는 제가 예를 들었던것을 총정리 한것입니다.

순서할당과 연결할당의 예
학생들의 번호가 논리적 순서라고하고, 

학생들의 강의실 책상의 번호가 물리적 순서라고 할 때, 

순서할당방법은 학생들의 번호순과 강의실 책상에 앉은 번호가 동일한 순서의 규칙에 의해 지정되는 것입니다.
연결할당은 학생들이 책상에 앉을때 특정하지 않은 책상으로 분산하여 앉는 경우를 뜻한다고 볼수 있습니다. 

이때 학생들의 번호는 학생들 개인이 자신의 다음 학생이 어느 책상 번호에 앉아 있는지를 알려주는 

링크(포인터)의 기능을 갖고 있어야 학생들의 번호 순서가 인식될수 있는 할당방법입니다.

2016/05/03 - [자료구조] - [자료구조] 자료구조의 구분

2016/05/01 - [자료구조] - [자료구조] 자료구조 관계용어

2016/05/01 - [자료구조] - [자료구조]자료구조(Data Structure) 정의