Implementing Popback in constant time in a singly linked list

Question

I wanted to know if it was possible(It should be as std::list seems to do it) to implement a PopBack() operation on a singly linked list in constant time and how?

I am assuming that we store head and tail pointers. In such a case, PushBack(), PushFront(), PopFront() can be easily implemented in constant time. But can't think of the way to implement PopBack() with the same running time.

Answer 1

You can not implement pop_back for a single linked list in a constant time. To do this you need to know the previous element before the last that is the last element shall contain a reference to the previous element. If so then you will have a double linked list.

You can inplement push_back in a constant time. One of my proposals for C++ Standard was to introduce std::x_forward_list that will support push_back member function. In this case you will be able to use such a single linked list to simulate a queue.