CODEWITHSUNDEEP
c#.netdata-structures
Wayne Bloss
Wayne Bloss

Reputation: 5550

Why isn't System...Stack<T> implemented as a Linked List?

I was looking through my code and I found a couple of extension methods that I wrote in order to remove items from a System.Collections.Generic.Stack. I was curious, so I looked at the source of Stack with Reflector and I can see that they implemented it as an array instead of a linked list and I'm just wondering why? With a linked list there would be no need to resize an internal array...

Here are my extensions, any criticisms or suggestions are welcome. Thanks.

public static Stack<T> Remove<T>(this Stack<T> stack, T item)
{
    Stack<T> newStack = new Stack<T>();

    EqualityComparer<T> eqc = EqualityComparer<T>.Default;

    foreach( T newItem in stack.Reverse() )
    {
        if( !eqc.Equals(newItem, item) )
        {
            newStack.Push(newItem);
        }
    }

    return newStack;
}
/// <summary>
/// Returns a new Stack{T} with one or more items removed, based on the given predicate.
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="stack"></param>
/// <param name="fnRemove"></param>
/// <returns>The new stack.</returns>
/// <remarks>
/// We have to turn tricks in order to save the LIFO order of the pool
/// since there is no built-in remove method since they implement a Stack internally
/// as an array instead of a linked list. Maybe they have a good reason, I don't know...
/// 
/// So, to fix this I'm just using a LINQ extension method to enumerate in reverse.
/// </remarks>
public static Stack<T> RemoveWhere<T>(this Stack<T> stack, Predicate<T> fnRemove)
{
    Stack<T> newStack = new Stack<T>();

    foreach( T newItem in stack.Reverse() )
    {
        /// Check using the caller's method.
        if( fnRemove(newItem) )
        {
            /// It's not allowed in the new stack.
            continue;
        }
        newStack.Push(newItem);
    }

    return newStack;
}

Upvotes: 4

Views: 470

Answers (3)

Jon Skeet
Jon Skeet

Reputation: 1502006

Consider the size of a Stack<byte> with 1,000,000 items.

  • With an array, size ~= 1,000,000 bytes. Usually more due to spare capacity, but probably not more than double.
  • With a linked list, each entry needs its own object, the data itself, and at least one reference (for a singly-linked list, which is probably all that's needed for a stack). With padding to 4 bytes, total size is likely to be ~16,000,000 bytes. Ouch.

Add to that the locality of reference and the reduced GC pressure, and I think it makes perfect sense to use arrays as the underlying data structure for stacks, queues and deques - the last two would use the array as a circular buffer, of course. The only obvious downsides are the wasted "spare capacity" and the need to copy everything when that capacity runs out.

Upvotes: 8

L. Cornelius Dol
L. Cornelius Dol

Reputation: 64056

A LIFO queue (a stack) is typically most efficient with an array, because you are pushing items onto the end of the array and pulling items off the same end of the array. So an array works well, without the memory and allocation overhead of a linked list. The cost of making and resizing an array is offset by not needing to create and garbage collect the list item wrapper objects.

Upvotes: 10

commondream
commondream

Reputation: 504

When you run benchmarks, you end up almost always end up seeing huge performance benefit in Array because of locality. The ArrayList puts everything into an array which is stored in a big contiguous block of memory. Linked lists store their data through links, and so end up with tons more memory allocations and also tons more jumping around in memory.

Upvotes: 3

Related Questions