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]

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?

Originally Posted by whiteflags

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)

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.

Originally Posted by Salem

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.

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 ?

Originally Posted by Salem

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 .

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.

Originally Posted by laserlight

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.

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.

Originally Posted by laserlight

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 ?

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?

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.

Originally Posted by laserlight

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?

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.

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?