linked list problem

Hello this is my first post.
I am making a linked list. The problem is that whenever I try to retrieve a value I get the value from the first node.

LinkedList.cpp

Code:

#include <iostream>

using namespace std;
/*constructor*/
List::List():head(NULL),length(0)//sets first heads pointer to null
{
    //remeber that head is not a node and does not contain any data
	//it simply points to the current first node
	//thus after the constructor is called, there trully still is no link list
}
    
/*destructor*/
List::~List()
{
    eraseAll();
}

void List::eraseAll()
{
    while(head != NULL)
    {
        NodePtr temp = head;
        head = head -> next;//the node pointed to by head, the value of next (which is an adress)
        delete temp;
    }//heads pointer is now null
}

bool List::isEmpty() const
{
    return head == NULL;//if head is null then the link list was just made, or deleteAll was just called or the list was lost (memorey leek)
}

unsigned int List::size() const
{
    int count = 0;//this means the first element (list) is at 0
    NodePtr toEnd = head;
    while(toEnd->next != NULL)
    {
        toEnd = toEnd->next;
        count++;
    }
    return count;
}
/*returns true upon sucess, otherwise false*/
bool List::insert(DataType item, unsigned int position)
{
	if(position > length)
		return false;//couldn't be inserted (would cause empty spaces in list)
	if(position == 0 && head == NULL)
	{
        cout<<"inisde insert"<<endl;
		head = new Node(item);
        cout<<"this is head "<<head<<endl;
		return true;
	}
    int count = 0;
    NodePtr temp = head;
    NodePtr previous;
	while(count != position)
	{
		previous = temp;
		temp = temp->next;
		count++;
	}//the new node should now be inserted after previous, and be followed by temp
	previous = new Node(item);
	previous->next->next = temp;
	length++;
    return true;
}

DataType List::get(unsigned int position) const
{
    NodePtr temp = head;
    if(head->next == NULL)//head's next is always null for some reason
        cout<<"head's screwed up"<<endl;
    unsigned int count = 0;
    cout<<"position: "<<position<<endl;
    while(count < position && temp->next != NULL)
    {
        count++;
        temp = temp->next;
    }

    cout<<"element from temp "<<temp->element<<endl;
    return temp->element;//problem occures here
}

this is the file I used to test it

tester.cpp

Code:

#include "LinkedList.h"
#include <iostream>

using namespace std;

int main()
{
    List aList = List();
    aList.insert(4.2, 0);
    aList.insert(22, 1);
    aList.insert(5,3);
    cout<<aList.get(3)<<endl;
    
    return 0;
}

for some reason head is always pointing to null. This confuses me because the only place I assign a variable the value of NULL is in the constructor.
actually I miss-spoke. Head is not pointing to null the first time I call the insert method, but it is pointing to null whenever I call the get method.

here it is again slimmed down:

Code:

#include <iostream>

using namespace std;

List::List():head(NULL),length(0)
{

}


/*returns true upon sucess, otherwise false*/
bool List::insert(DataType item, unsigned int position)
{
	if(position > length)
		return false;
	if(position == 0 && head == NULL)//it appears head is always true
	{
		head = new Node(item);
		return true;
	}
    int count = 0;
    NodePtr temp = head;
    NodePtr previous;
	while(count != position)
	{
		previous = temp;
		temp = temp->next;
		count++;
	}
	previous = new Node(item);
	previous->next->next = temp;
	length++;
    return true;
}

DataType List::get(unsigned int position) const
{
    NodePtr temp = head;
    unsigned int count = 0;
    while(count < position && temp->next != NULL)//this condition is never true
    {
        count++;
        temp = temp->next;
    }
    return temp->element;//problem occures here
}

tester.cpp

Code:

#include "LinkedList.h"
#include <iostream>

using namespace std;

int main()
{
    List aList = List();
	aList.insert(4.5, 0);
    aList.insert(22, 1);
    aList.insert(5,3);
    cout<<aList.get(3)<<endl;
    
    return 0;
}

LinkedList.h

Code:

#include <cstdlib>

typedef double DataType;

// our list is zero based, that is, the first element in the list is in position 0.

class List
{
    public:
        List();
        List(const List & rhs);
        List& operator=(const List & rhs);
        bool insert (DataType item, unsigned int position);
        DataType get(unsigned int position) const;
#ifndef NDEBUG
#endif
    private:
        struct Node
        {
            DataType element;
            Node* next;
            Node(DataType item):element(item),next(NULL){}
        };
        typedef List::Node * NodePtr;

        NodePtr head;//private field
		unsigned int length;
};
#include "LinkedList.cpp"

If you cant "get" something correctly, it is probably a hint that stuff isnt being "put" properly. I would change the insert from

Code:

    NodePtr temp = head;
    NodePtr previous;
	while(count != position)
	{
		previous = temp; // this line doesnt do anything, because outside the loop you overwrite its value
		temp = temp->next;
		count++;
	}
	previous = new Node(item);
	previous->next->next = temp;
	length++;

to something like

Code:

    NodePtr temp = head;
    NodePtr next; //rename to next, as you add nodes after (to end), not before
	while(temp->next != null)
	{
		temp = temp->next;
		count++;
	}
	next = new Node(item);
	temp->next = next;
	length++;

Give that a try.

