What's better

This is a discussion on What's better within the C++ Programming forums, part of the General Programming Boards category; When making stacks and queues I was wondering what's better to use an array or a linked list, and why....

  1. #1
    Registered User
    Join Date
    Jan 2003
    Posts
    3

    What's better

    When making stacks and queues I was wondering what's better to use an array or a linked list, and why.

  2. #2
    Registered User
    Join Date
    Jan 2003
    Posts
    3

    Clarification

    I just wondering which one would be more efficient overall and increase ease in popping and peeking

  3. #3
    Registered User Cela's Avatar
    Join Date
    Jan 2003
    Posts
    362
    >>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. :-)
    *Cela*

  4. #4
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683
    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....

  5. #5
    Registered User
    Join Date
    Nov 2002
    Posts
    491
    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.

  6. #6
    Registered User
    Join Date
    Dec 2001
    Posts
    88
    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....
    a linked list is MUCH bigger than an array.
    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...
    Hope you don't mind my bad english, I'm Austrian!

  7. #7
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683
    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...

  8. #8
    CS Author and Instructor
    Join Date
    Sep 2002
    Posts
    511

    Wink

    There are a lot of good Data Structrues And Algorithm Analysis texts that answer this question!!
    Mr. C: Author and Instructor

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21