Thread: linked list

  1. #1
    Registered User
    Join Date
    Apr 2011
    Posts
    22

    linked list

    Code:
    //--- Definition of push()
    void Stack::push(const StackElement & value)
    {
       Stack::NodePointer ptr;
       if(value%2==0)
            first = new Stack::Node(value, first);
        else{
            ptr = first;
            while(ptr != 0)
            ptr = new Stack::Node(value, NULL);
        }
    }
    I need to write a function that will create new nodes as the user inputs values for them. The even values are supposed to be put into nodes on one end and the odd values are supposed to be put into nodes on the other end. My program was working fine when I was accepting all values the same way but with the if else statement it will only let me enter two or three numbers. This is the first time I have tried to create a linked list so any help would be greatly appreciated. THANK YOU!

    (typedef int StackElement;
    typedef Node * NodePointer)

  2. #2
    Registered User
    Join Date
    Apr 2011
    Posts
    22
    I realized i didn't have
    Code:
            ptr = ptr->next;
    in my for loop but now I am not getting any odd data back when I call display?
    Here is the function for display as well
    Code:
    //--- Definition of push()
    void Stack::push(const StackElement & value)
    {
       Stack::NodePointer ptr;
       if(value%2==0)
            first = new Stack::Node(value, first);
        else{
            ptr = first;
            while(ptr != 0){
            ptr = ptr->next;
            }
            ptr = new Stack::Node(value, NULL);
        }
    }
    
    //--- Definition of display()
    void Stack::display(ostream & out) const
    {
       Stack::NodePointer ptr;
       for (ptr = first; ptr != 0; ptr = ptr->next)
          out << ptr->data << endl;
    }

  3. #3
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    In your while loop to find the end of the list you need to keep the previous ptr and set its next pointer to the new node.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  4. #4
    Registered User
    Join Date
    Apr 2011
    Posts
    22
    Quote Originally Posted by oogabooga View Post
    In your while loop to find the end of the list you need to keep the previous ptr and set its next pointer to the new node.
    Code:
    ptr->next = new Stack::Node(value, NULL);
    like this?
    my program crashes when it tries to execute this line

  5. #5
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    No. You have to keep the previous ptr value in your loop, otherwise once the loop has ended ptr is 0, which of course you can't dereference as you're attempting with the arrow operator.

    So something like this:
    Code:
            ptr = first;
            while (ptr != 0) {
                prev = ptr;
                ptr = ptr->next;
            }
            prev = new Stack::Node(value, 0);
    Although this does not take care of the case where first is 0, if that is possible in your design. So it might fail if the first number you enter is odd. I'll leave that to you.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  6. #6
    Registered User
    Join Date
    Apr 2011
    Posts
    22
    Quote Originally Posted by oogabooga View Post
    No. You have to keep the previous ptr value in your loop, otherwise once the loop has ended ptr is 0, which of course you can't dereference as you're attempting with the arrow operator.

    So something like this:
    Code:
            ptr = first;
            while (ptr != 0) {
                prev = ptr;
                ptr = ptr->next;
            }
            prev = new Stack::Node(value, 0);
    Although this does not take care of the case where first is 0, if that is possible in your design. So it might fail if the first number you enter is odd. I'll leave that to you.


    okay thanks that makes sense but even with the new Stack being set to prev I'm still not receiving any odd integers in the output. Whether or not I put them at the begining, the end, or somewhere in the middle they aren't being printed in my display.

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    What is your current code?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Registered User
    Join Date
    Apr 2011
    Posts
    22
    Code:
    //--- Definition of push()
    void Stack::push(const StackElement & value)
    {
       Stack::NodePointer ptr;
       Stack::NodePointer prev;
       if(value%2==0)
            first = new Stack::Node(value, first);
        else{
        ptr = first;
        while (ptr != 0) {
            prev = ptr;
            ptr = ptr->next;
        }
            prev = new Stack::Node(value, 0);
        }
    }
    
    //--- Definition of display()
    void Stack::display(ostream & out) const
    {
       Stack::NodePointer ptr;
       for (ptr = first; ptr != 0; ptr = ptr->next)
          out << ptr->data << endl;
    }

  9. #9
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Oops. I meant to say:
    Code:
    prev->next = new Stack::Node(value, 0);
    But remember that you still have to add special processing for the case that first is 0.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by lancehumiston
    The even values are supposed to be put into nodes on one end and the odd values are supposed to be put into nodes on the other end.
    Why is this class named Stack when elements are being inserted at both ends? It sounds like you are really dealing with say, a double ended queue.

    The NodePointer typedef (?) is not useful here. You should also indent your code properly, e.g.,
    Code:
    //--- Definition of push()
    void Stack::push(const StackElement& value)
    {
        Stack::Node* ptr;
        Stack::Node* prev;
        if (value % 2 == 0) {
            first = new Stack::Node(value, first);
        } else {
            ptr = first;
            while (ptr != 0) {
                prev = ptr;
                ptr = ptr->next;
            }
            prev = new Stack::Node(value, 0);
        }
    }
     
    //--- Definition of display()
    void Stack::display(ostream& out) const
    {
        Stack::Node* ptr;
        for (ptr = first; ptr != 0; ptr = ptr->next) {
            out << ptr->data << endl;
        }
    }
    Now, my concern is this: how is first initialised? If you don't initialise it properly and handle the case of the double ended queue being empty, then you're in for a potential problem.

    Another thing to think about: write a member function to insert at the front of the double ended queue. Write another member function to insert at the back of the double ended queue. Then, write a non-member function that takes the double ended queue and the value to insert, and then depending on whether the value is odd or even, calls the appropriate member function to insert. This separation of concerns makes your double ended queue more reusable, and you can test the functionality separately.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 05-01-2010, 10:19 PM
  2. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  3. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 06:37 PM
  4. bi-linked list based on one-way linked list
    By ronenk in forum C Programming
    Replies: 1
    Last Post: 03-04-2005, 08:16 AM
  5. Replies: 6
    Last Post: 03-02-2005, 02:45 AM

Tags for this Thread