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_)
 

[weaknessforcats]

I believe your design is at fault.

Since this is a linked list, your class should be appropriately named:

class LinkedList
{
 
};
 
 

A linked list is a series Nodes connected by addresses. The Node contains the data.

class Node
{
     Datatype* the data;
     Node* next;
     Node* prev;
};
 

The LinkedList just need info on the start, end and current position (in the cas eof a traverse) of the list:

class LinkedList
{
    Node* start;
    Node* end;
    Node* current;
 
};
 

The only mention of Node next/prev pointers will be in the Node member functions.

The Node class does not know there is a list. All it knows is that there are Nodes with data. That means you can write twomethods on the Node to insert the this object before or after the Node used on the call.

class LinkedList
{
    Node* start;
    Node* end;
    Node* current;
   public:
     void InsertAfter(Node* first);
     void InsertBefore(Node* first);
 
};
 

To sort the list, you just need a method on the LinkedList class

class LinkedList
{
    Node* start;
    Node* end;
    Node* current;
 
   public:
     enum Sequence {ASCENDING, DESCENDING};
     void Sort(enum Sequence);
 
};
 

The Datatype for the data in the Node is a second level of development. Initially, I would just use an int until the linked list code is working. Then I would create a template class for the Datatype.

[beacon]

I believe your design is at fault.

Since this is a linked list, your class should be appropriately named:

class LinkedList
{
 
};
 
 

A linked list is a series Nodes connected by addresses. The Node contains the data.

class Node
{
     Datatype* the data;
     Node* next;
     Node* prev;
};
 

The LinkedList just need info on the start, end and current position (in the cas eof a traverse) of the list:

class LinkedList
{
    Node* start;
    Node* end;
    Node* current;
 
};
 

The only mention of Node next/prev pointers will be in the Node member functions.

The Node class does not know there is a list. All it knows is that there are Nodes with data. That means you can write twomethods on the Node to insert the this object before or after the Node used on the call.

class LinkedList
{
    Node* start;
    Node* end;
    Node* current;
   public:
     void InsertAfter(Node* first);
     void InsertBefore(Node* first);
 
};
 

To sort the list, you just need a method on the LinkedList class

class LinkedList
{
    Node* start;
    Node* end;
    Node* current;
 
   public:
     enum Sequence {ASCENDING, DESCENDING};
     void Sort(enum Sequence);
 
};
 

The Datatype for the data in the Node is a second level of development. Initially, I would just use an int until the linked list code is working. Then I would create a template class for the Datatype.

I appreciate your help, but we haven't learned enum, templates, or the 'this' object yet. I'm sure that knowing these things would make my program much easier, but I'm pretty much confined to what is contained herein.

[arnaudk]

Use enums, they're very simple and make your code more readable, it'll take you two minutes to learn how they work.

enum Sequence {ASCENDING, DESCENDING};
void Sort(enum Sequence);

is just pretty way of saying

int Sequence;
void Sort (int Sequence);

where you decide that Sequence=0 means ascending, Sequence=1 means descending.

You don't need to use templates at this stage if you don't want to. Just replace DataType by int or whatever, or you can typedef DataType as an alias to some other type. You can implement the suggestions above without using the this pointer.

Finally, there's no point in quoting the entire previous message in your answer, is there?

[weaknessforcats]

I appreciate your help, but we haven't learned enum, templates, or the 'this' object yet. I'm sure that knowing these things would make my program much easier, but I'm pretty much confined to what is contained herein.

I can understand not knowing templates.

However, enums are prehistoric C and you should know those by now.

But you can't use classes and write member functions without knowing what the this pointer is. The this pointer always contains the address of the object that contains the member data that the member function uses.

[beacon]

Sorry about the quote...it automatically came up like that when I hit reply and I wasn't paying attention. I'm going to read over your suggestions and try them out again. I'll post again if I stumble across something else confusing.\

Thanks...

[beacon]

I can understand not knowing templates.

However, enums are prehistoric C and you should know those by now.

But you can't use classes and write member functions without knowing what the this pointer is. The this pointer always contains the address of the object that contains the member data that the member function uses.

I wish you'd tell that to my professor. I hadn't programmed in any language but HTML before taking this class. I took a first level computer science class last semester, but we didn't cover anything like this then either. We've only focused on C++...no C whatsoever besides the fact that you can use using namespace std to avoid having to type std::cout or what have you.

Those are just a couple of reasons why I'm so frustrated with computer science at the moment. I love working with computers, but I feel like my professors aren't covering things that should be covered after speaking with people that have been in the game for a while.

Thanks for getting on to me by the way considering that you didn't even offer a lick of helpful advice this time around. What the hell is this forum for if users, nay moderators, like you are going to degrade other people that are trying to and are eager to learn a language. Instead of teaching me, you belittle me. That's not very becoming of someone that claims they've taught C++ for 15 years. Just because you've had more training and time spent with this doesn't mean that you are better than me. Why don't you go find a meat bathing suit and take your happy ass swimming with some sharks?

[Studlyami]

I think you misinterpreted the intention of that post I didn't see it as a personal attack, but a person who is just surprised that you didn't know some of the more basic topics before you were taking on a couple more of the complex ones and from the sound of it, the class structure at your school didn't cover what was needed.

As for not offering help he helped you on your design and he gave you several reference points in which you could expand your knowledge and help the program at hand (looking up enums for example). This site is one of the few sites where people here will actually help you with your program and understand what it is doing rather than just giving out an answer.

[beacon]

I think you misinterpreted the intention of that post I didn't see it as a personal attack, but a person who is just surprised that you didn't know some of the more basic topics before you were taking on a couple more of the complex ones and from the sound of it, the class structure at your school didn't cover what was needed.

As for not offering help he helped you on your design and he gave you several reference points in which you could expand your knowledge and help the program at hand (looking up enums for example). This site is one of the few sites where people here will actually help you with your program and understand what it is doing rather than just giving out an answer.

True, he did help me previously and I'm not knocking that, but my response was to his last post. Besides, if he was surprised that I hadn't learned those things it still baffles me why he would harp on it and not try to figure out why we hadn't covered those items in class.

Additionally, he assumed that I had experience in C, which is not the case and probably the thing that bothered me the most. I actually agreed with him that I should have learned those things by now, but for some reason my professor haven't felt like they were important pieces of the curriculum.

I absolutely love this forum and all of the help I've received. Plus, I enjoy being able to help other people with any problems they might have when I have the knowledge to do so.

Anyway, I apologize to weakness for the whole meat bathing suit crack. It was out of line, but I would like to request that everyone be careful about the response they give because they can very easily be misconstrued, as was the case in this instance if he, in fact, had good intentions. This is especially true with users, like myself, who are just starting out. I'd like to believe that no one on any of these forums would like to be the reason that an individual lost interest in programming altogether.

[weaknessforcats]

To beacon:

No need to apologize.

One of my first instructors told me that C++ cannot be learned until you weep the necessary tears. He explained that the necessary tears occur late, late at night after you have been working on one problem for hours and finally, you slam you keyboard into your monitor, with tears in your eyes shouting: "Why won't this &^(^$* thing compile!!!". At that point, he said, you will reach the "teachable moment" and in that moment you will learn.

Stick with me, beacon, we have all been in your position and have great empathy for you.

[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.eof())), 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::InsertNode(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.
VVVVVVVVVVVVVVVVV
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???
VVVVVVVVVVVVVVVVVVVVVV
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