[데이터구조] 가용공간리스트

화나는 책

가용공간 리스트

가용공간 리스트에 대한 소개

의미

• 사전적 의미: 컴퓨터 운영 체제가 주기억 장치의 사용되지 않은 영역, 또는 블록을 라이브러리 형태로 구성한 목록
• 직관적인 의미: 이제 사용하지 않는 노드를 체인 형태의 리스트로 만들기

 

등장 동기

1. 체인과 원형 레스트에서 진행되는 삭제는 노드를 하나씩 처리한다. => 따라서 체인 혹은 원형 리스트는 리스트의 길이에 비례하여 시간이 소요된다. => 삭제라는 행위자체가 비효율적이네.
2. 내용이 삭제된 노드에 파괴자를 실행하는 대신에, 삭제된 자유노드를 체인으로 유지하여 새로운 노드가 필요하면 이 빈 공간을 할당하게 만들면 좋을 것 같다. (존재자체를 지우던 삭제라는 행위를 아예 생략하는 거지.)
3. 만약 가용 공간 리스트가 공백이라면 new를 통한 새로운 노드를 생성하자.

 

가용공간 리스트 구현하기

구현사항

• 새로운 노드 필요시 리스트를 조사하여 다시 사용하게 만들자
• 리스트가 다 소모되어 없을 때만 malloc()을 사용함
• getNode(), retNode()를 구현해야 함.
• getNode()는 malloc()를 대신하는 역할이다
• retNode()는 free()를 대신하는 역할이다

(1) node(리스트)를 반환하는 getNode() 구현하기

listPointer* getNode(){ 
	listPointer *node;
    if (isAvailNode) {{ // isAvailNode => 가용노드가 있는지 판단하는 bool값
    	node = avail; // 'node의 주소값'에 '가용노드의 주소값' 대입
        avail = avail -> link; // 'avail'에 '다음 노드의 주소값' 대입
    else
    	node = (listPointer*) malloc(sizeof(listNode)); //새로운 메모리 할당
    return node;
}

사전 설명

• listPointer: 연결 리스트
• avail: 가용노드
• isAvailNode: 가용노드가 있는지 판단하는 bool값

코드 해설

주석달았음

 

 

(2) node를 지우는 retNode() 구현하기

void retNode(listPointer *ptr){
	ptr -> link = avail; // '현재 이전 노드'에 '지우고자 하는 노드(가용노드가 될 아이)'를 대입
	avail = ptr; // avail이 '이전 노드'를 가리키게 함으로써, avail이 가용노드가 되었음.
}

코드 해설

주석달았음

 

 

 

공부끝

위의 함수들은 임의로 기본형태만 나타낸 것이고,

노드 삭제시에 원형 리스트를 free등의 함수를 통해 가용 공간 리스트에 값을 반환하고, 가용 공간 리스트의 존재 여부에 따라 노드를 새롭게 할당하지 결정할 수 있다.

 

채점기준은 다르지만, 공부할 만한 요소같았다.

 

참고자료

bigeyec 네이버 블로그

자료구조와 C++ 프로그래밍 연결 리스트

파이리썬의 파이썬 티스토리 블로그

#26 [C 자료구조] 단순하지 않은: 단순 연결 리스트