Ok then, well lets take a look at the logic behind adding a node to a linked list in a certain order. The first thing we need to have is our function header, so let’s start with one:
Code:
void addNode(nodeType* nodeToAdd)
Here we can see that our function is going to take a pointer of type nodeType, and not return anything. Next we are going to need to create two more pointers to act as “walkers” so we can move through our linked list. So let’s do that:
Code:
nodeType* CurrentNode, *lastNode;
It is important to create two “walker” pointers here in order to successfully insert into our linked list, we will see why later. Now to insert an object into our linked list it would make sense to first check to see if the list is empty, and if it is to simply have the node be the first one:
Code:
if(head == NULL){
head = nodeToAdd;
nodeToAdd->nextNode = NULL; //Signifies end of list
return;
}
Now if our list is not empty we would need to walk through our list. This is where our “walker” pointers come into play. So the first thing we do is set our activeNode pointer to the first node in the list:
Code:
CurrentNode = head; //Start at the beginning
Then, we would want to initialize our last node pointer:
Now we begin to walk through our linked list. This is usually where it gets confusing so we will spend more time talking here. Lets suppose we have a linked list containing 3 nodes:
And we wanted to add node4 to this list, however we wanted to ensure our list remained in alphabetical order. To do this we would need to keep track of two things, the node we are currently on(Currentnode) and the node we were just at (previous or last node). So lets begin walking through our linked list.
1. We compare node4 with node1. node4 belongs after node1 so we continue down the chain, remembering where node1 is(in lastNode pointer).
2. We arrive at node2(Currentnode), and find that node4 belongs before node2. Now we need to do something. We know are linked lists are indeed linked:
Code:
node1----nextnode---->node2---nextnode---->node3
So in order to insert an item we need to redirect our nextnode pointers. Thankfully we remembered were node1 was by assigning it to our lastNode pointer. So we know that node1 needs to point to node4 and then node4 needs to point to node2.
Code:
node1----nextnode---->node4---nextnode---->node2---nextnode---->node3
So we assign node1’s(lastNode’s) nextnode pointer to node4 and we assign node4’s next node pointer to node2(Currentnode)
Alright that was a lot of talking, so lets bring on some code. The first thing we are doing in our loop is to use and if statement:
Code:
if(strcmp(nodeToAdd->Name, CurrentNode->Name) < 0){
Now if this statement evaluates to true we know that the node we want to add belongs before our Current Node. So now that we found where the node belongs we just need to do one more check, see if we are at the first node in the list or not (aka the head). To do this we check to see if lastNode is NULL. Remember we initialized this right before we entered our loop, so if it is still NULL that means our node to add belongs before the first node currently in the list. So we should see:
Code:
if(lastNode == NULL){
head = nodeToAdd;
}
Now if lastNode is not NULL we know we are somewhere inside the list, thus we would need to have the previous node’s nextnode pointer point to us:
Code:
else{
lastNode->nextNode = nodeToAdd
}
and finally we would need to have us point to the node we are coming before and then we would exit the loop/function:
Code:
nodeToAdd->nextNode = CurrentNode;
return;
Now you are probably saying well that’s great but how do I walk through the loop. Good point, remember that if statement with the comparison? Well if the statement doesn’t evaluate to true then you would walk through the loop. And how would you do that you might ask. It is pretty easy when you think about it. We have our CurrentNode and our lastNode. So to move through our loop we would move our lastNode to our CurrentNode. Then we would set our CurrentNode to the next node in the list:
Code:
else{
lastNode = CurrentNode;
CurrentNode = CurrentNode->nextnode;
And just one more thing. What happens if we are at the end of the list? Why we know the CurrentNode will be NULL and lastNode will be the last item, so we simply add our node after the last item:
Code:
if(CurrentNode == NULL){
lastNode->nextnode = nodeToAdd;
return;
}
So to see this whole thing put into a function:
Code:
void(nodeType* nodeToAdd){
nodeType* CurrentNode, *lastNode;
if(head == NULL){
head = nodeToAdd;
return;
}else{
CurrentNode = head;
lastNode = NULL;
while(1){
if(strcmp(nodeToAdd->name, CurrentNode->name) < 0){
if(lastNode == NULL)
head = nodeToAdd;
else
lastNode->nextnode = nodeToAdd;
nodeToAdd->nextnode = CurrentNode;
return;
}else{
lastNode = CurrentNode;
CurrentNode = CurrentNode->nextnode;
if(CurrentNode == NULL){
lastNode->nextNode = nodeToAdd;
return;
}
}
}
}
}