Linked List Template Class Insertion

Dega (5)
Hi.
I have been scratching my head trying to find out why I am getting a crash every time I try to use the insert() method in a Linked List template class I am working on.

Here is the code I have for the insert method in question. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
template <typename T>
void LinkedList<T>::Insert(T value){
//traverse the list and ADD a given value

     //dynamically allocate mem and create new node
     ListNode *NewNode = new ListNode; 
     NewNode->data = value; 
     NewNode->next= NULL; 
 
     //check if our first pointer has a value, if not... point to our new node
     if(first == NULL){
         first=NewNode;
     }
     else{
          //initialize current pointer to start of our list
          ListNode *current= first;
          
          //initialize a previous pointer
          ListNode *prev= NULL;
          
          //traverse our list to the insert location
          while (current->data < value && current->next !=NULL){ 
                prev = current; 
                current = current->next; 
          }//we should now be at our insertion location
          
          //update our pointers
          prev -> next = NewNode; 
          NewNode -> next = current;  
     }
     //increment size
     ListSize++;
}


What is going wrong? I traced the code (drew it out on paper) and I don't see how it is crashing. Inserting the first value (as I am testing) should just be running the following portion, right?: 

1
2
3
 
if(first == NULL){
    first=NewNode;
}


Any idea what I am missing here?
Dega (5)
Anyone? I need to get this figured out asap :(
xerzi (648)
In the case there is only 1 node, "prev" remains nullptr and you try to set "prev->next" of a nullptr.
Last edited on
Dega (5)
I'm still kinda lost. I am testing the insertion with only 1 value. This should only be doing:

first=NewNode;

right? (based on precondition that first is initialized to NULL, which it is).

xerzi (648)
1
2
3
4
5
6
7
8
9
10
 
         ListNode *current= first; // only 1 value in list which is first
         ListNode *prev= NULL;
          
  
          while (current->data < value && current->next !=NULL){ 
                prev = current; // this never gets called as current->next is NULL
                current = current->next; 
          }

          prev -> next = NewNode; // prev is invalid so exception happens here
Dega (5)
Oh. I think I see it now...

So do I just catch it in an if/else statement (right after the while) like so?:

1
2
3
 
if(current->next == NULL){
    current->next = NewNode;
}


xerzi (648)
Think about what that is doing, do you want NewNode to always be after current ?
Last edited on
Dega (5)
lol... I must be thinking too hard at this point or something.
Guess I will have to go back to basics and hit up some tutorial videos or something. Hopefully it magically makes full sense before Monday.
xerzi (648)
Yah it can be done with a pointer to a pointer pretty easily, or if it was a doubly linked list :P.
Last edited on
Topic archived. No new replies allowed.

C++

Forum