对于O(1)随机存取，这是不可战胜的。

是时候回到过去上课了。虽然我们在今天的高级托管语言中没有过多地考虑这些事情，但它们都建立在相同的基础上，因此让我们看看在C中如何管理内存。

在我深入研究之前，先快速解释一下术语“指针”的含义。指针只是一个变量，它“指向”内存中的某个位置。它不包含这个内存区域的实际值，它包含它的内存地址。把一块内存看作一个邮箱。指针将是该邮箱的地址。

在C语言中，数组只是一个带偏移量的指针，偏移量指定在内存中查找的距离。这提供了O(1)访问时间。

  MyArray   [5]
     ^       ^
  Pointer  Offset

所有其他数据结构要么建立在此基础上，要么不使用相邻内存进行存储，从而导致较差的随机访问查找时间(尽管不使用顺序内存还有其他好处)。

例如，假设我们有一个数组，其中有6个数字(6,4,2,3,1,5)，在内存中它看起来是这样的:

=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================

在数组中，我们知道每个元素在内存中彼此相邻。一个C数组(这里称为MyArray)只是一个指向第一个元素的指针:

=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================
   ^
MyArray

如果我们想要查找MyArray[4]，内部会像这样访问它:

   0     1     2     3     4 
=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================
                           ^
MyArray + 4 ---------------/
(Pointer + Offset)

因为我们可以通过给指针加上偏移量来直接访问数组中的任何元素，所以不管数组的大小如何，我们都可以在相同的时间内查找到任何元素。这意味着获取MyArray[1000]将花费与获取MyArray[5]相同的时间。

另一种数据结构是链表。这是一个指针的线性列表，每个指针指向下一个节点

========    ========    ========    ========    ========
| Data |    | Data |    | Data |    | Data |    | Data |
|      | -> |      | -> |      | -> |      | -> |      | 
|  P1  |    |  P2  |    |  P3  |    |  P4  |    |  P5  |        
========    ========    ========    ========    ========

P(X) stands for Pointer to next node.

注意，我将每个“节点”放入自己的块中。这是因为它们在内存中不保证是相邻的(而且很可能不会)。

如果我想访问P3，我不能直接访问它，因为我不知道它在内存中的位置。我所知道的只是根(P1)在哪里，所以我必须从P1开始，并跟随每个指针指向所需的节点。

这是一个O(N)查找时间(随着每个元素的添加，查找成本也会增加)。与P4相比，P1000的成本要高得多。

更高级别的数据结构，如哈希表、堆栈和队列，都可以在内部使用一个数组(或多个数组)，而链表和二叉树通常使用节点和指针。

您可能想知道为什么有人会使用需要线性遍历的数据结构来查找值，而不只是使用数组，但它们有自己的用途。

再看我们的数组。这一次，我想找到包含值为'5'的数组元素。

=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================
   ^     ^     ^     ^     ^   FOUND!

在这种情况下，我不知道要给指针加上什么偏移量才能找到它，所以我必须从0开始，一直到找到它。这意味着我要进行6次检查。

因此，在数组中搜索一个值被认为是O(N)。随着数组变大，搜索成本也会增加。

还记得上面我说过有时使用非顺序数据结构有优势吗?搜索数据是这些优点之一，其中一个最好的例子是二叉树。

二叉树是一种类似于链表的数据结构，但不是链接到单个节点，而是每个节点可以链接到两个子节点。

         ==========
         |  Root  |         
         ==========
        /          \ 
  =========       =========
  | Child |       | Child |
  =========       =========
                  /       \
            =========    =========
            | Child |    | Child |
            =========    =========

 Assume that each connector is really a Pointer

当数据被插入到二叉树中时，它会使用一些规则来决定在哪里放置新节点。基本概念是，如果新值大于父值，则将其插入左侧，如果小于父值，则将其插入右侧。

这意味着二叉树中的值可能是这样的:

         ==========
         |   100  |         
         ==========
        /          \ 
  =========       =========
  |  200  |       |   50  |
  =========       =========
                  /       \
            =========    =========
            |   75  |    |   25  |
            =========    =========

当在二叉树中搜索值为75时，我们只需要访问3个节点(O(log N))，因为这样的结构:

75比100小吗?看右节点 75比50大吗?查看左节点 有75个!

尽管我们的树中有5个节点，但我们不需要查看剩下的两个节点，因为我们知道它们(及其子节点)不可能包含我们正在寻找的值。这给了我们一个搜索时间，在最坏的情况下意味着我们必须访问每个节点，但在最好的情况下，我们只需要访问节点的一小部分。

这就是数组被击败的地方，它们提供了一个线性的O(N)搜索时间，尽管有O(1)访问时间。

这是对内存中数据结构的一个非常高级的概述，跳过了许多细节，但希望它说明了与其他数据结构相比，数组的优点和缺点。

不是所有的程序都做同样的事情或在相同的硬件上运行。

这就是为什么存在各种语言特性的原因。数组是计算机科学的一个核心概念。将数组替换为列表/矩阵/向量/任何高级数据结构将严重影响性能，并且在许多系统中是完全不可行的。在许多情况下，由于所讨论的程序，应该使用其中一个“高级”数据收集对象。

在商业编程中(我们大多数人都做)，我们可以瞄准相对强大的硬件。在这些情况下，使用c#中的List或Java中的Vector是正确的选择，因为这些结构允许开发人员更快地完成目标，从而使这类软件更具特色。

在编写嵌入式软件或操作系统时，数组通常是更好的选择。虽然数组提供的功能较少，但它占用的RAM较少，而且编译器可以更有效地优化代码以查找数组。

我确信我遗漏了这些情况下的一些好处，但我希望你能明白这一点。

查看数组优势的一种方法是查看数组的O(1)访问能力在哪里是必需的，因此大写:

在应用程序的查找表中(用于访问特定分类响应的静态数组) 记忆(已经计算过复杂函数的结果，这样你就不用再计算函数值了，比如log x) 需要图像处理的高速计算机视觉应用(https://en.wikipedia.org/wiki/Lookup_table#Lookup_tables_in_image_processing)