#include <iostream> 

using namespace std; 

struct list 
{ 
       int key; 
       list* next; 
}; 

class List 
{ 
      public: 
             List(); 
             ~List(); 
             bool Add(int nValue, int nPosition, int nValue2, bool lgAfter); 
             bool Delete(int nPosition, int nValue); 
             void Show(); 
             void Sort(); 
             void Swap(int First, int Second); 
             int Size() { return nNumOfElem; } 
      private: 
             list* lHead, *preHead; 
             int nNumOfElem; 
             void Destroy(list*); 
             void Swap(list*,list*); 
}; 

List :: List() 
{ 
     preHead = new list; 
     preHead -> next = NULL; 
     nNumOfElem = 0; 
     lHead = NULL; 
} 

List :: ~List() 
{ 
     Destroy(lHead); 
} 

void List :: Destroy(list* lTemp) 
{ 
     if ( lTemp ) 
     { 
          Destroy(lTemp -> next); 
          delete lTemp; 
     } 
} 

bool List :: Add (int nValue, int nPos, int nValue2 = 0, bool lgAfter = false) 
{ 
     list *lCur = preHead; 
     if ( nPos > 0 ) 
     { 
          if (nPos > nNumOfElem + 1 ) 
                 return false; 

          for ( int i = 1; i < nPos; i++ ) 
          { 
              lCur = lCur -> next; 
          } 

          if ( lCur -> next ) 
          { 
               list* temp = new list; 
               temp -> next = lCur -> next; 
               temp -> key = nValue; 
               lCur -> next = temp; 
               lCur = lCur -> next; 
          } 
          else 
          { 
              lCur -> next = new list; 
              lCur = lCur -> next; 
              lCur -> next = NULL; 
              lCur -> key = nValue; 
          } 
          if ( nPos == 1 ) 
                 lHead = lCur; 
          nNumOfElem++; 
          return true; 
      } 
      else 
      { 
          if ( lHead ) 
          { 
               int nPositi 
              while ( lCur ) 
              { 
                    if ( lCur -> key == nValue2 ) 
                       break; 
                    lCur = lCur -> next; 
                    nPosition++; 
              } 

              if ( !lCur ) 
                 return false; 

              if ( lgAfter ) 
                 nPosition++; 

              Add(nValue,nPosition,0,false); 
          } 
          else 
          { 
              system&#40;"pause"&#41;; 
              return false; 
          } 
      } 
      return true; 
} 

bool List :: Delete(int nPos, int nValue = 0) 
{ 
     list* lCur = preHead; 
     if ( nPos > 0 && nPos <= nNumOfElem ) 
     { 
          for (int i = 1; i < nPos; i++) 
          { 
              lCur = lCur -> next; 
          } 
          if (lCur == preHead) 
             lHead = lHead -> next; 

          list* lTemp = lCur -> next; 
          lCur -> next = lTemp -> next; 

          delete lTemp; 
          nNumOfElem--; 
     } 
     else 
     { 
          int nPositi 
         while ( lCur ) 
         { 
               if ( lCur != preHead && lCur -> key == nValue ) 
                  break; 
               lCur = lCur -> next; 
               nPosition++; 
         } 

         if ( !lCur ) 
            return false; 

         Delete(nPosition,0); 
     } 
     return true; 
} 

void List :: Show() 
{ 
     cout << "List: " << endl; 
     if ( lHead ) 
     { 
        list *lCur = lHead; 
        while (lCur) 
        { 
              cout << lCur -> key << " "; 
              lCur = lCur -> next; 
        } 
     } 
     else 
     { 
         cout << "List is empty"; 
     } 
     cout << endl; 
} 

void List :: Swap(list* lFirst, list* lSecond) 
{ 
     if (lFirst == preHead) 
        lHead = lSecond -> next; 

     list* lTemp = lFirst -> next; 
     lFirst -> next = lSecond -> next; 
     lSecond -> next = lTemp; 

     lTemp = lSecond -> next -> next; 
     lSecond -> next -> next = lFirst -> next -> next; 
     lFirst -> next -> next = lTemp; 
} 

void List :: Swap(int i, int j) 
{ 
     if ( i > j ) 
     { 
          i += j; j = i - j; i -= j; 
     } 
     if (j>nNumOfElem) return; 
     list* lFirst, *lCur = preHead; 
     for ( int k = 1; k < j ; k++ , lCur = lCur -> next ) 
     { 
         if ( k == i ) 
            lFirst = lCur; 
     } 
     Swap(lFirst,lCur); 
} 

void List :: Sort() 
{ 
     list* i = preHead;      list* j; 
     if (!lHead) return; 
     while (i -> next -> next) 
     { 
         j = i-> next; 
         while ( j -> next ) 
             if (i -> next -> key > j -> next -> key) 
                Swap(i,j); 
             else 
                j = j -> next; 
         i = i -> next; 
     } 
}