Thread: 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

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.

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.

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.

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.