Thread: Inserting at end of a linked list error

  1. #1
    Registered User
    Join Date
    May 2011
    Posts
    9

    Inserting at end of a linked list error

    Hi everyone, just doing some practices on linked lists. So I'm trying to insert a node at the end of a linked list but I'm getting this error saying i can't access the next node using P. P is just a node pointer that i want to use to traverse though the list, please show me where I'm going wrong if you spot the mistake, thank you!
    (the program compiles but crashes when i run)

    Code:
    void InsertNewLast(dataItem value, NodeType **L) {
         NodeType *N, *P;
         
         N = (NodeType*)malloc(sizeof(NodeType));
         N->data = value;
         N->next = NULL;
         
         if (*L==NULL){         // check for empy list
            *L = N;
         }
         else {                 // list is not empty
             P = *L; 
             while (P){            // traverse through list till the end
                   P = P->next;  // 
             }
             P->next = N;          // set N to be last node
         }
    }

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    So the whole point of the while loop is that, when you reach the end, P doesn't exist anymore (you've got, basically, "while P exists" as your loop). Trying to use P after that, then, is silly. You need to loop until P->next doesn't exist anymore, for then P will be your last element.

  3. #3
    Registered User
    Join Date
    May 2011
    Posts
    9
    hmm I see, thanks. but actually, even when i changed the while loop to while(P->next) and try to run the program, it still crashes on me for some reason..

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    if l
        n = malloc
        if n
           n->data =
           n->next =
        else
            fail
        for( p = *l; p && p->next; p = p->next )
            ;
        if !p
            *l = n
        else
            p->next = n
    That looks about right.


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

  5. #5
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    You really should learn to use a debugger. It will point out the exact line that causes your crash. As tabstop said, your loop condition was wrong, and a likely cause of your crash. But there are other potential places for a crash. Basically, anytime you have a pointer to something, if the pointer doesn't point to valid memory, then any dereference or member-of operator may cause a crash, i.e. *p or p->something. In your code, the following lines are suspect:
    Code:
         N->data = value;
         N->next = NULL;
    You didn't check to make sure malloc succeeded, so N could be NULL. Also, don't cast malloc (see this FAQ entry as to why)

    Code:
         if (*L==NULL){         // check for empy list
            *L = N;
    
    ...
             P = *L;
    You need to make sure L is valid before trying *L. You can at least check for L == NULL before dereferencing, but it also depends on how that parameter is passed in from the calling function.

  6. #6
    Registered User
    Join Date
    May 2011
    Posts
    9
    ok so i fixed the malloc issue. i'm not quite sure what you mean by make sure L is valid? like if L exists? i passed it in as **L, but i'm not too sure about the whole pointer to a pointer concept either. the function declaration were just already in the example. But so i did learn to use the debugger and it says my problem is right at the line when i tried calling P->next in my while loop statement. It gave me an error of "access violation (segmentation fault) raised in system". any idea what that means..?

    btw, thanks for all the help guys, really appreciate it

  7. #7
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,949
    Did you adjust your loop like quzah suggested? Seg fault means you are trying to access memory that isn't yours to access,which means you do not have a valid pointer. Post what you currently have.
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

  8. #8
    Registered User
    Join Date
    May 2011
    Posts
    9
    Code:
    void InsertNewLast(dataItem value, NodeType **L) {
         NodeType *N = malloc(sizeof(*N));
         NodeType *P;
         
         N->data = value;
         N->next = NULL;
         
         if (*L == NULL){         // check for empy list
            *L = N;
         }   
         else {                 // list is not empty
             P = *L; 
             while (P->next){            // traverse through list till the end
                   P = P->next;  // 
                   //printf("abc");
             }
             P->next = N;          // set N to be last node
         }
    }
    hm... i didn't really read over quzah's, i will try to adjust it now. thanks

  9. #9
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    What I was suggesting for checking if L is valid is this:

    Code:
    void InsertNewLast(dataItem value, NodeType **L)
    {
        if (L == NULL)
            // somebody passed in a NULL pointer for L, we can't continue, so return error
            // if L is NULL, and we try the next line, *L will seg fault, see method 1 below
    
        // here we can still seg fault if L was passed in with a bad address, as in method 2 below
        if (*L == NULL) {
            *L = N;
        }
    }
    If the code that calls InsertNewLast is not correct, then you can get a seg fault:
    Code:
    dataItem value;
    NodeType **L1 = NULL;
    NodeType **L2;
    NodeType *L3 = NULL;
    
    InsertNewLast(value, L1);  // L1 doesn't point to a valid piece of memory, but this can be protected against by the first if check above
    InsertNewLast(value, L2);  // L2 doesn't point to a valid piece of memory, and we can't protect against it, it's a seg fault waiting to happen
    InsertNewLast(value, &L3);  // This is the correct way to pass in a list to add to it

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 7
    Last Post: 11-04-2010, 01:18 PM
  2. Inserting into linked list
    By mikeman in forum C++ Programming
    Replies: 3
    Last Post: 01-22-2010, 07:46 PM
  3. inserting stuff into a linked list
    By cosmic_cow in forum C Programming
    Replies: 4
    Last Post: 08-13-2009, 03:09 PM
  4. inserting into linked list
    By MiroMage in forum C Programming
    Replies: 4
    Last Post: 09-16-2008, 07:55 PM
  5. linked list inserting
    By comar in forum C++ Programming
    Replies: 3
    Last Post: 07-26-2007, 07:01 AM

Tags for this Thread