1 //list -- simple Double Linked List, by tsaiwn@csie.nctu.edu.tw
  2 #ifndef __MYLIST_
  3 #define __MYLIST_
  4 class _LP {   // Linked pointer
  5   public:  _LP* prev;  _LP* next;   // left = previous, right
  6 };
  7 template <class T>
  8 class _LKNode : public _LP { public:  T  data;  };
  9 
 10 template <class T, class TRef, class TPtr>
 11 struct myListIterator {    // public:
 12   _LP* myNode;
 13   myListIterator(_LKNode<T> * it) : myNode(it) {}
 14   myListIterator( ) { myNode = 0;}
 15   void _M_incr() { myNode = myNode->next; }
 16   void _M_decr() { myNode = myNode->prev; }
 17   myListIterator<T, TRef, TPtr> & operator++( ) {   // for ++it;
 18     this->_M_incr( );  return *this;
 19   }
 20   myListIterator<T, TRef, TPtr> & operator++(int) {  // for it++;
 21     myListIterator<T, TRef, TPtr> tmp= *this; 
 22     this->_M_incr(); return tmp;
 23   }
 24   myListIterator<T, TRef, TPtr> & operator--( ) {  // for  --it;
 25     this->_M_decr( );  return *this;
 26   }
 27   myListIterator<T, TRef, TPtr> & operator--(int) {  // for it--;
 28     myListIterator<T, TRef, TPtr> tmp= *this; 
 29     this->_M_decr(); return tmp;
 30   }
 31   bool operator==(const myListIterator<T, TRef, TPtr> & bp) const {
 32     return myNode == bp.myNode;
 33   }
 34   bool operator!=(const myListIterator<T, TRef, TPtr> & bp) const {
 35     return myNode != bp.myNode;
 36   }// operator!=
 37   TRef operator*() const { return ((_LKNode<T> *) myNode)->data; }
 38 }; // struct myListIterator
 39 ////// ////// //////    ////// ////// //////
 40 template <class T> 
 41 class list {    // Linked List
 42    _LKNode<T> * head;   // the head Node    *********************
 43   public:
 44     typedef myListIterator<T, T&, T*>  iterator;
 45     list( ){head=new _LKNode<T>( ); head->next = head->prev = head; }
 46     int size( ) const {  int ans = 0;
 47        for(iterator i=begin(); i != end(); ++i) ++ans; return ans;
 48     }//size(
 49   ////////////// === there is NO capacity( ) for list
 50     iterator begin( ) const { return (_LKNode<T> *)(head->next);}
 51     iterator end( ) { return head; }
 52     iterator end( ) const { return head; }
 53     T& front( ) const { return *begin( ); }
 54     T& back( ) const {  return *(--end() ); }
 55     void push_front(const T& x) { insert(begin(), x); }
 56     void push_back(const T& x) { insert(end(), x); }
 57     iterator insert(iterator it, const T& x ) { // study these codes
 58        _LKNode<T> * tmp = new _LKNode<T>( );
 59        tmp->data = x;
 60        tmp->next = it.myNode;       // do "insert before"
 61        tmp->prev = it.myNode->prev;
 62        it.myNode->prev->next = tmp;
 63        it.myNode->prev = tmp;
 64        return tmp;
 65     }// insert(
 66     iterator insert(int n, const T& x ) { // add to n-th position
 67         iterator it = begin( );    // this is 0-th position
 68         for(int k=0; k < n; ++k) ++it;  return insert(it, x);
 69     }
 70     void sort( ) {  // not implement yet 
 71     }// sort(
 72 };  // class list
 73 #endif