Need help with simple linked list

Hi, I'm trying to transform a double linked list into a simple linked list. For that I need to change how the functions work and I'm having trouble with Insert().

The problem is that I do not have access to pPrev pointer anymore but I still need to know where the previous node is.

So if anyone have any idea on how to do this, help would be appreciated.

Code:

---

ClIterator Insert(ClIterator p_position, const T& p_data)
                {
                if (++m_nbNode== 1)
                        {
                        m_pHead= m_pTail= new TypeNode(p_data, 0);
                        return ClIterator(m_pHead);
                        }

                TypeNode* pPosition= p_position.m_pNode;
                if (pPosition == 0)
                        {
                        m_pTail= new TypeNode(p_data, m_pTail, 0);
                        m_pTail->pPrev->pNext= m_pTail;
                        return ClIterator(m_pTail);
                        }

                if (pPosition == m_pHead)
                        {
                        m_pHead= new TypeNode(p_data, 0, m_pHead);
                        m_pHead->pNext->pPrev= m_pHead;
                        return ClIterator(m_pHead);
                        }
               
                TypeNode* p= new TypeNode(p_data, pPosition->pPrev, pPosition);
                p->pNext->pPrev= p->pPrev->pNext= p;
                return ClIterator(p);
                }

---

you don't need that prev pointer at all. Just keep track of head and tail as it does now. I didn't compile or test this, so use it at your own risk!

Code:

---

ClIterator Insert(ClIterator p_position, const T& p_data)
                {
                if (++m_nbNode== 1)
                        {
                        m_pHead= m_pTail= new TypeNode(p_data, 0);
                        return ClIterator(m_pHead);
                        }

                TypeNode* pPosition= p_position.m_pNode;
                if (pPosition == 0)
                        {
                          // add node to tail of linked list
                        TypeNode* pNewNode = new TypeNode(p_data, m_pTail, 0);
                        m_pTail->pNext= pNewNode;
                          m_pTail = pNewNode;
                        return ClIterator(m_pTail);
                        }

                if (pPosition == m_pHead)
                        {
                        // add node to head of linked list
                        TypeNode* pNewNode = new TypeNode(p_data, 0, m_pHead);
                        pNewNode->next = m_pHead;
                        m_pHead= pNewNode;
                        return ClIterator(m_pHead);
                        }
reach here

// I guess this is supposed to insert the new node just before the current position.
// The program will have to iterate through the list to find the insert position.
  TypeNode*p = m_pHead;
  while(p && p->next != pPosition)
          p = p->next;
                TypeNode* p= new TypeNode(p_data, p,pPosition);
                p->pNext->pPrev= p->pPrev->pNext= p;
                return ClIterator(p);
                }

---

Thanks for the help Ancient Dragon,
I managed to make it work, but it search the whole list until it find the position to insert the node...

Is there a faster way to find the position to insert the node ?

>> Is there a faster way to find the position to insert the node ?

Not normally -- and thats just one of the big advantages of doubly-linked lists.

Yes. Use another data structure. std::map would be rather useful, or you could use a hash table (also in the STL somewhere).

>> you could use a hash table (also in the STL somewhere)
Not yet- unordered_map and friends were added to std::tr1 (an almost but not-quite standard library). There are implementations of those available (see Boost for example). They won't actually be part of the real standard until the next one is approved.