[자료구조와 STL] 14. list 만들기 – 더미 노드있는 이중 연결 리스트

3. 1 list 만들기 – 더미 노드있는 이중 연결 리스트

 

 먼저, 프로젝트를 만들어 앞에서 만든 파일들을 추가하는 것부터 하세요. 그리고 EHList.h를 추가합시다.

 

 EHList.h에는 템플릿 클래스인 list를 정의할 것입니다. 우리가 만들 list도 EHLIB 이름 공간 내에 정의할게요.

 

#pragma once

namespace EHLIB

{

    template<typename T>

    class list

    {

    };

};

 

 list 클래스 내부에는 node 형식이 정의해야 합니다. 그리고 node의 멤버로는 보관할 요소와 다른 노드의 위치 정보가 있어야 할 것입니다. 여기에서는 이중 연결리스트로 만들 것이기 때문에 두 개의 링크를 캡슐화할게요.

 

template<typename T>

class list

{

    struct node

    {

        node *prev; //이전 노드의 위치 정보

        node *next; //다음 노드의 위치 정보

        T data; //보관된 요소

        node(T data=0):data(data) //초기화

        {

            prev = next = 0;

        }

    };

};

 

 list에는 첫 번째 노드 위치와 마지막 노드 위치 정보 및 보관된 요소 개수를 위한 멤버 필드를 캡슐화할게요.

 

template<typename T>

class list

{

    node *head; //맨 앞 노드의 위치 정보

    node *tail;    //맨 뒤 노드의 위치 정보

    size_t bsize;  //보관된 요소 개수

};

 

 vector와 마찬가지로 보관한 요소들을 순회하여 사용할 수 있게 iterator 형식을 정의합시다. iterator 형식은 list를 사용하는 개발자의 코드에서도 사용해야 하므로 노출 수준을 public으로 지정해야 합니다.

 

template<typename T>

class list

{       

    public:

    class iterator

    {

    };

};

 

 list에서는 요소가 보관된 노드를 알아야 하고 list를 사용하는 개발자의 코드에서는 보관된 요소를 알 수 있어야 합니다. 이 두 가지 목적을 달성하기 위해 최소한 노드의 위치 정보를 알고 있어야 합니다. 이러한 이유로 node의 위치 정보를 알고 있는 멤버 필드를 캡슐화할게요.

 

class iterator

{

    node *now; //현재 노드의 위치 정보

};

 

 iterator 형식의 생성자 메서드는 특정 node의 위치 정보를 입력 인자로 받는 생성자가 필요할 것입니다.

 

class iterator

{

    public:

    iterator(node *now=0)

    {

        this->now = now;

    }

};

 

 iterator는 list 내에서는 요소를 보관된 노드의 위치 정보를 알아야 하므로 node *와 묵시적 형변환 연산자를 중복 정의할게요. 그리고 list를 사용하는 개발자 코드에서는 보관된 요소를 알아야 하므로 간접 연산자를 중복 정의하여 보관된 요소 형식을 반환합시다.

 

class iterator

{

    public:

    T operator *() //간접 연산자 중복 정의, 보관된 요소를 반환

    {

        return now->data; //현재 노드에 보관된 요소 반환

    }

    operator node *() //list 내에서 node *와 반복자 간의 묵시적 형변환 가능하게 함

    {

        return now;

    }

};

 

 list를 사용하는 개발자 코드에서 iterator를 이용하여 비교 연산을 할 수 있도록 같음(==)연산자와 다름(!=) 연산자를 중복 정의할게요.

 

class iterator

{

    public:

    bool operator == (const iterator &iter) //now 노드의 위치 정보가 같은지 판별

    {

        return now == iter.now;

    }

    bool operator != (const iterator &iter) //now 노드위 위치 정보가 다른지 판별

    {

        return now != iter.now;

    }

};

 

 그리고 list를 사용하는 개발자 코드에서 iterator를 다음으로 이동시킬 때 ++ 연산자를 사용할 수 있게 합시다.

 

class iterator

{

    public:

    iterator &operator++()//전위 ++연산자 중복 정의

    {

        now = now->next;  //now를 다음 노드의 위치 정보로 변경

        return (*this); //변경된 자기 자신을 반환

    }

    const iterator operator++(int)

    {

        iterator re(*this); //변경되기 전 자신을 복사

        now = now->next; //now를 다음 노드의 위치 정보로 변경

        return re; //변경되기 전 자신을 복사한 반복자 반환

    }

};

 

 

 list의 생성자 메서드에서는 두 개의 더미 노드를 생성하여 head와 tail 대입하고 size를 0으로 초기화하겠습니다. head와 tail에 더미 노드를 생성하여 대입하면 노드를 삽입하거나 제거하는 논리를 단순화시킬 수 있습니다. 더미 노드가 있으면 노드를 추가하는 논리는 언제나 특정한 노드와 노드 사이에 추가하는 논리로 작성하면 됩니다. 노드를 삭제할 때도 언제나 특정한 노드와 노드 사이에 있는 노드를 삭제하면 되겠죠. 더미 노드가 없다면 처음 추가되는 경우와 중간에 추가하는 경우, 맨 뒤에 추가하는 경우와 맨 앞에 추가하는 경우의 논리가 조금씩 달라집니다. 삭제의 경우도 마찬가지로 맨 앞의 노드를 제거하거나 맨 뒤에 노드를 제거, 중간에 있는 노드를 제거하는 경우의 논리가 달라집니다.

 

template<typename T>

class list

{

    public:

    list()

    {

        head = new node();//더미 노드를 생성하여 head 에 대입

        tail = new node();   //더미 노드를 생성하여 tail에 대입

        head->next = tail;  //head가 가리키는 노드의 next 정보를 tail로 변경

        tail->prev = head;  //tail이 가리키는 노드의 prev 정보를 head로 변경

        bsize = 0; //보관된 요소 개수를 0으로 대입

    }

};

