Thread: Linked List alpha insertion

  1. #1
    Registered User mouse163's Avatar
    Join Date
    Dec 2002
    Posts
    49

    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

  2. #2
    Registered User
    Join Date
    Apr 2003
    Posts
    2,663
    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.
    Last edited by 7stud; 02-19-2005 at 10:11 AM.

  3. #3
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    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.
    You're only born perfect.

  4. #4
    Registered User mouse163's Avatar
    Join Date
    Dec 2002
    Posts
    49
    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

  5. #5
    Handy Andy andyhunter's Avatar
    Join Date
    Dec 2004
    Posts
    540
    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 don't think most standard compilers support programmers with more than 4 red boxes - Misplaced

    It is my sacred duity to stand in the path of the flood of ignorance and blatant stupidity... - quzah

    Such pointless tricks ceased to be interesting or useful when we came down from the trees and started using higher level languages. - Salem

  6. #6
    Registered User mouse163's Avatar
    Join Date
    Dec 2002
    Posts
    49
    I did study it but, can't get some of the C logic.
    I am very weak with this.

  7. #7
    Handy Andy andyhunter's Avatar
    Join Date
    Dec 2004
    Posts
    540

    Adding nodes to Linked Lists in Order

    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;
                        }
                   }
               }
         }
    }
    i don't think most standard compilers support programmers with more than 4 red boxes - Misplaced

    It is my sacred duity to stand in the path of the flood of ignorance and blatant stupidity... - quzah

    Such pointless tricks ceased to be interesting or useful when we came down from the trees and started using higher level languages. - Salem

  8. #8
    Registered User mouse163's Avatar
    Join Date
    Dec 2002
    Posts
    49
    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...

  9. #9
    Registered User mouse163's Avatar
    Join Date
    Dec 2002
    Posts
    49
    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

  10. #10
    Registered User mouse163's Avatar
    Join Date
    Dec 2002
    Posts
    49
    figured out the probl..thanks andy!!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help sorting a linked list. Beginner
    By scarlet00014 in forum C Programming
    Replies: 1
    Last Post: 09-27-2008, 06:16 PM
  2. Adding directory/file names to a linked list
    By thoseion in forum C Programming
    Replies: 13
    Last Post: 12-08-2006, 01:13 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM