[자료구조] 연결 리스트 3 (원형 리스트, 가용 공간 리스트)

원형리스트

원형 리스트(circular list)

- 체인에서 마지막 노드의 link 필드가 첫 번째 노드를 가리킴

- 포인터 current가 마지막 노드를 가리키는지 검사할 때,

   current->link == 0이 아니라 current->link == first로 검사

- 삽입, 삭제 함수에서 마지막 노드의 link 필드가 첫 번째 노드를 가리키는지 연산이 끝난 후 확인

 

원형 리스트 예시

                        ↙  ←  ←  ←  ←  ←  ←  ←  ←  ↖

first  → [data | link] → [data | link] → [data | link]

 

리스트 앞에 새 노드 삽입

- 마지막 노드의 link를 변경해야 하므로 접근 포인터가 마지막 노드를 가리키는 편이 편리

template <class T>
void CircularList<T>::InsertFront(const T &e)
{ // 원형 리스트 *this의 front에 e를 삽입
  // last는 리스트의 마지막 노드를 가리킴
    ChainNode<T> *newNode = new ChainNode<T>(e);
    if (last)
    { // 비어있지 않은 리스트
        newNode->link = last->link;
        last->link = newNode;
    }
    else
    { // 비어있는 리스트
        last = newNode;
        newNode->link = newNode;
    }
}

 

시간복잡도 - O(1)

 

헤더 노드

- 공백 리스트를 특별한 경우로 처리할 필요 없음

 

 

가용 공간 리스트

삭제된 노드의 체인

• 노드 삭제 시간은 체인의 길이에 비례
• 자유 노드의 체인 유지를 통해 소멸자의 시간 O(1)로 감소
• 새 노드가 필요할 때는 자유 노드 체인에서 사용
• 자유 노드 체인이 공백일 때만 new로 새로운 노드 생성

 

노드 획득

template <class T>
ChainNode<T> *CircularList<T>::GetNode()
{ // 사용할 노드 생성
    ChainNode<T> *x;
    if (av)
    {
        x = av;
        av = av->link;
    }
    else
        x = new ChainNode<T>;
    return x;
}

 

노드 반환

template <class T>
void CircularList<T>::RetNode(ChainNode<T> *&x)
{ // x가 가리키는 노드 반환
    x->link = av;
    av = x;
    x = 0;
}

 

원형 리스트의 삭제

template <class KeyT>
void CircularList<T>::~CircularList()
{ // 원형 리스트 삭제
    if (last)
    {
        ChainNode<T> *first = last->link;
        last->link = av; // 마지막 노드가 av에 연결
        av = first;      // 리스트의 첫 번째 노드가 av리스트의 첫 번째 노드가 됨
        last = 0;
    }
}