비사용 기억공간

최종 수정 : 24.12.27

비사용 기억공간

1. 순차 가용공간에서 노드 획득

리스트에서 노드의 생성을 위해 노드가 사용할 공간을 할당받아야 하는데, 기억공간을 순차적으로 사용하는 경우에는 이미 사용 중인 공간 이후에 가용공간을 할당받아 사용하게 된다. 그러나 사용 중인 공간 이후로 여유 공간이 없다면 기억공간이 가득 찬 경우로 판단하기 때문에 더 이상 노드의 삽입이 불가능하다.

 

전체적인 기억 공간으로는 아직 여유가 있지만 순차적으로 공간을 할당받아 사용하기 때문에 기억 공간이 남아 있어도 오버플로가 발생하게 된다. 이러한 문제점 때문에 리스트에서 사용되는 기억 공간의 관리 방식으로는 사용하기 전의 기억공간이나 사용이 끝난 기억공간을 관리의 용이성을 위해 노드로 구성하여 연결한 리스트를 자유 공간 리스트 또는 순차 가용 공간이라고 하며, 연결 리스트 구현을 구현하여 기억공간의 효율적인 사용을 위하여 쓰인다.

---

2. 초기 가용 공간에서의 연결 리스트 생성

가용 공간 리스트는 이미 생성된 노드들이 사용되지 않고 반환되는 경우 노드들을 주소로 연결하여 리스트 구조를 유지하는 리스트이다. 즉, 더 이상 사용되지 않는 노드들을 리스트로 구성하여 유지함으로 메모리 할당 함수(malloc : memory allocation)를 이용하여 새롭게 노드를 생성하지 않고 가용 공간 리스트에 있는 노드를 사용하는 것이다. 이로써 효율적인 공간 활용이 가능하게 된다. 이러한 가용 공간 리스트를 사용하기 위해서는 초기에 가용 공간 연결 리스트를 생성해 주어야 한다.

---

3. 연결 리스트 가용 공간에서의 노드 획득

연결 리스트의 가용 공간이 있다면 새로운 노드를 삽입할 때 기억 공간을 할당하지 않고 가용 공간에서 새 노드로 사용할 노드를 획득하여 사용한다.

---

4. 연결 리스트로 된 가용공간에 삭제 노드의 반환

연결 리스트로 만들어진 가용 공간에 삭제 노드의 반환은 다음에 기억 공간의 재활용을 위해서 해제하지 않고 연결 리스트로 된 가용 공간에 반환한다.

---

참고

독학사 교재