Thread: How do I remove the last node from a list, without having a prev pointer ?

  1. #1
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657

    How do I remove the last node from a list, without having a prev pointer ?

    The problem is that, for a singly linked list; I have no way of knowing which node will be the new 'end' (not end past 1) of the list.
    Here is the code...(The important portion is highlighted in red)

    Code:
    namespace mm
    {
        class list
        {
            class node;
        public:
            class iterator
            {
            public:
                iterator operator++(int)
                {
                    iterator result = iterator(n);
                    n=n->next;
                    return result;                
                };
                iterator operator++()
                {
                    n=n->next;
                    return iterator(n);
                }
                std::string operator*(){return n->val;};
                bool operator==(iterator it){return n==it.n;};
                bool operator!=(iterator it){return n!=it.n;};
                iterator(node* n_):n(n_){};
                
                friend class list;
            private:
                node* n;            
            };
            iterator begin(){return iterator(begin_sn->next);};
            iterator end(){return iterator(end_->next);};
            
            int size(){return size_val;}
            
            void push_back(std::string s)
            {
                node* new_node = new node(s);
                new_node->next = end_->next;
                end_->next = new_node;
                end_ = new_node;
                size_val++;
            }
            void push_front(std::string s)
            {
                node* new_node = new node(s);
                new_node->next = begin_sn->next;
                begin_sn->next = new_node;
                size_val++;
            }
            iterator insert(const std::string& s,iterator it)//inserts after 'it'
            {
                bool end_flag;
                node* new_node = new node(s);
                node* prev = it.n;
                end_flag = (prev==end_);
                new_node->next = prev->next;
                prev->next = new_node;
                if(end_flag)end_=new_node;
                size_val++;
                return iterator(new_node);
            }
            void remove(iterator it)
            {
                node* n = it.n;
                n->val = n->next->val;
                bool end_flag=(n==end_);
                node* temp = n->next->next;
                delete(n->next);
                n->next = temp;            
                if(end_flag)
                {
                    n->next = nullptr;n->sentinel=true;
                    //Have to set end_ here...which would be n's prev..
                }
                size_val++;
            }
            std::string eval();
            std::string car();//Returns the first element
            list cdr(); //Returns a list containing the last (size-1) elements.
            
            list(const std::string&);
            list(const std::vector<std::string>&);
            list(node* b_sn,node* e_);//Only for special friends !
            list():size_val(0)
            {
                begin_sn = new node();
                end_ = begin_sn;
                end_->next=new node();
            }
        private: 
            class node
            {
            public:
                node* next;
                bool sentinel;
                std::string val;
                node(std::string val_,node* next_=nullptr):next(next_),sentinel(false),val(val_){};
                node():next(nullptr),sentinel(true){};
            };
            node* begin_sn;//Sentinel node at the beginning
            node* end_;//Node before the end sentinel
            int size_val;
        };
    }
    Other criticism is more than welcome.
    (The last time I made a list.. it was a bit leaky....Does this fare better ?)
    [Note: This was originally a template... but I replaced Ts with std::string...because I found that I'd need the list for strings only]
    Last edited by manasij7479; 11-26-2011 at 11:16 PM.

  2. #2
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    I'm a bit confused. In std::list, erase() should delete the argument. You wrote delete(n->next); which to me implies that you pass in the thing just before what should be deleted. That's fine with me, but wouldn't n be the previous node you're looking for then?

  3. #3
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by whiteflags View Post
    I'm a bit confused. In std::list, erase() should delete the argument. You wrote delete(n->next); which to me implies that you pass in the thing just before what should be deleted. That's fine with me, but wouldn't n be the previous node you're looking for then?
    You misunderstood the logic..
    I can't delete n directly because I'd then need its previous mode's address to maintain the integrity of the list.
    To solve that problem..I take the next nodes data member in the current node ...and then delete the next ! ...(And of course assign the old next's next to the current 's new next)

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Have you drawn diagrams like this on paper?

    Code:
    +===+   +===+   +===+   +===+   +===+   +===+   
    | S |-->| 1 |-->| 2 |-->| 3 |-->| 4 |-->| E |
    +===+   +===+   +===+   +===+   +===+   +===+
    Where S and E are your sentinel nodes and 1 to 4 are your data nodes.

    Model on paper what it is you're trying to do.

    If you have sentinels, then all operations are the same anyway.
    There isn't anything special about the last node.

    I think you're stuck with having to scan the list again to find the predecessor in any case.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by Salem View Post
    I think you're stuck with having to scan the list again to find the predecessor in any case.
    That is what I was trying to avoid.
    The logic I have here successfully avoids this for operations anywhere in the middle...but for the end....it now seems I'd have to traverse the entire list again.

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    How is the middle different from the end?
    Especially when you have sentinels.

    If you figured out how to delete node 2, then why can't you use the same thing to delete 4 ?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  7. #7
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by Salem View Post
    How is the middle different from the end?
    Especially when you have sentinels.

    If you figured out how to delete node 2, then why can't you use the same thing to delete 4 ?
    In the middle... only removing the intended node and fixing the link is sufficient.
    But, for the end... Some extra steps are needed..
    Code:
    void remove(iterator it)
    {
           node* n = it.n;
           n->val = n->next->val;
           bool end_flag=(n==end_);
           node* temp = n->next->next;
           delete(n->next);
           n->next = temp;
           if(end_flag)
           {
                     n->next = nullptr;
                     n->sentinel=true;
                     //Have to set end_ here..to n's prev..
           }
           size_val++;
    }
    The steps within the if(...) aren't necessary for a node in the middle.
    "end_" is not the sentinel... "end_->next" is .
    Last edited by manasij7479; 11-27-2011 at 03:04 AM.

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    It looks like remove is intended to remove the next node. As such, the solution is simple: make it a pre-condition that remove shall not be called on an iterator to the last node, or make calls to remove on an iterator to the last node be a no-op. That said, you will need to provide some other way to remove the first node.
    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

  9. #9
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by laserlight View Post
    It looks like remove is intended to remove the next node. As such, the solution is simple: make it a pre-condition that remove shall not be called on an iterator to the last node, or make calls to remove on an iterator to the last node be a no-op. That said, you will need to provide some other way to remove the first node.
    No it does not remove the next node.
    It changes the present node to carry the value of the next node...and then deletes the next node...
    That makes it look like that the node to which the iterator is given...is deleted.

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Oh yeah, I missed that. However, then this means that removing a node invalidates iterators and references to the next node, which is strange for a linked list.
    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

  11. #11
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by laserlight View Post
    Oh yeah, I missed that. However, then this means that removing a node invalidates iterators and references to the next node, which is strange for a linked list.
    The node class is private to the list and no one outside will see it.
    As for invalidating the iterator....Why do you think so ?.. The iterator passed into it is a copy...even if its parent is used..it would point to the 'next' of the deleted node.

    This way of removing in constant time was the best I could come up with (except that it fails for the last node(...by fails... I mean ..it appears if the last node is emptied instead of being removed))
    ....Any other ideas ?

  12. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by manasij7479
    As for invalidating the iterator....Why do you think so ?.. The iterator passed into it is a copy...even if its parent is used..it would point to the 'next' of the deleted node.
    Suppose I have two iterators: one points to the first node and the other points to the second node. I use remove on the iterator to the first node, then access the iterator to the second node. What happens?

    Quote Originally Posted by manasij7479
    This way of removing in constant time was the best I could come up with (except that it fails for the last node(...by fails... I mean ..it appears if the last node is emptied instead of being removed))
    ....Any other ideas ?
    You could copy of the interface of SGI's slist:
    Slist provides the member functions insert_after and erase_after, which are constant time operations: you should always use insert_after and erase_after whenever possible. If you find that insert_after and erase_after aren't adequate for your needs, and that you often need to use insert and erase in the middle of the list, then you should probably use list instead of slist.
    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

  13. #13
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by laserlight View Post
    Suppose I have two iterators: one points to the first node and the other points to the second node. I use remove on the iterator to the first node, then access the iterator to the second node. What happens?
    Flight Simulators !
    You could copy of the interface of SGI's slist:
    Wouldn't erase_after have the same problem with invalidating iterators which used to point to the 'after' in question?

  14. #14
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by manasij7479
    Wouldn't erase_after have the same problem with invalidating iterators which used to point to the 'after' in question?
    No, because it is clear that the next node is to be erased, so it is to be expected that iterators to that node will be invalidated.
    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

  15. #15
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    If I make the remove function to remove the one next to the passed node..
    Should I change the begin() to return an iterator to the front sentinel instead of the first node containing a value?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 7
    Last Post: 11-04-2010, 01:18 PM
  2. Replies: 0
    Last Post: 09-16-2008, 05:04 AM
  3. Linked List remove node issue
    By prihod in forum C Programming
    Replies: 1
    Last Post: 04-19-2008, 09:54 AM
  4. traversing a linked list with a node and list class
    By brianptodd in forum C++ Programming
    Replies: 2
    Last Post: 04-24-2003, 11:57 AM
  5. Replies: 5
    Last Post: 10-04-2001, 03:42 PM