# Encapsulates a double linked listIn this blog, I will try to encapsulate a double linked list.

# DefinitionsIn computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes.

# FunctionThis double linked list contains these functions:

Getting the size of the list. Checking the list whether empty or not. Inserting element in anywhere in the list. Deleting element in anywhere in the list. Getting element in anywhere in the list. Showing the whole list. Clearing the whole list. Using the iterator to traverse the whole list. # MethodI define a class named DoubleLink. In the class, it has a private class about node , properties, interface, and iterator.

# node classThe object of this class is the element in DoubleLink. The node class has three properties. one property which stores data is generic paradigm. The other two properties are pointers which point to the next or previous element.

let us look the code:

1 2 3 4 5 6 7 private : class node { public : T data; node *prev; node *next; };

# IteratorI define a Iterator class to traverse the whole elements of the list. By overloading the operator, I can traverse the list by ++ instead of by ->next;

let us look the code:

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 public : class Iterator { private : node *prv; public : Iterator(node* p = nullptr ) { prv = p; } ~Iterator(){ if (prv!=NULL ) delete prv; } Iterator& operator ++ () { prv = prv->next; return *this ; } Iterator& operator = (Iterator x){ prv=x.prv; return *this ; } Iterator& operator -- () { prv = prv->prev; return *this ; } T operator *() const { return prv->data; } bool operator != (const Iterator& rhs) const { return (rhs.prv != this ->prv); } bool operator == (const Iterator& rhs) const { return (rhs.prv == this -> prv); } };

# PropertyBecause the List need some variables to express the properties, I define some variable.

*head :a pointer point the head of list *tail :a pointer point the tail of list len :the size of the list1 2 3 4 private : node *head; node *tail; int len;

# InterfaceI define these interfaces to realize the functions of the 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 public : DoubleLink(); DoubleLink(const DoubleLink &l); ~DoubleLink(); Iterator begin () { return Iterator(head); } Iterator end () { return Iterator(tail->next); } int size () ; bool IsEmpty () ; void insert (int index,T data) ; void pushBack (T data) ; void pushHead (T data) ; T get (int index) ; void popBack () ; void deletenode (int index) ; void popHead () ; void show () ; void clear () ;

# Constructor and Copy ConstructorThrough the constructor, the properties of list has a initial value.

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 template <class T >DoubleLink <T>: :DoubleLink(){ head = NULL ; tail =NULL ; len =0 ; } ``` Through the copy constructor, we can assign a DoubleList object to the others ```C++ template <class T >DoubleLink <T>: :DoubleLink(const DoubleLink &l){ if (l.head!=NULL ) { node *tmp=l.head; head = new node(); head ->data=tmp->data; len++; tmp=tmp->next; node *temp = head; while (tmp!=l.tail) { temp->next = new node(); len++; temp->data = tmp->data; tmp = tmp->next; } } else { head=tail=NULL ; len = 0 ; } }

# DestructorThrough the destructor ,we delete all nodes in the list to avoid memory leak.

1 2 3 4 5 6 7 8 9 10 11 12 template <class T >DoubleLink <T>: :~DoubleLink(){ node *tmp=head; while (head!=tail) { head=head->next; delete tmp; tmp = head; } len = 0 ; }

# getsize()We can get the number of nodes in the list

1 2 3 4 5 template <class T >int DoubleLink <T>: :size(){ return len; }

# IsEmpty()We can check the list whether empty or not

1 2 3 4 5 template <class T >bool DoubleLink <T>: :IsEmpty(){ return len==0 ; }

# insert() , pushBack() , pushHead()We use these function to insert the element to the 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 template <class T >void DoubleLink <T>: :insert(int index,T data){ node *p,*q; p= head; q=head->next; if (index>len||index<0 ) cout <<"you can't add the node,because the index you entered is wrong" <<endl ; else { for (int i=2 ;i<index;++i) { p=p->next; q=q->next; } p->next = new node(); p->next->data= data; p->next->prev=p; q->prev=p->next; q->prev->next=q; } } template <class T >void DoubleLink <T>: :pushBack(T data){ if (head==NULL ) { head = new node(); head->data = data; len++; tail=head; } else { tail->next=new node(); tail->next->data= data; len++; tail->next->prev=tail; tail=tail->next; tail->next=NULL ; } } template <class T >void DoubleLink <T>: :pushHead(T data){ if (head==NULL ) { head = new node(); head->data = data; len++; tail=head; } else { head->prev=new node(); head->prev->data= data; len++; head->prev->next=head; head=head->prev; } }

