Thread: need help understanding Linked lists

First of all ... shall i learn Linked lists and binary trees only and ignore learning stacks and queues??? because the last two seem useless and unefficent...

second... see this code , its a linked list program that align letters in alpabatic order regardless the order you insert them (don't panic i just need a little explanation on few lines) :

Code:

/* Operating and maintaining a list */
#include <stdio.h>
#include <stdlib.h>


struct listNode {   /* self-referential structure */
   char data;
   struct listNode *nextPtr;
   };

        typedef struct listNode ListNode;
        typedef ListNode *ListNodePtr;

        void insert( ListNodePtr *, char );
        char delete( ListNodePtr *, char );
        int isEmpty( ListNodePtr );
        void printList( ListNodePtr );
        void instructions( void );


int main()
{ 
   ListNodePtr startPtr = NULL;
   int choice;
   char item;

   instructions();  /* display the menu */
   printf( "? " );

   scanf( "%d", &choice );

   while ( choice != 3 ) { 

      switch ( choice ) { 
         case 1:
            printf( "Enter a character: " );
            scanf( "\n%c", &item );
            insert( &startPtr, item );
            printList( startPtr );
            break;
         case 2:
            if ( !isEmpty( startPtr ) ) { 
               printf( "Enter character to be deleted: " );
               scanf( "\n%c", &item );
               if ( delete( &startPtr, item ) ) { 
                  printf( "%c deleted.\n", item );
                  printList( startPtr );
               }
               else
                  printf( "%c not found.\n\n", item );
            }
            else
               printf( "List is empty.\n\n" );
            break;
         default:
            printf( "Invalid choice.\n\n" );
            instructions();
            break;
      }
      printf( "? " );
      scanf( "%d", &choice );
   }
   printf( "End of run.\n" );
   return 0;
}
 
void instructions( void )		/* Print the instructions */
{ 
   printf( "Enter your choice:\n"
          "   1 to insert an element into the list.\n"
          "   2 to delete an element from the list.\n"
          "   3 to end.\n" );
}

/* Insert a new value into the list in sorted order */

void insert( ListNodePtr *sPtr, char value )
{ 
   ListNodePtr newPtr, previousPtr, currentPtr;

   newPtr = malloc( sizeof( ListNode ) );

   if ( newPtr != NULL ) {     /* is space available */
      newPtr->data = value;
      newPtr->nextPtr = NULL;

      previousPtr = NULL;
      currentPtr = *sPtr;

      while ( currentPtr != NULL && value > currentPtr->data ) { 
         previousPtr = currentPtr;          /* walk to ...   */
         currentPtr = currentPtr->nextPtr;  /* ... next node */
      }

      if ( previousPtr == NULL ) { 
         newPtr->nextPtr = *sPtr;
         *sPtr = newPtr;
      }
      else { 
         previousPtr->nextPtr = newPtr;
         newPtr->nextPtr = currentPtr;
      }
   }
   else
      printf( "%c not inserted. No memory available.\n", value );
}
 
char delete( ListNodePtr *sPtr, char value ) /* Delete a list element */
{ 
   ListNodePtr previousPtr, currentPtr, tempPtr;
   if ( value == ( *sPtr )->data ) { 
      tempPtr = *sPtr;
      *sPtr = ( *sPtr )->nextPtr;  /* de-thread the node */
      free( tempPtr );             /* free the de-threaded node */
      return value;
   }
   else { 
      previousPtr = *sPtr;
      currentPtr = ( *sPtr )->nextPtr;
      while ( currentPtr != NULL && currentPtr->data != value ) { 
         previousPtr = currentPtr;          /* walk to ...   */
         currentPtr = currentPtr->nextPtr;  /* ... next node */
      }
      if ( currentPtr != NULL ) { 
         tempPtr = currentPtr;
         previousPtr->nextPtr = currentPtr->nextPtr;
         free( tempPtr );
         return value;
      }                                                        
   }
   return '\0';
}

int isEmpty( ListNodePtr sPtr )   /* Return 1 if the list is empty, 0 otherwise */
{ 
   return sPtr == NULL;
}
void printList( ListNodePtr currentPtr )	/* Print the list */
{ 
   if ( currentPtr == NULL )
      printf( "List is empty.\n\n" );
   else { 
      printf( "The list is:\n" );
      while ( currentPtr != NULL ) { 
         printf( "%c --> ", currentPtr->data );
         currentPtr = currentPtr->nextPtr;
      }
      printf( "NULL\n\n" );
   }
}

As you can see , its pretty easy to understand BUT , when it comes to "insert" function things confuse me a bit.

Lets focus on the "insert" function. Assuming that the list is empty now , when i insert 'a' in the list , the function will allocate space for a new structure , set previous pointer to NULL and current pointer to the start pointer '*sptr' wich is NULL now.

In the while loop current pointer must point to NULL and the value must be smaller than the value in the structure in order to break the loop right???

Lets assume that we filled the list with some letters and it looked like this :

a -> b -> d -> e -> NULL


now if i insert the letter 'c' , how the hell did the program break out of that 'while' loop in function 'insert' since it requires the current pointer to point to NULL and a smaller value than the one in the structure??? i imagine it looping infinitly because when 'currentPtr' reaches 'a' it'll point to 'b' not NULL , but it doesn't because the program works well and i have no idea how it happened

Originally Posted by Brain Cell

First of all ... shall i learn Linked lists and binary trees only and ignore learning stacks and queues??? because the last two seem useless and unefficent...

This is hardly a C-question. If you insist, stacks and queues are useful in certain situations, like lists and trees are.

<...>
now if i insert the letter 'c' , how the hell did the program break out of that 'while' loop in function 'insert' since it requires the current pointer to point to NULL??? i imagine it looping infinitly because when 'currentPtr' reaches 'a' it'll point to 'b' not NULL , but it doesn't because the program works well and i have no idea how it happened

The secret is here:

Code:

      while ( currentPtr != NULL && value > currentPtr->data ) { 
         previousPtr = currentPtr;          /* walk to ...   */
         currentPtr = currentPtr->nextPtr;  /* ... next node */
      }

Read more carefully the second part of the while expression. The && makes it break on 2 possible conditions.

Emmanuel Delaha :
sorry i forgot to mention the other condition . I still don't understand it though....

Robc :
sorry but i don't know how to do that.

all i wanted is a bit of logical elaboration on the 'insert' function and the 'while' loop specifically

Originally Posted by Brain Cell

sorry i forgot to mention the other condition . I still don't understand it though....

The loop stops when the "value > currentPtr->data" expression becomes false. Then the newly allocated node is inserted into the list at the right place.

For a dynamic view of the behaviour, should I suggest to add some smart traces (printf()).

oh now i get it !! sorry but i've been away from C for a long time. Its funny how you get into complicated stuff and forget how the 'while' loop actually work

the statement in the 'while' loop should be 'true' so the program can skip\break it. I forgot that and i thought it should be 'false' (stupid me )...



thanks for the help anyway Emma and robc