linked list problem

This is a discussion on linked list problem within the C++ Programming forums, part of the General Programming Boards category; Hello this is my first post. I am making a linked list. The problem is that whenever I try to ...

  1. #1
    Registered User help_seed's Avatar
    Join Date
    Nov 2009
    Posts
    13

    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"
    Last edited by help_seed; 11-23-2009 at 05:44 PM. Reason: added last line

  2. #2
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    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.

  3. #3
    Registered User help_seed's Avatar
    Join Date
    Nov 2009
    Posts
    13
    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?

  4. #4
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    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.

  5. #5
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,236
    Quote Originally Posted by nadroj View Post
    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.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  6. #6
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    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).

  7. #7
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,236
    Quote Originally Posted by nadroj View Post
    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.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,296
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Registered User help_seed's Avatar
    Join Date
    Nov 2009
    Posts
    13
    Quote Originally Posted by iMalc View Post
    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;

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,454
    Quote 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.

    Quote 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
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User help_seed's Avatar
    Join Date
    Nov 2009
    Posts
    13
    thanks guys got things straightened out

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  2. Replies: 6
    Last Post: 03-02-2005, 01:45 AM
  3. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 07:11 AM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 05:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21