Help with insert function with nodes

[pepstein]

In this program I am attempting to create a function called "insert" which takes in a node and a value. The function is supposed to insert it into a position within the linked list based on its value; the node is presorted so no need to worry about that. So if the list contains nodes holding the values "25", "15", "10", and I want to insert a Node with the value "20" it will be input between the 25 and 15 nodes. The problem I am having is that the insert function is only working when I try to insert a node who's value is lower than all the values of the nodes currently in the list. So in the previous example if I added a node with value "1" it would be inserted to the end correctly. However, if I try to insert a Node with a value higher than all current nodes it doesn't insert it at all and if I insert a Node with a value that should is in between values that are already in the list, like "20" in the previous example it is inserting it at the end only overwriting the last Node. It is probably something wrong with the insert algorithm but I can't figure it out, any help would be appreciated, thanks.

insert function

 template <typename T>
void insert(Node<T> *head, T val) {
    Node<T> *p=head;
	Node<T> *q=NULL;
	while (p !=NULL && val < p->data) {
            q=p;
            p=p->next;
	}
    if (q==NULL)
        insertFront(val, p);
    else
        insertAfter(q, val);
}

insertAfter function

template <typename T>
void insertAfter(Node<T> *nodeP, const T &val) {
	if (!nodeP) throw "Passed NULL to insertAfter";
	Node<T> *newNodeP = new Node<T>(val);
	nodeP->next = newNodeP;
}

insertFront function

template <typename T>
void insertFront(T data, Node<T> *nodeP) {
        nodeP = new Node<T>(data, nodeP);
        //*nodeP = newNodeP;
}

[pepstein]

any ideas on how I am approaching this wrong?

[booradley60]

In your insertAfter function, you create a new node called newNodeP. What is newNodeP's "next" pointer supposed to point to? You never set it to anything.

I find it really handy to do this work with pencil and paper. Draw lots of pictures. Then, once you've got a good idea of all the little tasks you must do, implement in code.

[busturdust]

http://codereview.stackexchange.com/questions/4569/linked-list-implementation-in-c

study up

-TheBaddestOne

[pepstein]

thanks for the help thus far, I have been able to implement it so if I insert a node with a value lower than all current values it works (is placed as the last node) and if I insert a node with a value in between values in the list it is inserted correctly and in the right position, but I am still unable to insert nodes with a value larger than all the current values in the nodes. When I do that it simply doesn't do anything, no node is inserted. I must be doing the algorithm wrong or something but I've looked at it for a while and can't figure it out. Here are the functions in question, it's messy since I've tried a bunch of different ways thus far, none which have worked (some closer than others):

insert function

template <typename T>
void insert(Node<T> *head, T val) {
    Node<T> *p=head;
	Node<T> *q=NULL;
    if (val > p->data){
        insertFront(val, p);
    }
    else {
        while (p !=NULL && val < p->data)
        {
            q=p;
            p=p->next;
        }
    insertAfter(q, val);
    }
}

insertFront

template <typename T>
void insertFront(T val, Node<T> *nodeP) {
   Node<T> *newNodeP = new Node<T>(val);
    //nodeP->next = newNodeP;
    newNodeP->next=nodeP;
}

insertAfter

template <typename T>
void insertAfter(Node<T> *nodeP, const T &val) {
	if (!nodeP) throw "Passed NULL to insertAfter";
	Node<T> *newNodeP = new Node<T>(val, nodeP->next);
	nodeP->next = newNodeP;
}

I haven't had problems with insertAfter but figured I'd throw it in, if you see problems with that please let me know. Thanks for the help.

[pepstein]

is anyone able to see what I am doing wrong? still stumped

[D80DSL3A]

I do see a problem with insertAfter(). newNodeP is to be inserted between nodeP and nodeP->next, hence:

newNodeP->next = nodeP->next;// point to node following nodeP
nodeP->next = newNodeP;// now newNodeP follows nodeP 

You're missing the 1st assignment.

[pepstein]

that's a good point, fixed that, thanks. any clue what i'm doing wrong with insertbefore?

[D80DSL3A]

I see an insertFront(), but no insertBefore().One problem with the insertFront() is that the value of head can't be updated, as it should be. newNodeP becomes the new list head.

Pass head by reference (or a pointer to it) to insertFront. Note the change to line 2.

template <typename T>
void insertFront(T val, Node<T> *& nodeP) {// passing pointer by reference
   Node<T> *newNodeP = new Node<T>(val);
    newNodeP->next=nodeP;

    nodeP = newNodeP;// save the new list head
}

EDIT: I just noticed that fix won't be enough. A copy of head is being passed to insertFront() in the insert(). You will need to pass head itself in order for it to be changed by the function.
I also see that head is passed by value to insert(), from a pointer declared in main()? So, I don't see how the insert() is working at all. Are you allocating the 1st node to head in the main() before ever calling insert()? This would at least give you something to insertAfter.

[pepstein]

thanks for the help, yes, in main the list is originally created before ever calling insert.

[D80DSL3A]

OK. I thought so. I'm guessing that insertFront operations aren't working. That's because the insert() can't change what head points to in main().
Passing head by reference to insert() and to insertFront() ( and change line 6 in insert() to
insertFront(val, head); ) should fix the problem.

You're welcome for the help. I enjoy the exchange, particularly if it leads to a solution!

[pepstein]

yup, that was the exact problem. i always screw up with passing by value and reference, thanks for pointing out the mistake.

[D80DSL3A]

Glad that worked out so quickly.
There were 3 ways I could think of to solve the problem.Passing a pointer to head is one way, but I'd avoid it due to the convoluted pointer syntax then required in the insert functions.

I hereby challenge you to rewrite insert and insertFront so they return the new value of head (instead of void). head may now be pass by value to these functions since any change to head will be given by the return value.
in main() head = insert( val, head );// new head value will be returned if an insertFront is made.
The new function prototypes would be then:

template <typename T>
Node<T>* insert(T val, Node<T> * pNode);

template <typename T>
Node<T>* insertFront(T val, Node<T> * currHead);

[S3TkoG1T]

Hi Pepstein, Marissa here. How are you are calling insert() in the main?