Linked List Question

[beacon]

As you can probably tell from the title, I'm a little frustrated with linked lists. I'm working on a homework assignment and it just isn't making sense to me. I've read and read and read on the subject and I've checked out sample code, but I can't for the life of me get to methods in my class to work, let alone make sense. I've talked to my professor and to tutors at school, but I'm no better now than I was 2 weeks ago when the program was assigned.

Here's the gist:

1) I have to create a linked list that will sort in ascending or descending order based on the user's input and it has to be in a class. The list will read in data from a file that will be named at runtime(???). If it is not named it will get a generic filename.

2) I have to create an append method that will place a new node at the end of the list.

3) I have to create an insert method that will place a new node in the correct order (ascending or descending) in the list.

4) I have to create a print method to output the data.

First off, I have no idea what should go in my constructor. Should I prompt the user to enter 'd' or 'a' and then call the constructor based on their input?

Secondly, I can't get the insert method to work to save my life. I keep getting lost in an infinite loop and don't know why.

Anyway, here's my code so far if anyone would like to help.

Thanks...

//*** MAIN ***
#include <iostream>
#include <fstream>
#include <string>
#include "SortedList.h"
 
using namespace std;
 
void fileName();
 
void main(){
 
    fileName();
 
    /*string order;
    cout<<"Enter 'A' for ascending or 'D' for descending ";
    cin>>order;
 
    if(order == 'D'){
        SortedList list("descending");
    }
    else
        SortedList list("ascending");*/
 
    cin.clear();
 
    SortedList list("ascending");
 
    list.appendNode(23);
 
    list.printList();
}
 
void fileName(){
 
    ifstream infile;
 
    cout<<"Please enter a name for your file: ";
    string x;
    getline(cin,x);
 
    if(x == "\0"){
        cout<<"Your filename will be nums.in";
        infile.open("nums.in");
    }
    else{
        cout<<"Your filename will be "<<x.c_str()<<endl<<endl;
        infile.open(x.c_str());
    }    
}

// SortedList.cpp: implementation of the SortedList class.
//
//////////////////////////////////////////////////////////////////////
 
#include <iostream>
#include <fstream>
#include <string>
#include "SortedList.h"
 
using namespace std;
 
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
 
SortedList::SortedList(string order)
{
 
    if(order == "descending") 
        cout<<"so you want a descending list"<<endl; 
    else 
        cout<<"so you want an ascending list"<<endl; 
    head = NULL; 
 
}
 
SortedList::~SortedList()
{
 
}
 
/*void SortedList::appendNode(int inData){
 
    node *Ptr = head; // combining the steps; create a pointer and assign it to head
                             //Ptr = head;
    node *nodePtr;
    nodePtr = new node;
 
    nodePtr->data = inData;
    nodePtr->next = NULL;
 
    while(Ptr != NULL){
        if(Ptr->next == NULL){
            Ptr->next = nodePtr;
 
        }
        else//(nodePtr->next != NULL)
            Ptr = Ptr->next;
    }
}*/
 
void SortedList::appendNode(int inData){
    node *Ptr; 
 
    node *nodePtr;             
    nodePtr = new node; 
    nodePtr->data=inData; 
    nodePtr->next=NULL; 
 
    if(head==NULL) 
        head = nodePtr; 
    else{
        Ptr= head;
        while(Ptr->next!=NULL){
            Ptr=Ptr->next;
        }
        Ptr->next=nodePtr;
    }
    /*else{ 
        Ptr = head; 
        while(Ptr->next){ 
            Ptr = Ptr->next; 
        } 
        Ptr->next = nodePtr; 
    } */
}
 
void SortedList::insertNode(int inData){
 
    node *Ptr = head;
    node *tempPtr = head->next;
 
    node *nodePtr;
    nodePtr = new node;
    head->next = nodePtr;
    nodePtr->data = inData;
    nodePtr->next = NULL;
 
    while(Ptr != NULL){
        if(Ptr->data > tempPtr->data)
        {
            Ptr->next = nodePtr;
            nodePtr->next = tempPtr;
            tempPtr = tempPtr->next;
        }
        else //(Ptr->data < tempPtr->data)
        {
            Ptr = Ptr->next;
            tempPtr = tempPtr->next;
        }
    }
}
 
