[자료구조와 STL] 18. 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; //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의 이전 노드 위치 정보로 변경             }         }     }; };