doubly linked list problem

This is a discussion on doubly linked list problem within the C Programming forums, part of the General Programming Boards category; Hi, I am experiencing a runtime error with a function of my program that tries to output a doubly linked ...

  1. #1
    Registered User
    Join Date
    Apr 2003
    Posts
    17

    Question doubly linked list problem

    Hi, I am experiencing a runtime error with a function of my program that tries to output a doubly linked list backwards. I am not sure where the problem originates, but the debug shows a runtime error at the Retreat() function. I suspect I might not have pointers correctly set up in my Insert() function.

    The code below is a global function in main().
    Code:
    void
    PrintBackwards( const List L )
    {
        Position P = Tail(L);
    	 
        if( IsEmpty( L ) )
            printf( "Empty list\n" );
        else
        {
            do
            {
                P = Retreat( P );
                printf( "%d ", Retrieve( P ) );
            } while( !IsFirst( P, L ) );
            printf( "\n" );
        }
    }
    The next code is the structure itself and the functions used in PrintBackwards() function. They are in a separate functions file (list.c).

    Code:
    struct Node
    {
       ElementType Element;
       Position    Next;
       Position    Prev;
    };
    
    // Inserts an integer after Position P
    void Insert( ElementType X, Position P )
    {
       Position NewCell;
    
       NewCell = (Position) malloc( sizeof( struct Node) ); // create NewCell
       if( NewCell == NULL )
         FatalError( "Out of space!!!" );
    
       NewCell->Element = X; // assign a value to the NewCell
    
       /* Assigning and Reassigning the Pointers After Adding a NewCell */			
    				
       NewCell->Prev = P; // assign the NewCell's Prev pointer to the left adjacent node
       NewCell->Next = P->Next; // reassign the NewCell's Next pointer to the right adjacent node
    
       P->Next = NewCell;       // reassign left adjacent next ptr to NewCell
    				
    // condition needed since a NULL cannot point back to anything
      if (NewCell->Next != NULL) {
    					
      NewCell->Next->Prev = NewCell; 
      // assign right adjacent previous ptr to NewCell
      // NewCell->Next->Next may point to other numbers in the list
    														
       }
    }
    
    Position Tail( List L )
    {
       while (L != NULL) { // traverse to the end of the list
        L = L->Next;
    				}
        return L;
    }
    
    // Return true if L is empty
    int IsEmpty( List L ) {
       return L->Next == NULL;
    }
    
    Position Retreat( Position P ){
       return P->Prev;
    }
    
    ElementType Retrieve( Position P ) {
       return P->Element;
    }
    
    // Return true if P is the first position in list L
    int IsFirst( Position P, List L ) {
       return P->Prev == NULL;
    }

    I also have a PrintForwards() function, which works fine. You can download the entire code if the above info. does not help.

    1) list.h is the header file for function
    2) list.c has all the functions and the structure itself
    3) lab4.c has the main() function including PrintForwards() function

    Thank you very much for your help in advance.

    Yev
    Attached Files Attached Files
    Last edited by YevGenius; 05-02-2004 at 04:13 PM. Reason: Tail Function was not on board

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    Position Tail( List L )
    {
       while (L != NULL) { // traverse to the end of the list
        L = L->Next;
    				}
        return L;
    }
    You realize this will return NULL, right? Walk through it:
    Code:
    node1->node2->NULL
    
    Tail( node1 )
    {
        node1 != NULL
            next node
        node2 != NULL
            next node
        NULL == NULL
            break from loop
        return NULL;
    }
    And without reading more, that'll probably turn out to be your problem. You could always just keep a pointer to the end of your list, and then make a function walk through your previous pointer the same way you do your next.

    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    essence of digital xddxogm3's Avatar
    Join Date
    Sep 2003
    Posts
    589
    i haven't had time to read through the code, but i agree with quzah.
    my double linked list had node, prev, next, head, tail. makes it easy to print with out the need to traverse the list. if you are only using integers, can you write this with a circular array?

    here is a quick write of some code, i do not have a compiler to test it.
    Code:
    void Backwards( Position P )
    {
      printf("%i",P->data);
     
      if(P->previous!=NULL)
      {	 
    	P=P->previous
    	Backwards( Position P);
      }
    }
    Please someone check my recursion, I think it works. I can see it in my head.
    But recursion is always screwy. this requires that you have traversed to the end or have an end pointer.
    Last edited by xviddivxoggmp3; 05-02-2004 at 08:59 PM.
    "Hence to fight and conquer in all your battles is not supreme excellence;
    supreme excellence consists in breaking the enemy's resistance without fighting."
    Art of War Sun Tzu

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You can do it one better:
    Code:
    void Backwards( Position P )
    {
        if( P )
        {
            printf("%d", P->data );
            Backwards( P->prev );
        }
    }
    You don't need to assign P a new value. Anyway, the recrusive method only works on non-circular lists. If your list is circular, you'll have some problems. However, with a simple node pointer, you can just use a loop. Or if you feel like reusing the pointer passed to the argument, you don't even need a temporary one.

    Quzah.
    Hope is the first step on the road to disappointment.

  5. #5
    essence of digital xddxogm3's Avatar
    Join Date
    Sep 2003
    Posts
    589
    showed up once again.

    my code was in regards to the list type, and not the array type.

    that would be funny to see someone try to use it on an array.

    the way quzah wrote it is very clean.
    "Hence to fight and conquer in all your battles is not supreme excellence;
    supreme excellence consists in breaking the enemy's resistance without fighting."
    Art of War Sun Tzu

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting linked list please help with CODE
    By scarlet00014 in forum C Programming
    Replies: 3
    Last Post: 09-28-2008, 12:24 AM
  2. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 06:37 PM
  3. Doubly linked list woes
    By foniks munkee in forum C Programming
    Replies: 3
    Last Post: 03-06-2002, 03:04 AM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21