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

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

화나는 책

가용공간 리스트

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

의미

사전적 의미: 컴퓨터 운영 체제가 주기억 장치의 사용되지 않은 영역, 또는 블록을 라이브러리 형태로 구성한 목록

직관적인 의미: 이제 사용하지 않는 노드를 체인 형태의 리스트로 만들기

등장 동기

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

코드 해설

주석달았음

공부끝

해당 사항 구현했는지 채점하러 감.

from http://guti-coding.tistory.com/64 by ccl(A) rewrite - 2021-10-15 08:27:08