void SortedList::printList(){
    node *Ptr;
    node *nodePtr;
    Ptr=head;
    nodePtr = head;
    while(nodePtr!=NULL){
        cout<<nodePtr->data<<endl;
        nodePtr = nodePtr->next;
    }
}
 
void SortedList::revprintList(){
 
}
 
void SortedList::graphvizOut(){
 
}
 
/*void IntList::AppendNode(int data) 
{ 
 
    node *Temp; 
 
    node *NewNodePtr;             
    NewNodePtr = new node; 
    NewNodePtr->data=data; 
    NewNodePtr->next=NULL; 
 
    if(head==NULL) 
        head = NewNodePtr; 
    else{ 
        Temp = head; 
        while(Temp->next){ 
            Temp = Temp->next; 
        } 
        Temp->next = NewNodePtr; 
    } 
}*/
 

// SortedList.h: interface for the SortedList class.
//
//////////////////////////////////////////////////////////////////////
 
#include <iostream>
#include <fstream>
#include <string>
 
using namespace std;
 
#if !defined(AFX_SORTEDLIST_H__960B0846_9203_4427_9B0E_F30C4B0FA28A__INCLUDED_)
#define AFX_SORTEDLIST_H__960B0846_9203_4427_9B0E_F30C4B0FA28A__INCLUDED_
 
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
 
typedef int nodetype;
 
struct node{
    nodetype data;
    node*next;
    node*prev;
};
 
class SortedList  
{
private:
    node *head;
public:
    SortedList(string);
    ~SortedList();
    void inputFile();
    void appendNode(int);
    void insertNode(int);
    void printList();
    void revprintList();
    void graphvizOut();
 
};
 
#endif // !defined(AFX_SORTEDLIST_H__960B0846_9203_4427_9B0E_F30C4B0FA28A__INCLUDED_)
 

[beacon]

Well, I had to put this program on hold to work on some other things, which probably wasn't the best thing to do, but I'm back and I think I have a better understanding of what I need to do.

Problem now is something basic, I'm sure, but still presenting problems for me. Here's the gist:

Forget linked lists for a minute. I have created a file with random numbers in it (called "nums.in") using a function. I need to get these random numbers in sorted order, either ascending or descending.

I'm guessing that I need to read in the numbers from the file I created, compare them, and write them out to either the same file or a different file. I can read in numbers okay (using a while(!infile.e of())), but how do I compare the number being read in with the number that is at the end/beginning of the list (depending on if ascending or descending is chosen)?

Would I do something like this (for ascending):

infile>>x;
while(!infile.eof()){
     infile>>y;
     if(x>y){
          ofile<<x<<endl;
          ofile<<y<<endl;
     }
     else{
          ofile<<y<<endl;
          ofile<<x<<endl;
     }   
}
 

Once the numbers are in order, then I can begin appending, inserting, and printing my list, right? Do these numbers from the file get infiled into their own node?

Thanks for the help,
B

[weaknessforcats]

I suggest you keep your list in sorted order to begin with.

So you create an emty list.
You read a number from the file.
You add it to the list.
Repeat the previous step until the end of file is reached.

You now have a sorted list.

That's about all the code in main().

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.

[beacon]

So, I created the list of "random" numbers and sent it to an outfile. Now I need to turn around and read in the numbers into sorted order, right? Do I need to place these numbers in a different file if I want to track or check the output?

I'm not sure I know how to read in a number, then read in another number and compare it to the last number that I read in.

[Ganon11]

I would focus on reading all the numbers into an array first, and then sorting the array. There are a few sorting methods outlined in the C++ Articles section that are very simple to code (but not efficient. For your program, though, this shouldn't matter.). If you need something faster (but more difficult to code), try Quick Sort.

[beacon]

Hey Ganon,

That seems like extra work. It would seem to me that I could read in a number, compare it to the previous number, and then place it before or after that number. As each number is read in, there should be only one comparison made to sort the list.

I was hoping to read in the random numbers into sorted order so I don't have to sort them later. This will make using my class methods easier to implement.

I could be wrong, but wouldn't using an array take up more memory, especially if I try to sort it?

[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