# get()This function can return data of node.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 template <class T >T DoubleLink <T>: :get(int index){ node *p; p=head; if (index<0 ||index>len) { cout <<"you can't get it.because you enter a wrong index" <<endl ; return NULL ; } else { for (int i=1 ;i<index;++i) { p=p->next; } return p->data; } }

# deletenode() ,popBack(), popHead()These functions can delete elements in lists.

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 template <class T >void DoubleLink <T>: :deletenode(int index){ node *p,*q; p=head; q=head->next; if (index==1 ) { head=head->next; delete head->prev; return ; } if (index==len) { tail=tail->prev; delete tail->next; return ; } if (index>len||index<0 ) cout <<"you can't delete the node,because the index you entered is wrong" <<endl ; else { for (int i=2 ;i<index;++i) { p=p->next; q=q->next; } p->next= q->next; q->next->prev=p; delete q; } } template <class T >void DoubleLink <T>: :popBack(){ if (len==0 ) cout <<"the link is empty" <<endl ; else { tail=tail->prev; delete tail->next; tail->next=NULL ; } } template <class T >void DoubleLink <T>: :popHead(){ if (len==0 ) cout <<"the link is empty" <<endl ; else { head=head->next; delete head->prev; } }

# show()Showing the whole 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 template <class T >void DoubleLink <T>: :show(){ node *p; p= head; if (p==NULL ) { cout <<"Link is empty" <<endl ; } else { while (p!=tail->next) { cout <<p->data<<" " ; p=p->next; } cout <<endl ; } } ``` ###### clear() Remove the list . ```C++ template <class T >void DoubleLink <T>: :clear(){ node *p; p=head->next; while (p!=tail) { p=p->next; delete p->prev; } delete head; delete tail; tail=NULL ; head=NULL ; len=0 ; }

