Thread: question about a working linked list

  1. #16
    Registered User
    Join Date
    Apr 2004
    Posts
    17

    check this out

    Ok, here is my code, I added a function to add a node to the beginning, the middle or the end of the list:
    Code:
    #include <iostream>
    using namespace std;
    
    struct node {
      int x;
      node* next;
    };
    
    void createList( node* root, int size ){  //Creates a list of any size
    
      for(int i = 0; i < size; i++){
        root->x = i + 1;
        root->next = new node;  //Creates a new node at the end of the list
        root = root->next;  //Moves to that node
        root->next = 0;  //Sets the end of the list at the current node
      }  //for
    
    }
    
    void cleanList( node* root ){  //Clears the list from memory
    
      if( root != 0 ) {
    
        while( root->next != 0 ){
          node* temp = root;  //Assigns temp to be the current head
          root = root->next;  //Moves the head to the next element
          delete temp;  //Deletes the temporary head
        }  //while
    
      }  //if
    
    }
    
    void displayList( node* walker ){  //Displays all the elments of the list
    
      while(walker->next != 0 ){
        cout << walker->x << endl;
        walker = walker->next;  //Moves to the next element
      }  //while
    
    }
    
    node* addToList( node* head, int value ){  //Adds a new node to the 
                                               // beginning, the middle or the end
                                               // of the list
    
      node* search_ptr = head;  //search_ptr points to the first node
    
      node* newNode = new node;  //Creates new node
    
    //If the new value is less than or equal, or greater than the value in the first
    // node, then:
      if( value <= search_ptr->x ) {  
          newNode->x = value;           //Inserts this new value at the first node
          newNode->next = head;         // and makes the next pointer in newNode
                                        // to point to the beginning of the list
      } else {
    
        node* past_node;  //This node stores the last node accessed
    
        while( search_ptr->next != 0 ){  //While is not the end of the list
    
          past_node = search_ptr;  //past_node equals the current node
          search_ptr = search_ptr->next;  //Moves to the next node
    
    //If the value is less than or equal to the next value in the node, then
    // inserts the new node in the middle of the list
          if( value <= search_ptr->x ){  
    
            past_node->next = newNode;   //Last element in the node points to the
                                         // new node
            newNode->x = value;          //The new node gets the value
            newNode->next = search_ptr;  //The next pointer of the new node points
                                         // to the next element in the list
    
            return head;  //Returns the whole list
          } //if
    
        }  //while
    
    //If we get to the last node in the list and the results from the comparissons
    // were all false, then it means that this value must be placed at the end of
    // the list
        if( head->next == 0 ){
          newNode->x = value;           //Inserts this new value at the first node
          newNode->next = head;         // and makes the next pointer in newNode
        } else {
        newNode->x = value;  //The new node gets the value
        search_ptr->next = newNode;  //Search_ptr is now the last element in the
                                     // in the list, so we make the next pointer
                                     // of the last element to point to the newNode
        newNode->next = 0;           // and newNode becomes the last element in the
                                     // list
    
        return head;  //Returns the whole list
        }
      }
    
      return newNode;  //Returns the address of the new first node
    }
    
    int main(){
      node* head;  //First node in the list
      
      head = new node;  //Creates the first element
      
      createList( head, 1 );
    
      head = addToList( head, 10 );
      head = addToList( head, 6 );
    
      displayList( head );
    
      cleanList( head );
      
      cin.get();
    
    }
    So far so good, but I have a problem....if I haven't created the list, I want that addToList() to create it...but it doesn't work...if you want to know what I'm talking about try removing the line that says createList( head, 1 ); like this:

    Code:
    int main(){
      node* head;  //First node in the list
      
      head = new node;  //Creates the first element
      
      head = addToList( head, 10 );
      head = addToList( head, 6 );
    
      displayList( head );
    
      cleanList( head );
      
      cin.get();
    
    }
    What's wrong?

  2. #17
    Registered User
    Join Date
    Feb 2006
    Posts
    312
    In your main function, you are creating a "dummy" new node, although the node isn't initialised, so when addToList() attempts to dereference the dummy node, your program invokes undefined behaviour (That's bad - it means anything can happen).

    You should make sure that the new dummy node is initialised, assign its next pointer a value of NULL. You should assign a default value to the data member x (maybe 0).

    Code:
    int main(){
      node* head;  //First node in the list
      
      head = new node;  //Creates the first element
      head->next = NULL;
      head->x = 0;
    
    //  Commenting out your createList call
    //  createList( head, 1 );
    
      head = addToList( head, 10 );
      head = addToList( head, 6 );
    
      displayList( head );
    
      cleanList( head );
      
      cin.get();
    
    }
    Making these changes to your main() worked for me, although there might still be other potential bugs in your code..
    Last edited by Bench82; 09-04-2006 at 04:50 PM.

  3. #18
    Registered User
    Join Date
    Feb 2006
    Posts
    312
    Take a look at this..
    Code:
    void displayList( node* walker ){  //Displays all the elments of the list
    
      while(walker->next != 0 ){ //uh-oh, what if walker is NULL?
        cout << walker->x << endl;
        walker = walker->next;  //Moves to the next element
      }  //while
    
    }
    I would do it like this instead..
    Code:
    void displayList( node* walker ){  //Displays all the elments of the list
    
      while(walker != 0 ){ // There, that's much safer!
        cout << walker->x << endl;
        walker = walker->next;  //Moves to the next element
      }  //while
    
    }
    -------------------------------------

    (edit) You've done it here, too, although your if statement actually protects you, so it's ok.
    Code:
    void cleanList( node* root ){  //Clears the list from memory
    
      if( root != 0 ) { // This isn't necessary, if you change the while condition.
    
        while( root->next != 0 ){
          node* temp = root;  //Assigns temp to be the current head
          root = root->next;  //Moves the head to the next element
          delete temp;  //Deletes the temporary head
        }  //while
    
      }  //if
    
    }
    Last edited by Bench82; 09-04-2006 at 05:02 PM.

  4. #19
    Registered User
    Join Date
    Apr 2004
    Posts
    17
    Quote Originally Posted by Bench82
    Take a look at this..
    Code:
    void displayList( node* walker ){  //Displays all the elments of the list
    
      while(walker->next != 0 ){ //uh-oh, what if walker is NULL?
        cout << walker->x << endl;
        walker = walker->next;  //Moves to the next element
      }  //while
    
    }
    I would do it like this instead..
    Code:
    void displayList( node* walker ){  //Displays all the elments of the list
    
      while(walker != 0 ){ // There, that's much safer!
        cout << walker->x << endl;
        walker = walker->next;  //Moves to the next element
      }  //while
    
    }
    -------------------------------------

    (edit) You've done it here, too, although your if statement actually protects you, so it's ok.
    Code:
    void cleanList( node* root ){  //Clears the list from memory
    
      if( root != 0 ) { // This isn't necessary, if you change the while condition.
    
        while( root->next != 0 ){
          node* temp = root;  //Assigns temp to be the current head
          root = root->next;  //Moves the head to the next element
          delete temp;  //Deletes the temporary head
        }  //while
    
      }  //if
    
    }
    Hey there dude...let's say that I have the list created...the I call displayList(), the while condition says, I think, take this more as a question, than some kind of offense :
    "while the pointer following the current node is not empty, then do this, otherwise, skip this", am I right?

    So, if I change the condition to:
    Code:
    while( walker != 0 )
    then it will show an extra element...one that I'm not interested in hehehehe....

    So I put an
    Code:
    if( walker != 0 )
    before the while...I know you told me that it is unnecessary, but I don't want the extra value

  5. #20
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    Quote Originally Posted by cold_dog
    Hey there dude...let's say that I have the list created...the I call displayList(), the while condition says, I think, take this more as a question, than some kind of offense :
    "while the pointer following the current node is not empty, then do this, otherwise, skip this", am I right?
    Yeah... but that also means you're skipping the last node in your list, right?

    E.g. if you have:

    [Node 1] -> [Node 2] -> [Node 3] -> NULL

    then you're skipping Node 3 when it's a perfectly cromulant node. Your code would only iterate from Node 1 to Node 2.

    Or are you keeping a blank node at the end of the whole shebang for some reason?
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

  6. #21
    Registered User
    Join Date
    Feb 2006
    Posts
    312
    Quote Originally Posted by cold_dog
    "while the pointer following the current node is not empty, then do this, otherwise, skip this", am I right?
    Correct

    So, if I change the condition to:
    Code:
    while( walker != 0 )
    then it will show an extra element...one that I'm not interested in hehehehe....
    Right - that's because at the very start of your program (in main() ) you've created a new node (which you're not interested in). A better idea would be to remove this 'dummy' node completely, and just use a NULL pointer.

    Of course, you've designed your program around that 'dummy' node, so you would need to change your functions to be able to handle a NULL pointer... or, better still, alter your createList() function so that it makes no assumptions about the state of the head. ie,
    Code:
    node* add_a_node_to_the_front(node* head, int value)
    {
        node* newnode = new node; // Immediately we have a node to work on, we don't care whether head is NULL or not
        newnode->next = head; // the only use of head in this function is to give something for the new node to point to.
        newnode->x = value;
        return newnode;
    }
    Code:
    int main()
    {
        node* head = NULL;  // Don't create a node here, because that's just holding unwanted data
        for(int i=0; i!=10; ++i)
            head=add_a_node_to_the_front(head, i);
        // ...
    }
    Of course, if you want to insert a node somewhere other than the front, then you will need to do something with head, but either way, you must always check whether a pointer is NULL before doing anything to it, especially before doing anything involving the -> operator. (There aren't many "always" rules in programming, but that is one of them )


    So I put an
    Code:
    if( walker != 0 )
    before the while...I know you told me that it is unnecessary, but I don't want the extra value
    No, that was in a different function (your cleanList() function), where you had an if statement before your while loop. its that if statement which would be superfluous, if you changed the while condition.
    Last edited by Bench82; 09-05-2006 at 03:04 AM.

  7. #22
    Registered User
    Join Date
    Feb 2006
    Posts
    312
    Additional: There are logic flaws in your addToList() function (although its somewhat difficult to trace)

    One thing i've noticed though, from your comments, your new node must always get the value which you pass to addToList() - the point of a linked list is that you can insert a new node at any part of the list, including, the front, the end, or somewhere in the middle. you will never need modify the data inside the existing nodes. I believe this is where you could be going wrong.

    i'd suggest making seperate find functions, instead of embedding it all into one long function call (long functions are really difficult to trace bugs at the best of times).

    The functions could find the nodes in your list which would logically precede and follow your new node respectively. (That is, if either such nodes exist, otherwise the functions would return NULL).

    This would make it really easy to connect your new nodes to any part of the list.

    quick example:
    Code:
    node* find_insert_point(node* head, const int i)
    {
        if (head == NULL)         //
            return head;          //  Do Nothing!
        if (head->x > i)          //  List head is insert point.
            return head;          //
    
        node* walker=head;
        while( (walker!=NULL) && (walker->x < i) )
            walker=walker->next;
        return walker;
    }
    Note that this function only works properly if your list is already in order.
    Last edited by Bench82; 09-05-2006 at 06:22 AM.

  8. #23
    Registered User
    Join Date
    Apr 2004
    Posts
    17

    Thanks a lot man

    Thanks for taking your time to respond my questions...the problem is that I haven't found enoguh information about this linked list thing, so I'm kind of experimenting with it blindly In the book I'm reading barely mentions linked list...the book only shows an example with one, but doesn't bother in explaining about it....and I have read about linked list in a quick pascal book hehehe

    That's why I keep asking so much about this anyway...thanks a lot

  9. #24
    Registered User
    Join Date
    Apr 2004
    Posts
    17

    Sorry for bumping this thread

    Hey there, sorry for bugging with this stupid thread...but I want to inform you that I have finally came up with something kind of nice...thanks to all the people who answered my question, and those who guided me specially bench hehehe...It sounds like I'm getting some prize, anyway...here is the final code for my kind of simple linked list...I added once again, a function to add a node at the beggining, somewhere in the middle, and the end of the list...but following bench's advice, I used three separated functions for adding the node...and made one Insert function, that sorts out where to insert the node....

    *NOTE: If you use insertInTheMiddle() in the main body, it'll insert the node between the first, and the second nodes...not in the middle of the list.

    Code:
    //A simple linked list
    #include <iostream>
    using namespace std;
    
    struct node {
        int x;
        node* next;
    };
    
    node* insertNodeAtTheFront( node* head, int data ){
         
         node* newHead = new node;  //Creates a new node
         newHead->next = head;  //Makes the next pointer to point to the old
                                // head
         newHead->x = data;     //Assigns the data
         return newHead;        //Returns the new head
    }
    
    void displayList( node* walker ){  //Displays all the elments of the list
    
         while(walker != 0 ){
           cout << walker->x << endl;
           walker = walker->next;  //Moves to the next element
         }  //while
    }
    
    void insertNodeInTheMiddle( node* currentNode, int data ){
         
         node* searchNode;  //Used to traverse the list
         node* previousNode;  //Holds the previous node searchNode was pointing to
         
         node* middleNode = new node;  //This node will be inserted in the middle
                                       // of the two
         middleNode->x = data;  //This node will hold the data to insert
         
         searchNode = currentNode;  //Start searching at current node
         previousNode = searchNode;  //Holds the current node
         searchNode = searchNode->next;  //Moves to the next node
         
         previousNode->next = middleNode;  //Makes the next pointer of the previous
                                           // node to point to the node to insert
         middleNode->next = searchNode;  //And makes that node to point to the next
                                         // node in the list
             
    }
    
    void insertNodeAtTheEnd( node* head, int data ){
         
         node* lastNode = head;  //Makes a new node to point to the list
         
    //The while loop searches for the antepenultimate node in the list
         while( lastNode->next != NULL )
                lastNode = lastNode->next;
                
         lastNode->next = new node;  //Creates a new node at the end of the list
         lastNode = lastNode->next;  //Moves to the last node
         lastNode->x = data;  //Assigns the data
         lastNode->next = NULL;  //Sets the new end of the list
         
    }
    
    node* insertNode( node* head, int data ){
         
         node* copyOfHead = head;  //This copy of head will be used to insert a
                                   // node at the end
         node* searchPtr = head;  //This node will be used to search and insertion
                                  // point between two nodes
    
    //If head hasn't been created, or if the value in the first node is less than
    // the value to insert, then insert a new node at the beggining of the list     
         if( ( head == NULL ) || ( data <= head->x ) ){
             head = insertNodeAtTheFront( head, data );
             return head;
         }
    
    //Searches for the value to insert until it has reached the antepenultimate
    // node     
         while( searchPtr->next != NULL ){
                searchPtr = searchPtr->next;            
                
    //If the data is less than the value in the current node, inserts it in the
    // middle
                if( data < searchPtr->x ){
                    insertNodeInTheMiddle( searchPtr, data );
                    return head;
                }
    
         }
    
    //If the list reached the last node, and it didn't found any match, it means
    // that the node should be inserted at the end of the list     
         insertNodeAtTheEnd( copyOfHead, data );
         return head;
    }
    
    void cleanList( node* root ){  //Clears the list from memory
    
        while( root != 0 ){
          node* temp = root;  //Assigns temp to be the current head
          root = root->next;  //Moves the head to the next element
          delete temp;  //Deletes the temporary head
        }  //while
    
    }
    
    int main(){
        node* head = NULL;
        
        head = insertNode( head, 0 );
        head = insertNode( head, 10 );
        head = insertNode( head, -1 );
        head = insertNode( head, 100 );
        head = insertNode( head, 7 );
        
        displayList( head );
        
        cleanList( head );   
        
        cin.get();
    }
    I haven't found any bugs yet....hope you don't either

    Anyway, here's my final question as well...This list its kind of useless...how do I make a list to hold any kind of data?, string, chars, another pointers...ints, floats, objects, structs....anything I throw at it....its that possible?

    EDIT: Ok I did find an error with the inserting function...but here's the working code...so change the insert function to this:

    Code:
    node* insertNode( node* head, int data ){
         
         node* copyOfHead = head;  //This copy of head will be used to insert a
                                   // node at the end
         node* searchPtr = head;  //This node will be used to search and insertion
                                  // point between two nodes
    
    //If head hasn't been created, or if the value in the first node is less than
    // the value to insert, then insert a new node at the beggining of the list     
         if( ( head == NULL ) || ( data <= head->x ) ){
             head = insertNodeAtTheFront( head, data );
             return head;
         }
    
    //Searches for the value to insert until it has reached the antepenultimate
    // node     
         while( searchPtr->next != NULL ){
                
                node* temp = searchPtr;  //Temporary holds the previous node
                searchPtr = searchPtr->next;
    //If the data is less than the value in the current node, inserts it in the
    // middle
                if( data <= searchPtr->x ){
                    insertNodeInTheMiddle( temp, data );
                    return head;
                }
                
         }
    
    //If the list reached the last node, and it didn't found any match, it means
    // that the node should be inserted at the end of the list     
         insertNodeAtTheEnd( copyOfHead, data );
         return head;
    }
    Actually, it's not changing it...just add this line to the while loop:
    Code:
                node* temp = searchPtr;  //Temporary holds the previous node
    And change the parammeter for insertInTheMiddle() to this:
    Code:
                    insertNodeInTheMiddle( temp, data );
    Thank you very much!
    Last edited by cold_dog; 09-13-2006 at 01:27 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  2. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  3. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 09:27 PM
  4. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 07:11 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM