Lista doblemente enlazada

[latindeveloper]

Amigos.

A quienes esten interesados en resolver problemas de la ACM (http://acm.uva.es/problemset/ ), quiero compartir con ustedes una clase que escribí para resolver uno de esos problemas, esta clase tambien les servirá para muchos otros.

Se trata de una lista doblemente enlazada circular, la implementé justo para estos propositos. Con esta clase he podido resolver varios problemas como el 330.

No dejen de programar, cualquier duda acerca del funcionamiento de la clase solo escriban.

La clase todavia esta en pañales pero es util, Se aceptan sugerencias.

Enjoy!

Código: Seleccionar todo


/* CLinkedList, A circular double-linked list.
*  Version: 0.3
*  Author: Ivan Cachicatari ivancp@latindevelopers.com
*  Last Update: 03:40am 08-10-2006
*
* Please use and enjoy. Please let me know of any bugs/mods/improvements
* that you have found/implemented and I will fix/incorporate
* them into this file.
*/

template <typename>
class CLinkedList
{
  public:

   struct NODE
   {
      T *m_data;     
      NODE *pNext;
      NODE *pPrev;
      bool bIsHead;
      NODE(T *data) : m_data(data)
      {
         bIsHead = false;
         pNext = pPrev = this;         
      }
      NODE* next()
      {
         if(pNext->bIsHead)
            return NULL;
         return pNext;
      }
      void insertAfter(NODE *&prevNode)
      {
         remove();

         pPrev = prevNode;
         pNext = prevNode->pNext;
         prevNode->pNext->pPrev= this;
         prevNode->pNext= this;
      }

      void insertBefore(NODE *&nextNode)
      {
         remove();

         pPrev = nextNode->pPrev;
         pNext = nextNode;
         nextNode->pPrev->pNext = this;
         nextNode->pPrev= this;
         
      }

      void remove()
      {
         pNext ->pPrev = pPrev;
         pPrev ->pNext = pNext;
         pPrev = pNext = this;         
      }
   };

   int m_nCount;
   NODE *m_pRoot;
   int (*m_lpfnCompare)(const T *a,const T *b);

   // Constructor, input: a compare function

   CLinkedList(int (*lpfnCompare)(const T *a,const T *b))
   {
      m_pRoot = NULL;
      m_lpfnCompare = lpfnCompare;
      m_nCount = 0;
   }

   ~CLinkedList()
   {
      Empty();
   }

   // Inserts a unique sorted item, returns false if exists.
   bool Insert(T *&newValue, bool bUnique = false)
   {
      if(!m_pRoot)
      {
         m_pRoot = new NODE(newValue);
         m_pRoot->bIsHead = true;
         m_nCount++;
         //cout<<" + "<<m_pRoot>m_data->name<<"            [as root]"<<endl>m_data);
         
         // 1 newValue > pTmp->m_data
         // -1 newValue <pTmp>m_data

         if(bUnique && res == 0 ) // equal
            return false;
         if(res < 0) // newValue <pTmp>m_data
         {
            newNode->insertBefore(pTmp);

            if (pTmp == m_pRoot)
            {
               m_pRoot->bIsHead = false;
               newNode->bIsHead = true;
               m_pRoot = newNode;
            }
            m_nCount++;

            //cout<<" + "<<newNode>m_data->name<<"            ["<<i<<"]"<<endl>next();
      }
      m_nCount++;
      newNode->insertBefore(m_pRoot);
      //cout<<" + "<<newNode>m_data->name<<"["<<i<<"]"<<endl>pNext;
         delete toDelete->m_data;
         delete toDelete;
         toDelete = NULL;         
      }
      m_nCount = 0;
   }

   void Delete(T*& item)
   {
      NODE *pTmp = m_pRoot;

      if(m_nCount == 1)
      {
         delete m_pRoot->m_data;
         delete m_pRoot;
         m_pRoot = NULL;
         m_nCount--;
         return;
      }

      while(pTmp)
      {
         if(pTmp->m_data == item)
         {
            NODE *&toDelete = pTmp;

            if(toDelete == m_pRoot)
            {
               NODE *&pTmp2 = m_pRoot->pNext;

               m_pRoot->pPrev->pNext = m_pRoot->pNext;
               m_pRoot->pNext->pPrev = m_pRoot->pPrev;
               m_pRoot = m_pRoot->pNext;
               m_pRoot->bIsHead = true;

            }
            else
            {
               (NODE *&)pTmp->pPrev->pNext = toDelete->pNext;
               (NODE *&)pTmp->pNext->pPrev = toDelete->pPrev;
            }

            delete toDelete->m_data;
            delete toDelete;
            toDelete = NULL;
            m_nCount--;
            return;
         }
         pTmp = pTmp->next();
      }     
   }
   void Print()
   {
      NODE *pTmp = m_pRoot;
     
      if (!m_pRoot)
      {
         cout<<"\nEmpty\n";
         return;
      }
      while(true)
      {
         cout<<pTmp>m_data->name<<pTmp>bIsHead?"[root]":"")<<endl>pNext;
         if(pTmp == m_pRoot)
            break;
      }
   }

   T*& operator[](int nIndex) const
   {
      NODE *pTmp = m_pRoot;
      for(int i = 0 ; i <m_nCount>= nIndex || !pTmp->next())
            return pTmp->m_data;
         pTmp = pTmp->next();
      }
      return pTmp->m_data;
   }   
};

Nota:
El codigo es resultado de sugerencias y experiencias propias de varios años. Tuve que reescribir la clase.


Ejemplo de utilizacion:

Código: Seleccionar todo

struct ITEM
{
   char name[10];
   double cost;
   double price;
   long onHand;
   bool bSold;
   ITEM():onHand(0),bSold(false){}
};

inline int fnITEMCompare( const ITEM *a, const ITEM *b)
{
   return strcmp(a->name,b->name);
}

int main(int argc, char* argv[])
{
   CLinkedList<ITEM> items(fnITEMCompare);

   ITEM *item = new ITEM();
   strcpy(item->name,"Primer Item");
   item->cost = 45;
   item->price = 30.2;
   items.Insert(item,true);

   ITEM *item2 = new ITEM();
   strcpy(item2->name,"Segundo Item");
   item2->cost = 65;
   item2->price = 50.2;
   items.Insert(item2,true);

   items.Print();
   return 0;
}