[자료구조] 자유공간리스트 - 개념, 구현

메모리 획득과 반납방법

1️⃣ 프로그램 수행 중 즉석에서 필요한 메모리를 OS에서 malloc() 하는 방식

2️⃣ 미리 malloc()하여 자유공간리스트를 만든 후, 할당 및 회수하는 방식

👨‍💼 자유공간리스트 (free space list)

개념

• 필요에 따라 요구한 노드를 할당할 수 있는 자유 메모리풀
• 자유 공간 관리를 위해 연결리스트 구조를 이용하기 위해서는 초기에 사용할 수 있는 메모리를 연결 리스트로 만들어 놓아야함
• 노드 할당 요청 받을 시, 자유 공간 리스트 앞에서부터 공백노드 할당

추가 구현 함수

• getNode()

  • Free 포인터가 가리키는 빈 노드 하나를 newNode에게 주는 함수

    getNode(){
    	if (Free == NULL) underflow(); // 더이상 할당해 줄 빈 노드 부족
    	newNode <- Free;               // Free가 가리키고 있는 1개의 빈노드 
    	Free <- Free.link;             // Free는 한칸 전진
    	return newNode;
    }

• returnNode(p)
  • 포인터변수 p가 지시하는 노드를 자유 공간 리스트에 반환하는 함수
  • 앞에서부터 공백 반납

    returnNode(p){
    	p.link <- Free;
    	Free <- p
    }