이제 STL의 list를 모델로 정의한 list를 구현합시다. 설명은 주석으로 해 놓았어요.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 |
#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; } }; } |
