가용공간 리스트
가용공간 리스트에 대한 소개
의미
- 사전적 의미: 컴퓨터 운영 체제가 주기억 장치의 사용되지 않은 영역, 또는 블록을 라이브러리 형태로 구성한 목록
- 직관적인 의미: 이제 사용하지 않는 노드를 체인 형태의 리스트로 만들기
등장 동기
- 체인과 원형 레스트에서 진행되는 삭제는 노드를 하나씩 처리한다. => 따라서 체인 혹은 원형 리스트는 리스트의 길이에 비례하여 시간이 소요된다. => 삭제라는 행위자체가 비효율적이네.
- 내용이 삭제된 노드에 파괴자를 실행하는 대신에, 삭제된 자유노드를 체인으로 유지하여 새로운 노드가 필요하면 이 빈 공간을 할당하게 만들면 좋을 것 같다. (존재자체를 지우던 삭제라는 행위를 아예 생략하는 거지.)
- 만약 가용 공간 리스트가 공백이라면 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등의 함수를 통해 가용 공간 리스트에 값을 반환하고, 가용 공간 리스트의 존재 여부에 따라 노드를 새롭게 할당하지 결정할 수 있다.
채점기준은 다르지만, 공부할 만한 요소같았다.
더보기