[ 자료구조 ] 연결 리스트 : 원형 연결 리스트

연결 리스트의 마지막! 원형 연결 리스트에 대해 알아보자. 구조, 구현할 기능, 구현 순서로 진행된다. 

원형 연결 리스트

1. 구조

원형 연결 리스트는 단일 연결 리스트와 거의 똑같다. 단일 연결 리스트에서 tail의 포인터를 head 향하도록 하면 원형 연결 리스트가 된다. 시작과 끝을 가지고 있기 때문에 기준점 역할을 하는 노드가 필요한데, 이런 역할을 하는 노드를 'cursor'라고 부른다. back은 cursor의 원소, front는 cursor->next의 원소다.

2. 클래스 정의

노드 클래스 (CNode)

class CNode{
private:
    string elem; // 노드 원소값
    CNode* next; // 다음 노드
    friend class CircleList;
};

 

연결 리스트 클래스 (CircleList)

class CircleList{
public:
    CircleList(); // 생성자
    ~CircleList(); // 소멸자
    bool empty() const; // 비었는지?
    const string& front() const; // 커서 다음의 원소
    const string& back() const; // 커서의 원소
    void advance(); // 커서를 다음으로 이동
    void add(const string& e); // 커서 뒤에 노드 추가
    void remove(); // 커서 다음 노드 삭제
private:
    CNode* cursor; // 커서
};

3. 구현

// 생성자
CircleList::CircleList() : cursor(NULL){}

// 소멸자
CircleList::~CircleList()
    { while(!empty()) remove(); }

// 비었는지?
bool CircleList::empty() const
    { return cursor == NULL; }

// 커서의 원소
const string& CircleList::back() const
    { return cursor->elem; }

// 커서 다음의 원소
const string& CircleList::front() const
    { return cursor->next->elem; }

// 커서를 다음으로 이동
void CircleList::advance()
    { cursor = cursor->next; }

 

- 생성자는 커서를 NULL로 세팅한다.

- 소멸자는 리스트가 비워질 때까지 노드들을 반복적으로 제거한다.

- 리스트가 비었는지는 cursor가 NULL인지만 확인하면 된다.

- 커서의 원소는 cursor->elem을 반환하면 된다.

- 커서 다음의 원소는 cursor->next->elem을 반환하면 된다.

- 커서의 이동은 커서가 다음 노드로 이동하는 것을 뜻한다. 

 

데이터 삭제 및 삽입은 그 대상이 front 노드다. 즉, 데이터 삭제는 front 노드가 삭제되는 것이고 데이터 삽입은 front에 노드가 추가된다는 뜻이다. 이를 유념하고 각각 그림으로 자세히 살펴보자. 

 

1) 데이터 삽입

 

데이터 삽입은 리스트가 비었을 때와 비지 않았을 때로 분류된다. 

리스트가 비었을 경우 (cursor == NULL)

먼저 리스트가 비었을 경우는 위와 같다. 새로운 노드를 V라고 했을때 V 자체로 순환형 구조를 이룬다. 이를 그대로 코드로 구현하면 아래와 같다. 

CNode* v = new CNode; // 노드 생성
v->elem = e; // 노드값 설정
v->next = v; // 자기 자신이 순환 구조를 이룸
cursor = v; // 커서는 v를 가리킴

 

리스트가 비지 않았을 경우 (cursor != NULL)

위 그림은 리스트에 값이 하나라도 있는 경우다. 먼저 새로운 노드 V를 커서 뒤에 연결시킨 뒤에 커서가 V를 가리키도록 하면 된다. 이를 그대로 코드로 구현하면 아래와 같다. 

CNode* v = new CNode; // 노드 생성
v->elem = e; // 노드값 설정
v->next = cursor->next; // v를 커서 뒤에 연결
cursor->next = v; // 커서가 v를 가리키도록 한다

 

데이터 삽입은 리스트가 비었을 때와 그렇지 않을 때만 분류하면 되기 때문에 아래와 같은 함수로 일반화 할 수 있다. add(e)는 e라는 값을 가지는 노드를 원형 리스트에 추가한다는 뜻이다. 

void CircleList::add(const string& e){
    CNode* v = new CNode; // 새 노드 생성
    v->elem = e;
    if(cursor == NULL){ // 빈 리스트인 경우
        v->next = v;
        cursor = v;
    }
    else{ // 빈 리스트가 아닌 경우
        v->next = cursor->next;
        cursor->next = v;
    }
}

 

 

2) 데이터 삭제

 

데이터 삭제는 리스트에 값이 한 개 있을때와 두 개 이상 있을때로 분류된다. 

(old == cursor) 인 경우

먼저 리스트에 값이 한 개만 있는 경우는 위와 같다. 커서가 NULL을 가리키게 한 뒤에 유일했던 old 노드를 삭제하면 된다. 이를 그대로 코드로 구현하면 아래와 같다.

CNode* old = cursor->next; // old 노드 지정
cursor = NULL; // 커서가 NULL 가리키게 한다
delete old; // old 노드 삭제

 

(old != cursor) 인 경우

위 그림은 리스트에 값이 두 개 이상 있는 경우다. 커서의 next가 old의 next를 가리키도록 한 뒤에 old 노드를 삭제하면 된다. 이를 그대로 코드로 구현하면 아래와 같다. 

CNode* old = cursor->next; // old 노드 지정
cursor->next = old->next
delete old; // old 노드 삭제

 

데이터 삭제는 위와 같이 두 경우만 분류하면 되기 때문에 아래와 같은 함수로 일반화 할 수 있다. remove()는 리스트에 값 하나를 삭제한다는 뜻이다. 엄밀하게 말하면 front 위치의 노드를 삭제한다는 의미다. 

void CircleList::remove(){
    CNode* old = cursor->next;
    if(old == cursor) // 리스트에 값이 하나
        cursor = NULL;
    else // 리스트에 값이 두 개 이상
        cursor->next = old->next;
    delete old;
}

 

 

여기까지 연결 리스트를 마무리 한다. 추가적인 기능은 스스로 구현해 보는걸로... 다음은 스택과 큐로 다시 돌아오겠다.