1 #ifndef LINKLIST_H
  2 #define LINKLIST_H
  3 #endif
  4 #include<iostream>
  5
  6 using namespace std;
  7
  8 template<class unk>
  9 class NODE{
 10         public:
 11                 NODE<unk>( unk value, NODE<unk> *item_to_link_to = 0);
 12                 inline unk value();
 13                 inline void value(unk);
 14                 inline NODE<unk> * next();
 15                 inline void next(NODE<unk> *);
 16
 17                 ~NODE<unk>();
 18
 19         
 20         private: 
 21                 unk _value;
 22                 NODE<unk> *_next;
 23 };
 24
 25 template<class unk>
 26 inline NODE<unk>::NODE(unk value, NODE<unk> *item): _value(value) {
 27        if (!item){
 28                 //cout << "_value=> " << _value << endl;
 29                _next = 0;
 30        }
 31        else{
 32                 //cout << "insert after _value=> " << _value << endl;
 33                //_next = item->_next;
 34                next(item->next());
 35                item->next(this);
 36
 37                //inserts after on construction
 38        }
 39 };
 40
 41
 42 template<class unk>
 43 inline unk NODE<unk>::value(){ if(this != NULL) return _value; else return NULL; };
 44
 45 template<class unk>
 46 inline void NODE<unk>::value(unk val){
 47         _value = val;
 48 }
 49
 50 template<class unk>
 51 inline  NODE<unk> * NODE<unk>::next(){ if(this != NULL) return _next; else return NULL; };
 52
 53 template<class unk>
 54 inline void NODE<unk>::next(NODE<unk> * nxt){
 55         //cout << "Adding Next \n";
 56         _next = nxt;
 57 }
 58
 59 template<class unk>
 60 class LIST{
 61         public:
 62                 LIST<unk>() : _at_front(0), _at_end(0), _size(0) {}
 63                 inline int size();
 64                 inline void insert(NODE<unk> *, unk);
 65                 inline void insert(unk);
 66                 inline void front(unk);
 67                 inline void up_size();
 68                 inline void down_size();
 69                 void display(ostream &os = cout);
 70                 void remove_front();
 71                 void remove_all();
 72                 void remove_item(unk);
 73                 void remove_item(NODE<unk> *);
 74                 NODE<unk> * find(unk);
 75                 NODE<unk> * find_all(unk, NODE<unk> * last = NULL );
 76
 77                 ~LIST<unk>();
 78
 79         private:
 80                 NODE<unk> *_at_front;
 81                 NODE<unk> *_at_end;
 82                 int _size;
 83                 LIST<unk>(const LIST<unk>&);
 84                 LIST<unk>& operator=( const LIST<unk>&);
 85 };
 86
 87 template<class unk>
 88 inline int LIST<unk>::size(){return _size;}
 89 template<class unk>
 90 inline LIST<unk>::~LIST<unk>(){remove_all();}
 91 template<class unk>
 92 inline void LIST<unk>::insert(NODE<unk> *ptr, unk value){
 93         up_size();
 94         //cout << "insert:  ptr =>" << ptr << " value =>" << value << endl;
 95         if(ptr == 0){
 96                 front(value);
 97                 return;
 98         }
 99         if(ptr == _at_end){
100                 _at_end = new NODE<unk>(value,ptr);
101                 return;
102         }
103         new NODE<unk>(value,ptr);
104 }
105
106 template<class unk>
107 inline void LIST<unk>::insert(unk value){
108         up_size();
109         if(_at_end == 0){
110                 front(value);
111                 return;
112         }
113         NODE<unk> * new_item = new NODE<unk>(value, _at_end);
114         _at_end = new_item;
115 }
116
117 template<class unk>
118 inline void LIST<unk>::up_size(){ ++_size; }
119
120 template<class unk>
121 inline void LIST<unk>::down_size(){ --_size; }
122
123
124 template<class unk>
125 inline void LIST<unk>::front(unk value){
126         NODE<unk> *tmp;
127         up_size();
128         if(_at_front){
129                 tmp = _at_front;
130                 _at_front = new NODE<unk>(value);
131                 _at_front->next(tmp);
132                 return;
133         }
134
135         _at_end = _at_front = new NODE<unk>(value);
136         return;
137 }
138
139
140
141 template<class unk>
142 void LIST<unk>::display(ostream &os){
143         NODE<unk> * tmp = _at_front;
144
145         if (tmp == 0){
146                 os << "No List" << endl;
147                 return;
148         }
149
150
151         //unk i =0;
152         while(tmp != _at_end){
153                 //cout << "Entering While Loop: "<< ++i << endl;
154                 os << tmp->value() << ":";
155                 tmp = tmp->next();
156         }
157
158         os << tmp->value() << endl;
159
160 }
161
162
163
164
165
166
167
168