为什么我们使用数组而不是其他数据结构？

对于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） 查找时间（查找成本随着每个元素的添加而增加）。与到达 P1000 相比，到达 P4 要贵得多。

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

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

再拿我们的阵列。这一次，我想找到包含值“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（1），但它们提供线性 O（N） 搜索时间。

这是对内存中数据结构的令人难以置信的高层次概述，跳过了很多细节，但希望它能说明数组与其他数据结构相比的优势和劣势。

并非所有程序都执行相同的操作或在相同的硬件上运行。

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

在商业编程中（我们大多数人都这样做），我们可以针对相对强大的硬件。在这些情况下，使用 C# 中的 List 或 Java 中的 Vector 是正确的选择，因为这些结构允许开发人员更快地完成目标，这反过来又使这种类型的软件更具特色。

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

我敢肯定，我遗漏了这些案例的一些好处，但我希望你明白这一点。

了解数组优势的一种方法是查看需要数组的 O（1） 访问能力并因此大写：

1. 在应用程序的查找表中（用于访问某些分类响应的静态数组）

2. 记忆（已经计算出复杂的函数结果，这样你就不会再次计算函数值，比如log x）

3. 需要图像处理 （https://en.wikipedia.org/wiki/Lookup_table#Lookup_tables_in_image_processing 的高速计算机视觉应用)