Also, there are at least two places where you use "head->next" (or "temp->next") without checking if "head" (or "temp") is null first, meaning a segfault when it is null. Also, I havent really looked at your "get", but try and fix the insert first as theres a problem in it. The get should be straightforward though.

ok thanks, I think I got it working now.
one problem was that I forgot to increase the size (length++) in the case that there were 0 elements in my length.

I don't want to start a whole new thread for this question, but in c++ what do you call the source code with the main function in it? In Java it would be called main class so in c++ is it called main source code or something?

one problem was that I forgot to increase the size (length++) in the case that there were 0 elements in my length.

One thing I noticed is that you have a "size" function which iterates through the list to determine the size, however youre also keeping track of the size with the "length" variable. Doesnt it make sense for "size" to simply "return length"? Iterating through the array is wasted time each time the "size" function is called, since you (should) already know the "length" because youre keeping track of it--youre "re-inventing the wheel". Not that its taking that much time--the point is to remember that you made this "mistake" before and try not to repeat it! That is, if you were working on a very large and complex program, function calls might start to add up, so doing something unnecessarily like this will certain slow down the overall time. Just keep things like this in mind for the future.

in c++ what do you call the source code with the main function in it?

I dont think there is a technical term for it, in any language--including Java. The most common thing Ive heard it called is a "driver" class, it "drives" the program. I certainly wouldnt get caught up on those details, if you are.

Originally Posted by nadroj

That is, if you were working on a very large and complex program, function calls might start to add up, so doing something unnecessarily like this will certain slow down the overall time. Just keep things like this in mind for the future.

In a large, complex project, that sort of "double dimensioning" usually leads to more problems than it solves. Maintaining the length of the list in a variable is an optimization. The same piece of data now exists in two places: the list itself (insofar as it can be computed by traversing the list), and the variable. Any change to either the list or the variable needs to maintain consistency.

Generally, data should be computed from other data when necessary, not cached. Caching is purely an optimization and should only be done if there is clear proof that it's necessary.

I was trying to emphasize large and complex and be general.

- "large and complex": huge datasets where its not practical to calculate things like this each time it is needed. If the class is designed properly, with the principle of "information hiding" followed, then the only way the list/container/<whatever data structure> is modified is through the class' functions, which can maintain other information (i.e. a size). For example, some server program might keep track of how many connections it has. If it was some high-traffic server say some popular web server, it makes sense to stop accepting connections when it reaches the max that it keeps track of. It does not make sense for it to waste precious CPU cycles iterating through a list each time it needs to check if it can accept another connection or not. The small overhead of doing an increment or decrement, i.e. O(1)-time, is better than the O(n) time doing it the other way.

- "general"/generic: Meaning not specifically this topic. I meant to keep an eye out for things like this, where you might be doing more work than you have to (wasting your own time), or might be doing more work for whoever is using the program (wasting their time).

Originally Posted by nadroj

I was trying to emphasize large and complex and be general.

- "large and complex": huge datasets where its not practical to calculate things like this each time it is needed. If the class is designed properly, with the principle of "information hiding" followed, then the only way the list/container/<whatever data structure> is modified is through the class' functions, which can maintain other information (i.e. a size). For example, some server program might keep track of how many connections it has. If it was some high-traffic server say some popular web server, it makes sense to stop accepting connections when it reaches the max that it keeps track of. It does not make sense for it to waste precious CPU cycles iterating through a list each time it needs to check if it can accept another connection or not. The small overhead of doing an increment or decrement, i.e. O(1)-time, is better than the O(n) time doing it the other way.

It's true that encapsulation can HELP maintain the correctness of these sorts of optimizations. But somebody still needs to write and maintain the code, maybe not the original author.

Coding a hack is usually a sign that the data has been organized in the wrong way to begin with. In your specific example I can think of no compelling reason to use a linked list to store some fixed number of items.

The best thing you can do when writing something like this which is kinda new to you, is to step through the code line by line, watching what the effect of every statement is in the debugger. Your understanding will go up tenfold!

If you're going to program for any decent length of time, you're going to need some good debugging skills anyway, and there's no better way to practice. You wont find any top-notch programmer that isn't intimately familiar with a debugger or two.

Originally Posted by iMalc

You wont find any top-notch programmer that isn't intimately familiar with a debugger or two.

What IDE would you recommend for a beginner like me? Right now I'm using Scite.

can anyone see what I'm doing wrong here? Some times it works "fine". Other times it stops after printing "after for loop". I always get an error (from the OS) and the exit code -1073741819

Code:

        NodePtr temp1 = head;
        NodePtr temp2;
        cout<<"before for loop"<<endl;
        for(int i = 1; i < position; i++)
        {
            temp2 = head;
            temp1 = temp1->next;
        }
        cout<<"after for loop"<<endl;
        temp2->next = temp1->next;
        cout<<"before delete"<<endl;
        delete temp1;
        cout<<"after delete"<<endl;

Originally Posted by help_seed

What IDE would you recommend for a beginner like me? Right now I'm using Scite.

Apparently there is an extension for scite that will allow you to use the gdb debugger from scite: SciteDebug.

Originally Posted by help_seed

can anyone see what I'm doing wrong here? Some times it works "fine". Other times it stops after printing "after for loop". I always get an error (from the OS) and the exit code -1073741819

I would be wary of dereferencing null pointers, e.g., there is no check if temp1 is not a null pointer. Of course, a debugger would help you to debug such problems

thanks guys got things straightened out