need help understanding Linked lists

This is a discussion on need help understanding Linked lists within the C Programming forums, part of the General Programming Boards category; First of all ... shall i learn Linked lists and binary trees only and ignore learning stacks and queues??? because ...

  1. #1
    former member Brain Cell's Avatar
    Join Date
    Feb 2004
    Posts
    472

    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
    Last edited by Brain Cell; 07-16-2004 at 01:25 PM.
    My Tutorials :
    - Bad programming practices in : C
    - C\C++ Tips
    (constrcutive criticism is very welcome)


    - Brain Cell

  2. #2
    Helper
    Join Date
    Jun 2004
    Posts
    255
    Quote 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 Delahaye

    "C is a sharp tool"

  3. #3
    Compulsive Liar Robc's Avatar
    Join Date
    Jul 2004
    Posts
    149
    >This is hardly a C-question.
    And this isn't comp.lang.c. We do deviate from the language proper as long as it doesn't intrude on the topicality of the other forums.

    >shall i learn Linked lists and binary trees only and ignore learning stacks and queues???
    Linked lists and binary trees are implementations, stacks and queues are abstractions. For example, you can implement a stack or a queue with a linked list or a variation of a binary tree. It doesn't matter as long as the abstraction is maintained. That said, you should learn all of the classical data structures, it's worth the effort.

    >because the last two seem useless and unefficent...
    Judging from how often the two are used, I would say that you're wrong about them being useless. And for the problems that they're designed for, they're very efficient.

    >how the hell did the program break out of that 'while' loop
    Run the program in a debugger and watch how it works.

  4. #4
    former member Brain Cell's Avatar
    Join Date
    Feb 2004
    Posts
    472
    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
    My Tutorials :
    - Bad programming practices in : C
    - C\C++ Tips
    (constrcutive criticism is very welcome)


    - Brain Cell

  5. #5
    Helper
    Join Date
    Jun 2004
    Posts
    255
    Quote 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()).
    Emmanuel Delahaye

    "C is a sharp tool"

  6. #6
    Compulsive Liar Robc's Avatar
    Join Date
    Jul 2004
    Posts
    149
    >all i wanted is a bit of logical elaboration on the 'insert' function and the 'while' loop specifically
    Okay.
    Code:
    while ( currentPtr != NULL && value > currentPtr->data ) { 
      previousPtr = currentPtr;          /* walk to ...   */
      currentPtr = currentPtr->nextPtr;  /* ... next node */
    }
    The loop runs until the end of the list is found (currentPtr == NULL) or a node with a value greater than value is found (value > currentPtr->data). For each iteration of the loop, currentPtr is saved in previousPtr so that an insertion can be correctly performed. The idea is to insert before the end of the list or before the node that has a greater value. The only problem is how to insert at the front of the list. That's done by setting previousPtr to null originally. Then if the loop body is never reached, previousPtr will be null and you know to insert at the front of the list, like so:
    Code:
    if ( previousPtr == NULL ) { 
      newPtr->nextPtr = *sPtr;
      *sPtr = newPtr;
    }
    else { 
      previousPtr->nextPtr = newPtr;
      newPtr->nextPtr = currentPtr;
    }
    The first part of the conditional inserts at the front of the list and resets the head to account for the change. The second part inserts everywhere else in the list by linking the new node after previousPtr.

  7. #7
    former member Brain Cell's Avatar
    Join Date
    Feb 2004
    Posts
    472
    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
    My Tutorials :
    - Bad programming practices in : C
    - C\C++ Tips
    (constrcutive criticism is very welcome)


    - Brain Cell

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Understanding linked lists, structures, and pointers
    By yougene in forum C Programming
    Replies: 5
    Last Post: 07-13-2011, 09:13 PM
  2. Replies: 9
    Last Post: 01-03-2009, 03:48 PM
  3. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 05:32 PM
  4. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 09:57 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 07:25 PM

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