Linked list vs. dynamic array for implementing a stack

Question

I've started reviewing data structures and algorithms before my final year of school starts to make sure I'm on top of everything. One review problem said "Implement a stack using a linked list or dynamic array and explain why you made the best choice".

To me, it seemed more intuitive to use a list with a tail pointer to implement a stack since it may need to be resized often. It seems like for a large amount of data, a list is the better choice since a dynamic array re-size is an expensive operation. Additionally, with a list, you don't need to allocate any more space than you actually need so it's more space efficient.

However, a dynamic array would definitely allow for adding data far quicker (except when it needs to be resized). However, I'm not sure if using an array is overall quicker, or only if it doesn't need to be resized.

The book's solution said "for storing very large objects, a list is a better implementation" but I don't understand why.

Which way is best? What factors should be used to determine which implementation is "best"? Also, is any of my logic here off?

Solution 1

There are many tradeoffs involved here and I don't think that there's a "correct" answer to this question.

If you implement the stack using a linked list with a tail pointer, then the worst-case runtime to push, pop, or peek is O(1). However, each element will have some extra overhead associated with it (namely, the pointer) that means that there is always O(n) overhead for the structure. Additionally, depending on the speed of your memory allocator, the cost of allocating new nodes for the stack might be noticeable. Also, if you were to continuously pop off all the elements from the stack, you might have a performance hit from poor locality, since there is no guarantee that the linked list cells will be stored contiguously in memory.

If you implement the stack with a dynamic array, then the amortized runtime to push or pop is O(1) and the worst-case cost of a peek is O(1). This means that if you care about the cost of any single operation in the stack, this may not be the best approach. That said, allocations are infrequent, so the total cost of adding or removing n elements is likely to be faster than the corresponding cost in the linked-list based approach. Additionally, the memory overhead of this approach is usually better than the memory overhead of the linked list. If your dynamic array just stores pointers to the elements, then the memory overhead in the worst-case occurs when half the elements are filled in, in which case there are n extra pointers (the same as in the case when you were using the linked list), and in the best case when the dynamic array is full there are no empty cells and the extra overhead is O(1). If, on the other hand, your dynamic array directly contains the elements, the memory overhead can be worse in the worst-case. Finally, because the elements are stored contiguously, there is better locality if you want to continuously push or pop elements from the stack, since all the elements are right next to each other in memory.

In short:

• The linked-list approach has worst-case O(1) guarantees on each operation; the dynamic array has amortized O(1) guarantees.
• The locality of the linked list is not as good as the locality of the dynamic array.
• The total overhead of the dynamic array is likely to be smaller than the total overhead of the linked list, assuming both store pointers to their elements.
• The total overhead of the dynamic array is likely to be greater than that of the linked list if the elements are stored directly.

Neither of these structures is clearly "better" than the other. It really depends on your use case. The best way to figure out which is faster would be to time both and see which performs better.

Hope this helps!

Solution 2

Well, for the small objects vs. large objects question, consider how much extra space to use for a linked list if you've got small objects on your stack. Then consider how much extra space you'll need if you've got a bunch of large objects on your stack.

Next, consider the same questions, but with an implementation based on dynamic arrays.

Solution 3

What matters is the number of times malloc() gets called in the course of running a task. It could take from hundreds to thousands of instructions to get you a block of memory. (The time in free() or GC should be proportional to that.) Also, keep a sense of perspective. This might be 99% of the total time, or only 1%, depending what else is happening.

Solution 4

I think you answered the question yourself. For a stack with a large number of items, the dynamic array would have excessive overhead costs (copying overhead) when simply adding an extra item to the top of the stack. With a list it's a simple switch of pointers.

Solution 5

Resizing the dynamic array would not be an expensive task if you design your implementation well.

For instance, to grow the array, if it is full, create a new array of twice the size, and copy items.

You will end up with an amortized cost of ~3N for adding N items.

View more solutions

Comments

[Casey Patton]

So, for a dynamic array where you have to leave extra space to avoid resizing often, when using large objects that means a LOT of extra space needs to be left. On the other hand, with lists you don't have to leave any extra space which makes lists a better choice if the objects are very large. That seem right?

[Pillsy]

Well, you need some extra space if you're using a linked list, since each link takes up space.

[Baroudi Safwen]

Bravo for mentioning locality, I think it is the winning argument in favor of dynamic arrays.

[Leonid Vasilev]

The total overhead of the dynamic array is likely to be greater than that of the linked list if the elements are stored directly. What do you mean by "stored directly"?

[templatetypedef]

@Leonid Vasilyev I’m envisioning a C or C++ style array where the array elements are stored directly inside the array, rather than, say, a Java or Python array where the array holds references to the actual elements.

[Leonid Vasilev]

But instance of value type probably will occupy same amount of address space regardless of it's container (dynamic array or linked list node), doesn't it?

[templatetypedef]

@LeonidVasilyev Let's say you have n elements stored. Imagine you have a dynamic array where the backing array has size 2n (perhaps you just recently doubled the size of the array.) The total memory you need is going to be roughly one pointer (to know where the array is), two integers (to know the size and capacity), and 2n * sizeof(entry) bytes for storage space for those items. Total is 2n * sizeof(entry) + 3 * sizeof(pointer). For a linked list, you have n * sizeof(entry) bytes for the elements, plus n * sizeof(pointer) bytes for pointers. Totaly is n * (sizeof(entry) + sizeof(pointer).

[templatetypedef]

@LeonidVasilyev The difference here is that the linked list only allocates space for the actual entries when it needs to. This means that if you have a linked list of very large objects and compare it to a dynamic array of very large objects, you'll find that n * (sizeof(entry) + sizeof(pointer)) < 2n * sizeof(entry) + 3 * sizeof(pointer), and end up saving space.