C++ stack implementation using linked list

[cool1_best1]

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, This would require N-1 hops. Hence, implementing pop or push in the stack would take more time.

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?

But for both cases, how fast can I get to the stack top item? and how fast can I pop or push?

[Freaky_Chris]

You were correct, in the fist cast it would take O(N+1) time to push/pop, since it would be N for traversal and 1 for the push/pop.
In the second case it would be O(1) since you already have the last element.

Chris

[cool1_best1]

Thanks a lot :)

One small thing, can you please clarify what is O(N+1). Is it the output into N+1 time taken.. Thanks so much

[death_oclock]

O(N...whatever) is Big O Notation. It is a way of expressing the efficiency (often the "worst case" efficiency) of an algorithm based on the size of its input. O(N) is a linear efficiency, other common ones are O(N^2) and O(log(N)). Note that coefficients are not expressed; you would not say O(2N), just O(N).