Thread: 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"

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.

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