Thread: Need help with simple linked list

  1. #1
    Registered User
    Join Date
    Sep 2006
    Posts
    2

    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);
    		}

  2. #2
    Registered User
    Join Date
    Aug 2005
    Posts
    1,267
    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);
    		}
    Last edited by Ancient Dragon; 09-12-2006 at 09:08 AM.

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    2
    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 ?

  4. #4
    Registered User
    Join Date
    Aug 2005
    Posts
    1,267
    >> 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.

  5. #5
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    Yes. Use another data structure. std::map would be rather useful, or you could use a hash table (also in the STL somewhere).
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> 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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list question
    By mikeman in forum C Programming
    Replies: 1
    Last Post: 11-30-2008, 01:56 PM
  2. Sorting linked list please help with CODE
    By scarlet00014 in forum C Programming
    Replies: 3
    Last Post: 09-27-2008, 11:24 PM
  3. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 01:21 PM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM