Insertion Into a Linked List

[newbiecplusplus]

Hi, i'm really stuck with this linked list and i feel tottaly out of my depth.

Hopefully i can get it a bit clearer! what im trying to do is a print simulation with three priorities and im trying to make the linked list to act like the queue so a job with priority 1 goes first and priority 3 goes last, any ideas?

[Ancient Dragon]

>>any ideas

Yes -- post code.

[newbiecplusplus]

thanks for replying this is all I have.. i have no idea how to do the above problem..

void linkedList::insert(short int theID)
{

liData *newItem = new liData;
newItem->PrintItem.jobNo = theID;
newItem->ptrNext = ptrHead;
ptrHead = newItem;
}

[Ancient Dragon]

that will probably work to just add the new node to the head of the linked list. To add in priority order you would have to transverse (iterate) the list and find the spot where the new node has to be inserted.

[newbiecplusplus]

Does that mean just searching through the list to find the appriopriate priority? (im generating the list using the RAND)

[Ancient Dragon]

>>Does that mean just searching through the list to find the appriopriate priority

Yes.

[newbiecplusplus]

Thanks ancient dragon for your previous help

After spending all night trying to think about this I still can't get it at all and im starting to give up can anyways please help as to how i would insert by priority in the linked list? priorties one to three, even an algorithm?

[Ancient Dragon]

assuming jobNo is the priority number, if it isn't then you will have to add another variable to the structure that is the priority of that node. I didn't attempt to compile or test this, so use it at your own risk :S

void linkedList::insert(shortint theID)
{
    liData *newItem = new liData;
    newItem->PrintItem.jobNo = theID;
    // find the insertion poit of the new node
    liData *prev = NULL;
    liData *temp = NULL;
    for(temp = ptrHead; temp->ptrNext != NULL; temp = temp->ptrHead)
    {
          // is new node's priority less than current node pointer's priority?
          if(newItem->PrintItem.jobNo <  temp->PrintItem.jobNo)
          {
              if(prev == NULL)
              {
                    // add new node at the head
                    newItem->ptrNext = temp;
                    ptrHead = newItem;
                    break;
              }
              else
              {
                    // add new node somewhere in the middle of the list
                    newItem->ptrNext = temp;
                    prev->ptrNext = newItem;
                    break;
               }
               // save current node address
               prev = temp;
    }
     // if it gets to here then all the nodes in the list have the same
     // priority as the new node.  So just add the new node to the 
     // head of the list.
     newItem->ptrNext = ptrHead;    
    ptrHead = newItem;
}

[bbman]

thanks