[그림 8] 연결 리스트 초기화 모습

 

 list의 소멸자 메서드에서는 list 내에서 생성한 모든 노드를 소멸해야 합니다.

 

~list()

{

    while(head != tail) //맨 처음 노드와 맨 마지막 노드가 다르면

    {

        head = head->next; //head를 head가 가리키는 노드의 다음 노드로 변경

 

        //변경되기 전의 head를 삭제

        delete head->prev; //head가 가리키는 노드의 이전 노드 소멸(이전 head임)

    }

    delete head;             //마지막 남은 노드 소멸

}

 

 list에는 차례로 보관할 때 사용하는 push_back 메서드를 제공하고 있습니다. vector처럼 push_back 메서드는 end() 메서드가 반환하는 iterator 앞에 보관하면 됩니다. 즉, insert 메서드를 호출하면 되겠죠.

 

void push_back(T t)

{

    insert(end(),t); //맨 뒤에 보관, tail이 가리키는 노드 앞에 t를 보관

}

 

 list에서도 특정한 iterator 앞에 요소를 보관할 때 사용하는 insert 메서드를 제공하고 있습니다. insert 메서드에서는 요소를 보관하는 노드를 생성한 후에 생성한 노드를 입력 인자로 전달받은 iterator 앞에 매달면 됩니다.

 

void insert(iterator at, T t)

{

    node *pos = at; //at에 있는 노드를 pos에 대입(반복자에 묵시적 형변환 연산자)

    node *now = new node(t); //t를 보관한 노드를 생성하여 now에 대입

    hang_node(now,pos); //생성한 now 노드를 pos 앞에 연결

    bsize++;//보관된 요소 개수 1 증가

}

 

[그림 9] 연결 리스트에 노드를 매달기 전후의 논리적 모습

 

 특정한 노드 앞에 노드를 매다는 메서드인 hang_node는 list 내에서 사용하는 메서드로 노출 수준을 private으로 지정할게요. [그림 9]를 보면 연결 리스트에 노드를 매달기 전후의 논리적 모습을 알 수 있습니다. 여러분은 어느 노드의 어떤 링크들을 어떠한 순으로 조절해야 매달 수 있는지 파악해야 합니다. 이를 위해 여러분이 논리적인 그림을 도식하고 이를 코드로 옮기는 순서로 해결하신다면 좀 더 효과적으로 연결 리스트의 동작 원리를 이해할 수 있을 것입니다.

 

void hang_node(node *now,node *pos)

{

    //now가 가리키는 노드의 prev를 pos가 가리키는 prev로 변경

    now->prev = pos->prev;

    //now가 가리키는 노드의 next를 pos로 변경

    now->next = pos;

    //pos의 이전 노드의 next를 now로 변경

    pos->prev->next = now;

    //pos가 가리키는 노드의 prev를 now로 변경

    pos->prev = now;

}

[그림 10] 연결 리스트에 노드를 삽입하는 과정

 

 연결 리스트에서도 특정 위치에 보관된 요소를 지우는 erase 메서드를 제공하고 있습니다. erase 메서드에서는 리스트에서 해당 위치에 있는 노드의 연결을 끊는 작업이 필요합니다. 그리고 해당 요소를 보관하기 위해 동적으로 생성한 node 개체를 소멸해야겠지요.

 

void erase(iterator at)

{

    dehang_node(at); //at에 있는 노드를 리스트에서 연결을 끊는다.

    node *pos = at;

    delete pos; //at에 있는 노드를 소멸

    bsize--; //보관한 요소 개수 1 감소

}

 

 de_hang 메서드에서는 입력 인자로 전달된 노드의 위치 정보를 통해 이전 노드와 이후 노드의 링크를 변경해 주어야 할 것입니다. 어떠한 노드의 어느 링크를 조절해야 하는지 논리적으로 그림을 그려보세요.

[그림 11] 연결리스트에서 노드를 끊는 과정

 

 

void dehang_node(node *pos)

{

    //pos의 이전 노드의 next를 pos의 next로 변경

    pos->prev->next = pos->next;

    //pos의 다음 노드의 prev를 pos의 prev로 변경

    pos->next->prev = pos->prev;

}

 

 list 에서도 iterator를 사용할 수 있게 하려고 맨 앞에 보관된 요소가 있는 iterator를 반환하는 begin 메서드와 차례대로 보관할 때 보관할 위치(맨 마지막에 보관된 요소의 다음 위치)를 반환하는 end 메서드를 제공하고 있습니다. 연결 리스트를 생성할 때 head와 tail에 더미 노드를 생성하여 초기화를 하였기 때문에 맨 앞에 보관된 요소는 head가 가리키는 노드의 다음에 있게 되며 차례대로 보관할 때에는 tail이 가리키는 노드 앞에 보관하게 됩니다.

 

iterator begin()

{

    //head는 더미 노드이므로 head의 다음 노드가 첫 번째 보관된 요소가 있는 노드임

    return head->next; //head의 다음 노드를 반환(iterator와 node *는 묵시적 형변환)

}

iterator end()

{

    //end는 맨 마지막 보관된 요소의 다음 위치를 반환하므로 tail을 반환함

    return tail;   

}

 

 이 외에도 보관된 요소 개수를 반환하는 size 메서드와 보관된 요소의 개수를 갱신하는 resize 메서드를 제공할게요.

 

size_t size()

{

    return bsize;

}

 

void resize(size_t nsize)

{

     //0을 늘어난 개수 만큼 차례대로 보관

    for(size_t n=bsize; n<nsize ; n++)

    {

        insert(end(),0);

    }

}