A doubly linked list for a low memory situation

Sprache: English
Programmiersprache: C++
Veröffentlicht von: yanir [nicht registriert]
Letzte Änderung: 15.05.2006
Aufrufe: 1158

Lizenz: GNU General Public License

Beschreibung

this list uses a single pointer size "link" to point to both the previous and the next nodes in a list. the 'link' is a value calculated from XORing the poinets to the previous and next pointers. the travese needs two pointers to calculate the third.

Code

Zeilennummern anzeigen

1 2 typedef struct node{ 3 char data; 4 unsigned long link; 5 }node; 6 7 8 class xlList{ 9 public: 10 int IsEmpty(){return (!Cur);}//returns nonzero if empty 11 void Insert(char dat);// inserts after current. current will point to the inserted object 12 int Next(); // returns 0 on success,nonzero on failure (last or empty) 13 int Prev(); // returns 0 on success,nonzero on failure (first or empty) 14 int Del(); //deletes the current node 15 //moves to the next node or to the previous node if it was the last. 16 // returns 0 on success 17 int Data(char* container);//fills container with the data of the current node 18 //returns 0 on success 19 //1 on failure and container is unchanged. 20 xlList(){Cur = Back = NULL;} 21 private: 22 node *Cur,*Back; 23 // create the link of two pointers. 24 unsigned long MakeLink(node*prev,node*next){return (unsigned long)prev^(unsigned long)next;} 25 // calculate the next and prev of an existing node. 26 node *Next(node*cur,node*prev){return (node*)(cur->link^(unsigned long)prev);} 27 node *Prev(node*cur,node*next){return (node*)(cur->link^(unsigned long)next);} 28 }; 29 30 int xlList::Data(char *container) 31 { 32 if(!Cur)return 1; 33 *container = Cur->data; 34 return 0; 35 } 36 37 void xlList::Insert(char dat) 38 { 39 node* pTmp = new node; 40 pTmp->data = dat; 41 pTmp->link = 0; 42 if(!Cur){ 43 Cur=pTmp; 44 return; 45 } 46 node* pNext = Next(Cur,Back); 47 pTmp->link = MakeLink(Cur,pNext); 48 Cur->link = MakeLink(Back,pTmp); 49 Back = Cur; 50 if(pNext){//update the link of the next to the newly inserted 51 Cur = pNext; 52 pNext = Next(Cur,Back); 53 Cur->link = MakeLink(pTmp,pNext); 54 } 55 //BACK 1 NODE to point to the new node 56 Cur = pTmp; 57 } 58 59 int xlList::Next() 60 { 61 if(!Cur)return 1; 62 node*next = Next(Cur,Back); 63 if(!next)return 1; 64 Back = Cur; 65 Cur = next; 66 return 0; 67 } 68 69 int xlList::Prev() 70 { 71 if(!Cur)return 1; 72 if(!Back)return 1; 73 node* pprev = Prev(Back,Cur); 74 Cur = Back; 75 Back = pprev; 76 return 0; 77 } 78 79 int xlList::Del() 80 { 81 if(!Cur)return 1; 82 node* pNext = Next(Cur,Back); 83 node* pTmp; 84 if(pNext){ //update the link of "next" 85 pTmp = Next(pNext,Cur); 86 pNext->link = MakeLink(Back,pTmp); 87 } 88 if(Back){ 89 pTmp = Prev(Back,Cur); 90 Back->link = MakeLink(pTmp,pNext); 91 } 92 delete Cur; 93 Cur = NULL; 94 if(pNext){ 95 Cur = pNext; 96 }else if(Back){ 97 Cur = Back; 98 Back = Prev(Cur,pNext); 99 } 100 return 0; 101 } 102 103 // a simple tester for the class 104 // adds traverses and deletes the list 105 106 107 #include <iostream.h> 108 109 main() 110 { 111 xlList theList; 112 char i; 113 for(i='a';i<='p';i++){ 114 cout << i << ','; 115 theList.Insert(i); 116 } 117 theList.Prev(); 118 theList.Prev(); 119 cout << endl; 120 for(i='q';i<='z';i++){ 121 cout << i << ','; 122 theList.Insert(i); 123 } 124 cout << "finished inserting"<< endl; 125 while(!theList.Prev()); 126 127 for(i='a';i<='z';i++){ 128 char c=0; 129 theList.Data(&c); 130 cout << c << ','; 131 theList.Next(); 132 } 133 cout << endl; 134 for(i='a';i<='z';i++){ 135 char c=0; 136 theList.Data(&c); 137 cout << c << ','; 138 theList.Prev(); 139 } 140 cout << endl; 141 while(!theList.IsEmpty())theList.Del(); 142 cin >> i; 143 return 0; 144 } 145

Noch kein Kommentar vorhanden

Dieses Snippet kommentieren

Name *

E-Mail (wird nicht angezeigt) *

Website

Kommentar *

Sicherheitscode *