NSMutableArray当从数组的末端添加/删除元素（例如removeAtObject:0or ）时，我已经读过某处将具有 O(1) 性能而不是 O(n)，removeLastObject这使得它适合用作堆栈或队列 - 否定了需要为这些容器类型创建 LinkedList 实现。
真的是这样吗？如果是这样，Apple 是如何做到这一点的？如果不是，是否有任何证据表明在任一端添加/删除元素所花费的时间NSMutableArray实例的任一端添加/删除元素所需的时间会随着数组中元素数量的增加而增加？
PS：由于NSMutableArray本质上是CFArray（它是“纯C”对应物），并且源代码CFArray是 open，因此应该可以检查其内部工作原理。
_NSArrayM（在大多数 NSArrays 中用于代替 CFArray）目前是一个数组双端队列，它确实在两端提供了分摊的 O(1) 推送/弹出
（这不保证在任何过去或未来的操作系统版本上都是这种方式。例如，NSArrayM 本身是相当新的）
CFArray/ CFMutableArray（并且通过扩展，NSArray/ NSMutableArray）具有非常松散的性能保证——它们当然不保证 O(1) 插入/删除性能。
来自CFArray.h（强调添加）：
计算复杂性
对于当前和未来的任何实现，数组中值的访问时间保证在最坏情况下为 O(lg N)，但通常为 O(1)（恒定时间）。线性搜索操作同样具有 O(N*lg N) 的最坏情况复杂度，但通常边界会更紧，依此类推。插入或删除操作通常在数组中的值数量上是线性的，但在某些实现中，在最坏的情况下显然可能是 O(N*lg N)。阵列中没有性能偏好的位置；也就是说，访问具有低索引的值，或者插入或删除具有高索引的值，或其他任何东西，不一定更快。
Core Foundation/Foundation 目前不提供任何模拟链表性能的数据结构。
如果数据存储单独使用（即不用作树/数组控制器的后备存储），则可能值得使用 Obj-C++ 并使用任何 STL/boost 容器。