Member Avatar for cool1_best1

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?

  • 5 Contributors
  • 6 Replies
  • 153 Views
  • 11 Months Discussion Span
  • Latest Post Latest Post by mitrmkar
Member Avatar for skatamatic

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.

Member Avatar for cool1_best1

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?

Member Avatar for skatamatic

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?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.