===
As for difference between stack and linked list implementation, apart from being different paradigms, i see it as following:
�� linked list basically 'declares' that items can easily access neighboring ones through direct reference (hence links),
in stack, there's no any assumption whether items be able to see each other or not.
For single linked list, it requires tracking only head. For efficiency, one might track tail pointer as well, but it is not necessary for correct implementation.
Also, linked list structure allows very quick (O(1)) implementation for insertion/deletion items in the middle of it.
While for stack, inserting/deleting in the middle is a nonsense. And i would really execute anyone who using such behavior simply because Stack is a subclass of LinkedList :)
IMO, for stack a more efficient memory structure would be
[ buffer array of items ] + stack pointer.
As benefit, accessing items down the stack will be a simple indexing O(1) procedure, which is sometimes useful. Apparently, linked list is less efficient in this regard, since it will require interation.
The (ever) growing array size is not an issue here, since by its purpose, stack serves as a special data exchange structure, that dynamically pipes things through itself, and always consumed fully at the end. So we can expect that
��most algorithms is normally very quickly settling down with stack max size, and then there's no need for frequent reallocation of stack buffer.
I would also expect that stacks are never too deep: if it is, this might be an indication of using wrong data structure.