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.