[Data Structure] 가용 공간 리스트

가용 공간 리스트 (Available-Space List)

기존 단순 연결 리스트와 원형 리스트에서의 노드를 생성하고 삭제하는데 시간이 소요된다. 만약 삭제된 노드를 다른 장소에 유지한다면 노드를 새로 생성하고 삭제하는 시간을 O(1)로 줄일 수 있다.

 

이를 구현하기 위해선 삭제된 노드를 연결해놓을 리스트가 필요한데, 이를 가용 공간 리스트라 한다.

Node<T>* av = nullptr; // available-space list

노드 생성과 삭제

가용 공간 리스트가 있다면, 노드의 생성과 삭제에 new와 delete를 사용하지 않고 가용 공간 리스트에서 노드를 가져오는 함수를 사용하면 된다.

// 가용 공간 리스트(av)에서 사용할 노드 가져옴
// new 키워드로 노드 객체 생성하는 것 대신 사용
Node<T>* GetNode(T data)
{
    Node<T>* newNode;

    if (av)
    {
        newNode = av; // 사용하지 않는 노드를 가리키는 av를 새로운 노드로 사용
        av = av->next; // av는 다음 사용하지 않는 노드로 이동
        newNode->data = data;
    }
    else
    {
        newNode = new Node<T>(data); // 가용 공간 리스트에 남은 노드가 없을 때만 new 사용
    }

    return newNode;
}

// 사용한 노드 반환
// delete 키워드로 노드 객체 삭제하는 것 대신 사용
void ReturnNode(Node<T>* node)
{
    node->next = av;
    av = node;
    node = nullptr;
}

// 사용 예시

Node<int>* node1 = list.GetNode(1);
Node<int>* node2 = list.GetNode(2);
list.InsertFront(node1);
list.InsertRear(node2);
...