언어 자료구조 알고리즘/Escort 자료구조와 STL

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

언제나휴일 2016. 4. 18. 10:42
반응형

 

AboutList.zip


//EHList.h 더미노드가 없는 이중 연결 리스트

#pragma once

namespace EHLIB

{

    template<typename T>

    class list

    {

        struct node

        {

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

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

            T data; //노드에 보관된 요소

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

            {

                prev = next = 0;

            }

        };

 

        node *head; //리스트 맨 앞에 있는 노드 위치 정보

        node *tail;   //리스트 맨 뒤에 있는 노드 위치 정보

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

    public:

        class iterator

        {

            node *now;

        public:

            iterator(node *now=0)

            {

                this->now = now;

            }

            T operator *()//간접 연산자 중복 정의

            {

                return now->data; //현재 위치에 보관된 요소를 반환

            }

            operator node *()//node *와 반복자의 묵시적 형변환 연산자 중복 정의

            {

                return now; //now를 반환

            }

            bool operator == (const iterator &iter)

            {

                return now == iter.now;

            }

            bool operator != (const iterator &iter)

            {

                return now != iter.now;

            }

 

 

 

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

            {

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

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

            }

            const iterator operator++(int) //후위 ++ 연산자 중복 정의

            {

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

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

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

            }

        };

        list()

        {

            head = tail = 0;

            bsize = 0;

        }

        ~list()

        {

            while(head != tail) //head tail이 다른 노드를 가리키면

            {

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

                delete head->prev; //head의 이전 노드 소멸(변경 전 head)

            }

            delete head; //하나 남은 노드 소멸

        }

 

 

 

 

 

        void resize(size_t nsize)

        {

            //0으로 추가된 요소 개수만큼 차례대로 보관

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

            {

                insert(end(),0);

            }

        }

        void push_back(T t)

        {

            //t를 맨 뒤에 보관, end는 맨 뒤에 보관된 요소 다음 위치임

            insert(end(),t); //end 앞에 t를 보관

        }

        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 증가

        }

        void erase(iterator at)

        {

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

            node *pos = at; //at pos에 대입(묵시적 형변환)

            delete pos; //pos 위치의 노드 소멸

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

        }

        iterator begin()

        {

            return head; //더미 노드가 없으므로 head가 가리키는 노드를 반환

        }

        iterator end()

        {

            //맨 마지막 보관된 요소의 노드 다음 위치 반환,

            //더미 노드가 없으므로 tail이 가리키는 노드에 마지막 보관된 요소가 있음

            return 0; //tail next 0으로 0 반환(묵시적 형변환)

        }

        size_t size()

        {

            return bsize;

        }

    private:

        //now pos앞에 매다는 메서드

        void hang_node(node *now,node *pos)

        {

            if(pos)

            {

                if(pos == head) // 맨 앞에 매다는 경우

                {

                    now->next = head; //now의 다음은 head로 대입

                    head->prev = now; //head가 가리키는 노드의 prev now로 변경

                    head = now; //head now로 변경

                }

                else/ /중간에 매다는 경우

                {

                    now->prev = pos->prev;

                    now->next = pos;

                    pos->prev->next = now;

                    pos->prev = now;

                }

            }

 

            else

            {

                if(pos == head) //아무것도 없을 때

                {

                    head = tail = now;

                }

                else //맨 뒤에 매다는 경우

                {

                    tail->next = now; //tail이 가리키는 노드의 next now로 변경

                    now->prev = tail; //now의 이전은 tail로 대입

                    tail = now; //tail now로 변경

                }

            }

        }

        void dehang_node(node *pos)

        {

            if(pos->prev) //pos의 이전 노드가 있다면

            {

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

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

            }

            else //pos의 이전 노드가 없다면, pos head

            {

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

            }

            if(pos->next) // pos의 다음 노드가 있다면

            {

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

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

            }

 

            else //pos의 다음 노드가 없다면, pos tail

            {

                tail = tail->prev; //tail tail의 이전 노드 위치 정보로 변경

            }

        }

    };

};

 

반응형