Linked List Question

[Ganon11]

If you're only making one comparison per number, you won't get it into sorted order. And how would you print it before if you are outputting to a file? You may be interested in Insertion Sort, but you'll still need to get the numbers into an array before sorting.

Basically, if you're looking at only 2 numbers at a time, you can properly sort those 2 numbers, but that doesn't mean the entire list of numbers will be sorted. Take the following number sequence as an example:

1, 3, 8, 4, 6, 5, 2

So you read 1 and 3 in. 1 is less than 3, so you print that. Then you grab 8. 3 is less than 8, so you print 3. Now you get 4. 4 is less than 8, so you print that, etc, etc. The final list you get is:

1, 3, 4, 6, 5, 2, 8

which is obviously not sorted.

[beacon]

Ahh, I see. I don't know why I thought I could compare them that way. I guess I will need some kind of sort, regardless.

[weaknessforcats]

Now the add function:
1) starts at the Node address passed in
2) compares the number to the number in the node.
3) if the number is less than the node:
a) create a new node with the number in it.
b) insert the new node after the previous node.
Otherwise, you advance to the next node in the list
4) Repeat step 2 and 3.

1, 3, 8, 4, 6, 5, 2


So create an empty list, then follow the steps I outlined:
1) pass in 1
-list is empty
- Node 1 = 1
2) pass in 3
- 3 not less than 1
-advance list
-you are at the end
- add 3 as ne end of list
- Node 1 = 1, Node 2 = 3
3)pass in 8
-advance until 8 is less than the node
-you are at the end
- add 8 as new end of list
- Node 1 = 1, Node 2 = 3, Node 3 = 8
4)pass in 4
-advance until 4 is less than node.
- insert 4 after Node 2
- Node 1 = 1, Node 2 = 3, Node 3 = 4, Node 4 = 8
5)pass in 6
-advance until 6 is less than node.
- insert 6 after Node 3
- Node 1 = 1, Node 2 = 3, Node 3 = 4, Node 4 = 6, Node 5 = 8
6)pass in 5
-advance until 5 is less than node.
- insert 5 after Node 3
- Node 1 = 1, Node 2 = 3, Node 3 = 4, Node 4 = 5, Node 5 = 6, Node 6 = 8
7)pass in 2
-advance until 2 is less than node.
- insert 2 after Node 1
- Node 1 = 1, Node 2 = 2, Node 3 = 3, Node 4 = 4, Node 5 = 6, Node 6 = 8

You don't need either an array or a sort.

[beacon]

I'm confused still, but what's new. So basically I should use my insert node method to sort the data (I know the names of my methods don't coincide with my intentions, but they are the names my professor asked us to use)? Here's my updated code. Any thoughts??

void SortedList::InsertNode(int data)  
                           
{
    node * temp;   
    node * nodeptr;   
    node * nodeptrprev; 
    temp = new node;    
    temp->data=data;    
    temp->next=NULL;   
    
    if(!descending)        
    {
       if (head == NULL)    
       {                    
           head = temp;   
           return;            
       }
       nodeptr = head;    
       nodeptrprev = nodeptr;    
                    
       while(nodeptr->data < temp->data && nodeptr->next != NULL)
       {        
            nodeptrprev = nodeptr;    
            nodeptr = nodeptr->next; 
       }            
		
       if(nodeptr->next == NULL && nodeptr->data < temp->data)
       {     
             nodeptr->next=temp; 
       }        
       else
       {
	if (nodeptrprev == head && nodeptrprev->data > temp->data)
	{		
	     head = temp;    
                     temp->next = nodeptrprev;
	}
	else
	{
	     temp->next = nodeptr;    
                     nodeptrprev->next = temp;
	}
       }
    }
    else   
    {
        if (head == NULL) 
        {
            head = temp;   
            return;        
        }
        nodeptr = head;   
        nodeptrprev = nodeptr;  
        while(nodeptr->data > temp->data && nodeptr->next != NULL)
        {   
            nodeptrprev = nodeptr;  
            nodeptr = nodeptr->next;  
        }
            if(nodeptr->next == NULL && nodeptr->data > temp->data)
                {    
                    nodeptr->next=temp;    
                }
            else  
            {    
                if (nodeptrprev == head && nodeptrprev->data < temp->data)
                {                   
                    head = temp;    
                    temp->next = nodeptrprev;   
                }                
                else    
                {
                    temp->next = nodeptr;   
                                nodeptrprev->next = temp;    
                }        
            }
    }
}

[weaknessforcats]

I am going to put mkjy comments inside your code sample.

void SortedList::Ins ertNode(int data)

{
node * temp;
node * nodeptr;
node * nodeptrprev;
temp = new node;
temp->data=data;
temp->next=NULL;

Why not just say ascending ???
I assuke you are using an enum.
VVVVVVVVVVVV
if(!descending)
{
if (head == NULL)
{
temp is an uninitialized node*. You need to malloc a mode and put the data in it before you return.
VVVVVVVVV
head = temp;
return;
}
nodeptr = head;
if head is the start of the list then there is not previous node and
so nodeptrprev should be set to 0.
VVVVVVVVVVVVVVV VV
nodeptrprev = nodeptr;
just compare the data in the new node (temp) to the list (nodeptr).
Since this is an ascending sort stay in the loop as long as the new data is greater than the list:
while (temp->data > nodeptr->data)
{
if (nodeptrprev == 0)
{
// temp is new end of list
nodeptrprev = temp;
return
}
temp->next = nodeptrprev;
nodeptrprev = temp;
return;

So what's with all the code???
VVVVVVVVVVVVVVV VVVVVVV
while(nodeptr->data < temp->data && nodeptr->next != NULL)
{
nodeptrprev = nodeptr;
nodeptr = nodeptr->next;
}

if(nodeptr->next == NULL && nodeptr->data < temp->data)
{
nodeptr->next=temp;
}
else
{
if (nodeptrprev == head && nodeptrprev->data > temp->data)
{
head = temp;
temp->next = nodeptrprev;
}
else
{
temp->next = nodeptr;
nodeptrprev->next = temp;
}
}
}
else
{
if (head == NULL)
{
head = temp;
return;
}
nodeptr = head;
nodeptrprev = nodeptr;
while(nodeptr->data > temp->data && nodeptr->next != NULL)
{
nodeptrprev = nodeptr;
nodeptr = nodeptr->next;
}
if(nodeptr->next == NULL && nodeptr->data > temp->data)
{
nodeptr->next=temp;
}
else
{
if (nodeptrprev == head && nodeptrprev->data < temp->data)
{
head = temp;
temp->next = nodeptrprev;
}
else
{
temp->next = nodeptr;
nodeptrprev->next = temp;
}
}
}
}

You could also do the head == NULL check before you do the ascending/descending check. That would eliminate one test from the function.

Also, the ascending/descending has to do with how to compare the the two nodes based on gthe desired . That test should be inside the loop rather than outside.

The pseudocode might be:

Is list empty?? If yes, temp is new head of list ->> return.

Loop:
While list->next != NULL
if (ascending)
is new data greater than list
insert new data after previous node
return
if (descending)
is new data less that list
insert new data after previous node
return