When making stacks and queues I was wondering what's better to use an array or a linked list, and why.
Printable View
When making stacks and queues I was wondering what's better to use an array or a linked list, and why.
I just wondering which one would be more efficient overall and increase ease in popping and peeking
>>I just wondering which one would be more efficient overall and increase ease in popping and peeking
I don't know about everyone else, but I would prefer to use the built in stack<T> and queue<T> classes in <stack> and <queue>. But the obvious solution isn't always the right one, so I could be wrong, its happened before. :-)
I owuld prefer using a linked list.. Because once space is allocated for an array it cannot be increased.. And if you dont use all of the array space.. you are wasting memory resource.. All this is solved using Linked List.... in a way it is more scalable....
The only thing you have to take care is you have to make sure to unallocate the temp pointers you have created....
Maybe a mix would work. Each link in the list would consister of any array of X many objects.
This way you don't have to malloc each time around.
Where this might cause problems is if you are using it like a linked list instead of a queue/stack where you can add/remove objects in the middle or what not. If you are worried about order then you are going to get holes in it.
However, if the order in which objects are added and removed is not important to you (this would be for a non stack/queue situation) Then when you remove and object you can always take the last object and use it it to fill in the hole made by removing the other object.
Whatever floats your boat I guess.
a linked list is MUCH bigger than an array.Quote:
Originally posted by vasanth
I owuld prefer using a linked list.. Because once space is allocated for an array it cannot be increased.. And if you dont use all of the array space.. you are wasting memory resource.. All this is solved using Linked List.... in a way it is more scalable....
The only thing you have to take care is you have to make sure to unallocate the temp pointers you have created....
Why? Because oft the next and prev pointer (plus the first and last).
normally you have also a data pointer, that makes
n*sizeof(your data)+(n*3+2)*sizeof(pointer)
an array only uses
n*sizeof(your data)+1*sizeof(pointer)
that may be significant
array or list - it depends on what you need...
well in real applications.. when the que is veryy big.. Linked list really saves sapce.. Consider a que or stack which has to acomodate say 2000 elements.. Like an dense index to a database... Then an array would be wasting space... If the user is not utilising all the 2000 array space.. And consider the user has to add the 2001 element.. it is a big problem.. Linked list does away with all these problems...
There are a lot of good Data Structrues And Algorithm Analysis texts that answer this question!!