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

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의 이전 노드의 next를 now로 변경             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;         }     }; };