5. list 만들기 [디딤돌 자료구조와 알고리즘 with C++]

5. list 만들기

이번에는 STL의 list를 모델 삼아 list를 만들어 보기로 해요.

 

4장에서는 vector를 만들었습니다. 그 프로젝트에서 헤더파일 포함문과 using 문만 변경하세요.

//#include <vector>

//#include <algorithm>

//using std::vector;

//using std::find;

//using std::find_if;

#include "list.h"

#include "algorithm.h"

using ehlib::list;

typedef list<Genre *> Genres;

typedef Genres::iterator GIter;

typedef Genres::const_iterator GCIter;

 

물론 list.h 파일과 algorithm.h 파일을 프로젝트에 추가하세요. alogorithm은 4장에서 만든 것과 똑같습니다.

 

현재 구현한 것이 없기 때문에 프로젝트를 다시 빌드하면 컴파일 오류가 날 거예요. 오류가 나는 것을 하나 하나 수정하여 컴파일 오류만 나지 않게 하세요. 물론 코드 내부는 비어있는 상태입니다.

 

vector에서는 인덱스 연산자를 제공하지만 list에서는 인덱스 연산자를 제공하지 않습니다. 따라서 list는 순차적으로 보관하거나 특정 키 순으로 보관할 수 있지만 인덱스 연산은 사용할 수 없습니다. 또한 순차적으로 보관하거나 특정 키 순으로 보관하는 것은 list와 사용 방법이 같습니다.

 

4장에서 만든 세 개의 프로젝트 중에 순차적으로 보관하는 프로젝트와 특정 키 순으로 적용하면 다음과 같은 형태로 작성하면 컴파일 오류가 발생하지 않아요. 이게 이번 장에서 작성할 list입니다.

 

//list.h

#pragma once

namespace ehlib

{

    template<typename Data>

    class list

    {

    public:

        class iterator

        {

        public:

            iterator()

            {        

            }

            Data operator *()const

            {

                 return 0;

            }

            iterator &operator++()

            {

                return (*this);

            }

            const iterator operator++(int)

            {

                iterator re(*this);

                return re;

            }

            bool operator !=(const iterator &iter)const

            {

                return false;

            }

            bool operator ==(const iterator &iter)const

            {

                return false;

            }

        };

        typedef iterator const_iterator;

        list()

        {

        }

        ~list()

        {        

        }

        void push_back(Data data)

        {        

        }

        void insert(iterator at, Data data)

        {

        }

        void erase(iterator at)

        {

        }       

        iterator begin()

        {

            iterator iter;

            return iter;

        }

        iterator end()

        {           

            iterator iter;

            return iter;

        }

        const_iterator begin()const

        {

            iterator iter;

            return iter;

        }

        const_iterator end()const

        {           

            iterator iter;

            return iter;

        }

        size_t size()

        {

            return 0;

        }       

    };

}

 

5.1 list 구현

이제 STL의 list를 모델로 정의한 list를 구현합시다.

#pragma once

namespace ehlib

{

    template<typename Data>

    class list

    {

리스트 내부에 노드를 정의합시다. 여기에서는 링크가 두 개 있는 노드를 정의할게요.

        struct node

        {

            Data data;

            node *prev;

            node *next;

            node(Data data=0)

            {

                this->data = data;

                prev = next = 0;

            }

        };

리스트에는 맨 앞 노드와 맨 뒤 노드를 기억하는 head와 tail 멤버를 선언하세요.

        node *head;

        node *tail;

보관한 데이터 개수를 기억하는 멤버도 선언하세요.

        int count;

    public:

        class iterator

        {

반복자는 보관한 자료의 위치를 기억하고 있어야 합니다. 리스트에는 자료를 노드에 보관하므로 노드의 위치를 멤버로 선언하세요.

            node *now;

        public:

생성자는 기본 생성이 가능하게 디폴트 인자를 사용하세요.

            iterator(node *now=0)

            {        

                this->now = now;

            }

간접 연산으로 보관한 자료를 반환하게 구현하세요.

            Data operator *()const

            {

                 return now->data;

            }

 

리스트 내부에서는 반복자 내부의 노드의 위치 정보를 알 수 있어야 합니다. 여기에서는 묵시적 형 변환 연산을 정의할게요.

            operator node *()

            {

                return now;

            }

증가 연산자에서는 now를 다음 위치로 이동하세요.

            iterator &operator++()

            {

                now = now->next;

                return (*this);

            }

나머지 증가 연산자도 now를 다음 위치로 이동하세요.

            const iterator operator++(int)

            {

                iterator re(*this);

                now = now->next;

                return re;

            }

            bool operator !=(const iterator &iter)const

            {  

                return now != iter.now;

            }

            bool operator ==(const iterator &iter)const

            {

                return now == iter.now;

            }

        };

        typedef iterator const_iterator;

 

생성자를 정의합시다.

        list()

