We are using a singly linked list with head pointer to implement Stack ADT. The stack top is maintained at the end of the linked list, i.e. stack top is the last item. Discuss whether this is a good design in term of time efficiency:
In a stack of N-items, how fast can you access the stack top? Push or pop?

If we add a tail pointer to the implementation. Is this a good idea looking at:
1. In a stack of N-items, how fast can you get the stack top item?
2. To push or pop an item to an N-items stack, how fast can you do it?

We are using a singly linked list with head pointer to implement Stack ADT. The stack top is maintained at the end of the linked list, i.e. stack top is the last item. Discuss whether this is a good design in term of time efficiency:
In a stack of N-items, how fast can you access the stack top? Push or pop?

If we add a tail pointer to the implementation. Is this a good idea looking at:
1. In a stack of N-items, how fast can you get the stack top item?
2. To push or pop an item to an N-items stack, how fast can you do it?

Linked lists are always the slower option, as all items must be iterated to find the end. A well written hash table or binary map will give you the speed you seem to be looking for.

Hi
sorry didnt read the rules properly..
Well the question is for C++ stacks..

I think that if the stack top is maintained at the end of the linked list, i.e. stack top is the last item, accessing the stack top would take a lot of time, since N items of the linked list need to be traversed before we can access the last item, and push or pop.

However, if we add a tail pointer to the linked list, the implementation will then be efficient, as we can directly access the last item now.
Am I on the right track?

If it's a double linked-list it would make finding items past the half-way node more efficient,if you knew you where specifically looking at the end of the list, but finding an item in the middle would require the same amount of iterations as before. When would you need to specifically access the last item in a linked list?

This article has been dead for over six months. Start a new discussion instead.