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

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

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

list 만들기 – 더미 노드있는 이중 연결 리스트 소스 코드

 


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;

            }

            bool operator == (const iterator &iter)

            {

                return now == iter.now;

            }

            bool operator != (const iterator &iter)

            {

                return now != iter.now;

            }

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

            {

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

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

            }

 

 

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

            {

                iterator re(*this); //자신을 복제

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

                return re; //변경 전 복제한 반복자 반환

            }

        };

        list()

        {

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

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

            head->next = tail; //head가 가리키는 노드의 next tail로 대입

            tail->prev = head; //tail이 가리키는 노드이 prev head로 대입

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

        }

        ~list()

        {

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

            {

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

 

                //변경되기 전 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)

        {

            //맨 마지막 보관된 요소의 노드 뒤에 보관

            //end는 맨 마지막 보관된 요소의 노드 뒤임

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

        }

        iterator begin()

        {

            //맨 앞에 보관된 요소의 위치를 반환

            //head의 다음 노드가 요소가 보관된 맨 앞 노드임

            return head->next; //head next 반환(node *와 반복자는 묵시적 형변환)

        }

        iterator end()

        {

            //맨 마지막에 보관된 요소의 다음 위치를 반환

            //tail은 맨 마지막에 보관된 요소의 다음 위치 노드

            return tail; //tail 반환(node *와 반복자는 묵시적 형변환)

        }

        size_t size()

        {

            return bsize;

        }

 

        void insert(iterator at, T t)

        {

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

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

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

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

        }

        void erase(iterator at)

        {

            dehang_node(at); //at에 있는 노드의 연결을 끊음

            node *pos = at; //at에 있는 노드 위치를 pos에 대입(묵시적 형변환)

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

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

        }

private:

        //now 위치의 노드를 pos 앞에 연결하는 메서드

        void hang_node(node *now,node *pos)

        {

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

            now->prev = pos->prev;

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

            now->next = pos;

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

            pos->prev->next = now;

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

            pos->prev = now;

        }

 

        //pos 위치의 노드를 리스트에서 연결 끊는 메서드

        void dehang_node(node *pos)

        {

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

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

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

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

        }

    };

};

 

반응형