为什么不是System ... Stack <T>实现为链接列表？

我正在查看我的代码,我发现了一些扩展方法,我为了从System.Collections.Generic.Stack中删除项目而编写.我很好奇,所以我看了Stack with Reflector的来源,我可以看到他们将它实现为数组而不是链表,我只是想知道为什么？使用链表,不需要调整内部数组的大小......

以下是我的扩展,欢迎任何批评或建议.谢谢.

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

    EqualityComparer eqc = EqualityComparer.Default;

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

    return newStack;
}
/// 

/// Returns a new Stack{T} with one or more items removed, based on the given predicate.
/// 
/// 
/// 
/// 
/// The new stack.
/// 
/// 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.
/// 
public static Stack RemoveWhere(this Stack stack, Predicate fnRemove)
{
    Stack newStack = new Stack();

    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;
}

Lawrence Dol.. 10

LIFO队列(堆栈)通常对数组最有效,因为您将项目推送到数组的末尾并从项目的同一端拉出项目.因此,数组运行良好,没有链表的内存和分配开销.通过不需要创建和垃圾收集列表项包装器对象来抵消制作和调整数组大小的成本.

LIFO队列(堆栈)通常对数组最有效,因为您将项目推送到数组的末尾并从项目的同一端拉出项目.因此,数组运行良好,没有链表的内存和分配开销.通过不需要创建和垃圾收集列表项包装器对象来抵消制作和调整数组大小的成本.

考虑Stack包含1,000,000个项目的a的大小.

使用数组,大小〜= 1,000,000字节.通常更多是由于备用容量,但可能不会超过两倍.

使用链表,每个条目都需要自己的对象,数据本身和至少一个引用(对于单链表,这可能是堆栈所需的全部内容).填充为4个字节,总大小可能为~16,000,000个字节.哎哟.

再加上引用的局部性和降低的GC压力,我认为使用数组作为堆栈,队列和deques的底层数据结构是完全合理的 - 当然,最后两个将使用数组作为循环缓冲区.唯一明显的缺点是浪费的"备用容量"以及在容量耗尽时复制所有内容的需要.