Linked List alpha insertion

Hi.
when you see my code, it will go without saying I struggle with this-but I'm trying...

I have a LL class that has a data from a struct that holds
name and number.

I am trying to write the insert function so that the list is travered
and any new node is inserted in the appropriate alpha spot.

this is what I have:

Code:

void TList::insert (Data&d)
{
TList* tptr = new TList;
tptr->D = d;
while (head->D.name < tptr->D.name)
tptr=tptr->next;

next = tptr;
count++;
}

any suggestions would be a help.

also should I initialize head as NULL and say if the head is NULL
make the new node head?

thanks a bunch

also should I initialize head as NULL and say if the head is NULL
make the new node head?

That sounds like a good idea to me--rather than having head point to some random spot in memory, if it's NULL you will get an error if you do something wrong rather than continuing with junk data.

You could also have a pointer in your container class that points to the last node, so instead of having to traverse the list, you would have direct access to the last node.

Assume tptr is the node you want to add to the list and head is where you start. Another node pointer is needed to run the list, say current. First, assign head to current. Then compate current->D.name to tptr->D.name until you find the insetion point. With singly linked lists there are two pointer assignments that need to change with each insertion (unless the list is empty) First, assign the next pointer of the current node to the next pointer of the node to insert. Second, assign the node to insert to next pointer of current node.

I just cannot get this!
Then compate current->D.name to tptr->D.name until you find the insetion point.
the following is my attempt at this function.
(i have an overloaded > op in the struct TeleEntry to compare names.
this is it:

Code:

 bool TeleEntry::operator > (const char* &TeleEntryA) const
 {
	 if (strcmp(this->EntryName, TeleEntryA) > 0)
	 {return true;}
	 else
	 {return false;}
 }

then i use it in my function:
please make a suggestion

Code:

int ListofTeles::Add(TeleEntry *NewItem)
{
 TeleEntry *Sample = new TeleEntry;
 TeleEntry *current;
 current=Head;
if (strcmp(current->EntryName, Sample->EntryName) < 0)
{
 Sample   = NewItem;
 Sample->Next = Head;
 Head  = Sample;
}
else
current=current->Next;

 
 return size++;
}

thanks very much

Did you look at the other file (SectionB.cpp) I attached in this thread . I think this will show you the general logic you need. Just look at the addNode function.

I did study it but, can't get some of the C logic.
I am very weak with this.

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:

Code:

lastNode = NULL;

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:

Code:

node1     node2     node3

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;
                    }
               }
           }
     }
}

Andy,
your explanation was excellent.
I feel as though I understand it alot better -
I appreciate your time immensely.

Problem is, following your logic-my program is still crashing when I add a second node.
so, for some reason something is off and I can't tell what...

here is the assembly error from the debugger:

Code:

strcmp:
004226A0   mov         edx,dword ptr [esp+4]
004226A4   mov         ecx,dword ptr [esp+8]
004226A8   test        edx,3
004226AE   jne         dopartial (004226ec)
dodwords:
004226B0   mov         eax,dword ptr [edx]
004226B2   cmp         al,byte ptr [ecx] <------------arrowed problem
004226B4   jne         donene (004226e4)
004226B6   or          al,al

figured out the probl..thanks andy!!