# The Whole Code

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 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 #include <iostream> #include <cstdio> using namespace std ;template <class T >class DoubleLink //the class of Double link { private : class node { public : T data; node *prev; node *next; }; public : class Iterator { private : node *prv; public : Iterator(node* p = nullptr ) { prv = p; } ~Iterator(){ if (prv!=NULL ) delete prv; } Iterator& operator ++ () { prv = prv->next; return *this ; } Iterator& operator = (Iterator x){ prv=x.prv; return *this ; } Iterator& operator -- () { prv = prv->prev; return *this ; } T operator *() const { return prv->data; } bool operator != (const Iterator& rhs) const { return (rhs.prv != this ->prv); } bool operator == (const Iterator& rhs) const { return (rhs.prv == this -> prv); } }; private : node *head; node *tail; int len; public : DoubleLink(); DoubleLink(const DoubleLink &l); ~DoubleLink(); Iterator begin () { return Iterator(head); } Iterator end () { return Iterator(tail->next); } int size () ; bool IsEmpty () ; void insert (int index,T data) ; void pushBack (T data) ; void pushHead (T data) ; T get (int index) ; void popBack () ; void deletenode (int index) ; void popHead () ; void show () ; void clear () ; }; template <class T >DoubleLink <T>: :DoubleLink(){ head = NULL ; tail =NULL ; len =0 ; } template <class T >DoubleLink <T>: :DoubleLink(const DoubleLink &l){ if (l.head!=NULL ) { node *tmp=l.head; head = new node(); head ->data=tmp->data; len++; tmp=tmp->next; node *temp = head; while (tmp!=l.tail) { temp->next = new node(); len++; temp->data = tmp->data; tmp = tmp->next; } } else { head=tail=NULL ; len = 0 ; } } template <class T >DoubleLink <T>: :~DoubleLink(){ node *tmp=head; while (head!=tail) { head=head->next; delete tmp; tmp = head; } len = 0 ; } template <class T >int DoubleLink <T>: :size(){ return len; } template <class T >bool DoubleLink <T>: :IsEmpty(){ return len==0 ; } template <class T >void DoubleLink <T>: :insert(int index,T data){ node *p,*q; p= head; q=head->next; if (index>len||index<0 ) cout <<"you can't add the node,because the index you entered is wrong" <<endl ; else { for (int i=2 ;i<index;++i) { p=p->next; q=q->next; } p->next = new node(); p->next->data= data; p->next->prev=p; q->prev=p->next; q->prev->next=q; } } template <class T >void DoubleLink <T>: :pushBack(T data){ if (head==NULL ) { head = new node(); head->data = data; len++; tail=head; } else { tail->next=new node(); tail->next->data= data; len++; tail->next->prev=tail; tail=tail->next; tail->next=NULL ; } } template <class T >void DoubleLink <T>: :pushHead(T data){ if (head==NULL ) { head = new node(); head->data = data; len++; tail=head; } else { head->prev=new node(); head->prev->data= data; len++; head->prev->next=head; head=head->prev; } } template <class T >T DoubleLink <T>: :get(int index){ node *p; p=head; if (index<0 ||index>len) { cout <<"you can't get it.because you enter a wrong index" <<endl ; return NULL ; } else { for (int i=1 ;i<index;++i) { p=p->next; } return p->data; } } template <class T >void DoubleLink <T>: :deletenode(int index){ node *p,*q; p=head; q=head->next; if (index==1 ) { head=head->next; delete head->prev; return ; } if (index==len) { tail=tail->prev; delete tail->next; return ; } if (index>len||index<0 ) cout <<"you can't delete the node,because the index you entered is wrong" <<endl ; else { for (int i=2 ;i<index;++i) { p=p->next; q=q->next; } p->next= q->next; q->next->prev=p; delete q; } } template <class T >void DoubleLink <T>: :popBack(){ if (len==0 ) cout <<"the link is empty" <<endl ; else { tail=tail->prev; delete tail->next; tail->next=NULL ; } } template <class T >void DoubleLink <T>: :popHead(){ if (len==0 ) cout <<"the link is empty" <<endl ; else { head=head->next; delete head->prev; } } template <class T >void DoubleLink <T>: :show(){ node *p; p= head; if (p==NULL ) { cout <<"Link is empty" <<endl ; } else { while (p!=tail->next) { cout <<p->data<<" " ; p=p->next; } cout <<endl ; } } template <class T >void DoubleLink <T>: :clear(){ node *p; p=head->next; while (p!=tail) { p=p->next; delete p->prev; } delete head; delete tail; tail=NULL ; head=NULL ; len=0 ; } int main () { int n,m; DoubleLink<int >* lin=new DoubleLink<int >(); if (lin->IsEmpty()) { cout <<"空链表" <<endl ; } else { cout <<"链表非空" <<endl ; } cout <<"插入节点:" <<endl ; lin->pushBack(5 ); lin->pushBack(8 ); lin->pushBack(7 ); lin->pushBack(4 ); lin->pushBack(3 ); lin->pushBack(4 ); lin->pushBack(1 ); lin->pushBack(0 ); cout <<"链表大小" <<endl ; cout <<lin->size()<<endl ; cout <<"输出所有节点:" <<endl ; lin->show(); if (lin->IsEmpty()) { cout <<"空链表" <<endl ; } else { cout <<"链表非空" <<endl ; } cout <<"输入要查找第几个节点：" <<endl ; cin >>n; cout <<lin->get(n)<<endl ; cout <<"输入要删除第几个节点：" <<endl ; cin >>n; lin->deletenode(n); lin->show(); cout <<"头部添加节点：" <<endl ; cin >>n; lin->pushHead(n); lin->show(); cout <<"在任意位置添加结点：" <<endl ; cout <<"位置：" <<endl ; cin >>m; cout <<"节点：" <<endl ; cin >>n; lin->insert(m,n); lin->show(); cout <<"头部删除节点：" <<endl ; lin->popHead(); lin->show(); cout <<"尾部删除节点：" <<endl ; lin->popBack(); lin->show(); cout <<"输出迭代器第一个" <<endl ; DoubleLink<int >::Iterator it=lin->begin(); cout <<"迭代器遍历" <<endl ; for (DoubleLink<int >::Iterator it=lin->begin();it!=lin->end();++it) { cout <<*it<<" " ; } cout <<endl ; cout <<"清空节点：" <<endl ; lin->clear(); lin->show(); if (lin->IsEmpty()) { cout <<"空链表" <<endl ; } else { cout <<"链表非空" <<endl ; } return 0 ; }