        {

생성자에서는 head와 tail에 더미 노드를 생성하고 링크를 조절하세요. 여기에서 작성하는 이중 연결리스트는 3.2.2에서 작성했던 더미있는 이중 연결리스트입니다.

            head = new node();

            tail = new node();

            head->next = tail;

            tail->prev = head;

보관한 자료의 개수를 0으로 설정하세요.

            count = 0;

        }

 

소멸자를 정의합시다.

        ~list()

        {

맨 앞의 노드부터 순차적으로 소멸하세요.

            node *prev=0;

head가 존재하면 반복하세요.

            while(head !=0)

            {

head를 이동하기 전에 prev에 기억하세요.

                prev = head;

                head = head->next;

기억해 두었던 prev의 노드를 소멸하세요.

                delete prev;

            }

        }

 

순차적으로 보관하는 push_back 메서드를 구현합시다.

        void push_back(Data data)

        {

순차 보관하는 push_back에서는 insert 메서드를 이용하여 맨 끝에 보관합니다.

            insert(end(),data);

        }

 

특정 위치 앞에 보관하는 insert 메서드를 구현합시다.

        void insert(iterator at, Data data)

        {

자료를 보관할 노드를 생성하세요.

            node *now = new node(data);

반복자 형식에는 node * 형식으로 묵시적 형 변환을 정의하였습니다. node * 형식으로 얻어오세요.

            node *pos = at;

now 노드를 pos 앞에 매달기 위해 링크를 조절하세요. 자세한 내용은 3.2.2를 참고하세요.

            now->next = pos;

            now->prev = pos->prev;

            pos->prev->next = now;

            pos->prev = now;

보관한 자료 개수를 1 증가하세요.

            count++;

        }

 

 

특정 위치의 자료를 제거하는 erase 메서드를 구현합시다.

        void erase(iterator at)

        {

            node *now = at;

삭제할 노드의 링크를 끊어야겠죠.

            now->prev->next = now->next;

            now->next->prev = now->prev;

자료를 보관한 노드를 소멸하고 보관한 자료 개수를 1 감소하세요.

            delete now;

            count--;

        }

 

        iterator begin()

        {

head는 더미 노드를 가리키므로 head의 next가 자료를 보관하고 있는 첫 번째 노드입니다.

            iterator iter(head->next);

            return iter;

        }

        iterator end()

        {

end는 맨 마지막 자료를 보관한 다음 위치를 의미하죠. tail이 가리키는 노드는 맨 마지막 자료를 보관한 다음 위치입니다.

            iterator iter(tail);

            return iter;

        }

        const_iterator begin()const

        {

            iterator iter(head->next);

            return iter;

        }

        const_iterator end()const

        {           

            iterator iter(tail);

            return iter;

        }

        size_t size()

        {

보관한 자료 개수를 반환하세요.

            return count;

        }       

    };

}

 

5.2 list 코드

다음은 앞에서 작성한 list 코드입니다.

//list.h

#pragma once

namespace ehlib

{

    template<typename Data>

    class list

    {       

        struct node

        {

            Data data;

            node *prev;

            node *next;

            node(Data data=0)

            {

                this->data = data;

                prev = next = 0;

            }

        };

        node *head;

        node *tail;

        int count;

    public:

        class iterator

        {    

            node *now;

        public:

            iterator(node *now=0)

            {        

                this->now = now;

            }

            Data operator *()const

            {

                 return now->data;

            }

            operator node *()

            {

                return now;

            }

            iterator &operator++()

            {

                now = now->next;

                return (*this);

            }

            const iterator operator++(int)

            {

                iterator re(*this);

                now = now->next;

                return re;

            }

            bool operator !=(const iterator &iter)const

            {  

                return now != iter.now;

            }

            bool operator ==(const iterator &iter)const

            {

                return now == iter.now;

            }

        };

        typedef iterator const_iterator;

        list()

        {

            head = new node();

            tail = new node();

            head->next = tail;

            tail->prev = head;

            count = 0;

        }

        ~list()

        {

            node *prev=0;

            while(head !=0)

            {

                prev = head;

                head = head->next;

                delete prev;

            }

        }       

        void push_back(Data data)

        {

            insert(end(),data);

        }

        void insert(iterator at, Data data)

        {

            node *now = new node(data);

            node *pos = at;

            now->next = pos;

            now->prev = pos->prev;

            pos->prev->next = now;

            pos->prev = now;

            count++;

        }

        void erase(iterator at)

        {

            node *now = at;

            now->prev->next = now->next;

            now->next->prev = now->prev;

            delete now;

            count--;

        }       

        iterator begin()

        {

            iterator iter(head->next);

            return iter;

        }

        iterator end()

        {           

            iterator iter(tail);

            return iter;

        }

        const_iterator begin()const

        {

            iterator iter(head->next);

            return iter;

        }

        const_iterator end()const

        {           

            iterator iter(tail);

            return iter;

        }

        size_t size()

        {

            return count;

        }

    };

}