Which is more efficient in terms of time complexity & space complexity: stacks using array or stacks using linked lists (for large data) & why? Please explain in as much detail as possible.
Like why there is a need to implement stacks using linked lists if we already got the efficient solution using arrays with constant time complexity? Someone said that we use linked list implementation for stacks because there is unnecessary indices & in built array methods but that doesn't get credited for more efficient way in terms of time complexity & also doesn't get credited in terms of memory usage as there is also enough memory usage for creating nodes in a linked list.
Please somebody help me understand this, or tell me somewhere if I'm thinking wrong.
I've already searched google but could find any good relevance for the same.
Well, your answer is simple if you want to work with constant size of data then array is the best way because you know the size of the array but if you don't know the size it is best to use linked list.
You may say that I will declare an array with maximum size or to the highest limit for your requirement, what if you are not storing that much data, then the memory will be wasted, also if the size of data is greater than declared value then you need to resize the array which is a costly operation in terms of both time & space.
Hence it is recommended to use linked list for dynamic sized data purpose, as the size doesn't matter in linked list also you are not wasting any memory in any case, you may use extra space for storing pointers but its kkk.
Hence Linked List is more efficient.Well arrays will use constant time for accessing the data using indices but you are using a lot of memory because of constant size.
For example:
You declared an array of size 1000 but you are only storing 100 elements in it. Is it memory efficient?
Your array will take 1000*(4) (for int)= 4000 bytes.
For storing hundred elements : 100*(4) = 400 bytes
Here you are wasting 3600 bytes of memory, is it kkk?
By using linked list 100*(4+4) = 800 bytes (4 bytes for data and 4 bytes for int pointer)
Here clearly linked list is very efficient.
The only thing is you cannot randomly access element in constant time.