现在考虑我们需要在链表中存储数据的情况（因为链表中的节点数将等于实际存储的数据项，即没有像数组那样的额外空间）但我们不允许从为每个节点一次又一次地堆。对于某些人来说，这可能看起来是假设的情况，但这在嵌入式系统中并不是一个非常罕见的要求。基本上，在几个嵌入式程序中，由于多种原因，不允许通过 malloc() 等分配内存。一个明显的原因是性能，即通过 malloc() 分配内存在时间复杂度方面成本很高，因为您的嵌入式程序在大多数情况下都需要确定性。另一个原因可能是模块特定的内存管理，即嵌入式系统中的每个模块可能管理自己的内存。简而言之，如果我们需要进行自己的内存管理，可以不依赖于系统提供的malloc()和free()的API，而可以选择使用数组模拟的链表。我希望你知道为什么我们可能需要使用数组来模拟链表。现在，让我们首先看看如何做到这一点。假设，链表中的节点（即底层数组）的类型声明如下：
struct sllNode { int dataInt; int nextIndex; }; struct sllNode arrayLL[5];
如果我们初始化这个链表（它实际上是一个数组），它在内存中将如下所示：
[(0),-1] [(0),-1] [(0),-1] [(0),-1] [(0),-1] 0x500 0x508 0x510 0x518 0x520
需要注意的重要一点是，链表的所有节点在内存中都是连续的（每个节点占用 8 个字节），并且每个节点的 nextIndex 设置为 -1。这样做（即 -1）是为了表示链表的每个节点到目前为止都是空的。这个链表由头索引 0 表示。
现在，如果这个链表用数据部分 4、3、2 和 1 的四个元素连续更新，它在内存中将如下所示。这个链表可以看作是 0x500 -> 0x508 -> 0x510 -> 0x518。
[(1),1] [(2),2] [(3),3] [(4),-2] [(0),-1] 0x500 0x508 0x510 0x518 0x520
需要注意的重要一点是最后一个节点（即第四个节点）的 nextIndex 设置为 -2。这样做（即 -2）是为了表示链表的结尾。此外，链表的头节点是索引 0。如果我们从上面的链表中删除第二个节点，这个使用数组模拟链表的概念看起来会更有趣。在这种情况下，链表在内存中将如下所示：
[(1),2] [(0),-1] [(3),3] [(4),-2] [(0),-1] 0x500 0x508 0x510 0x518 0x520
结果链表是 0x500 -> 0x510 -> 0x518。这里需要注意的是，即使我们已经从链表中删除了第二个节点，但是这个节点的内存还在，因为底层数组还在。但是第一个节点的 nextIndex 现在指向第三个节点（索引为 2）。
希望上面的例子能给出一些想法，对于模拟链表，我们需要编写我们自己的类似于 malloc() 和 free() 的 API，它们基本上用于插入和删除节点。现在，这就是所谓的自己的内存管理。让我们看看这是如何以算法方式完成的。
有多种方法可以做到这一点。如果我们采用使用数组创建链表的简单方法，我们可以使用以下逻辑。对于插入节点，遍历底层数组并找到 nextIndex 为 -1 的节点。这意味着这个节点是空的。将此节点用作新节点。更新这个新节点中的数据部分，并将这个节点的nextIndex设置为链表的当前头节点（即头索引）。最后，将这个新节点的索引作为链表的头索引。为了形象化，让我们举个例子。假设链表如下，其中头索引为 0 即链表为 0x500 -> 0x508 -> 0x518 -> 0x520
[(1),1] [(2),3] [(0),-1] [(4),4] [(5),-2] 0x500 0x508 0x510 0x518 0x520
插入数据为 8 的新节点后，链表将如下所示，头部索引为 2。
[(1),1] [(2),3] [(8),0] [(4),4] [(5),-2] 0x500 0x508 0x510 0x518 0x520
所以链表节点将位于地址 0x510 -> 0x500 -> 0x508 -> 0x518 -> 0x520
对于删除节点，我们需要将节点的 nextIndex 设置为 -1，以便将节点标记为空节点。但是，在这样做之前，我们需要确保将上一个节点的 nextIndex 正确更新为要删除的该节点的下一个节点的索引。我们可以看到我们已经完成了自己的内存管理，用于从数组内存中创建一个链表。但是，这是在这个链表中插入和删除节点的一种方式。可以很容易地注意到，就时间复杂度而言，找到一个空节点并不是那么有效。基本上，我们正在线性搜索完整数组以找到一个空节点。
让我们看看我们是否可以进一步优化它。基本上，我们也可以在同一个数组中维护一个空节点的链表。在这种情况下，链表将由两个索引表示——一个索引用于具有实际数据值的链表，即到目前为止已插入的节点，其他索引用于空节点的链表。通过这样做，每当我们需要在现有链表中插入一个新节点时，我们都可以快速找到一个空节点。让我们举个例子：
[(4),2] [(0),3] [(5),5] [(0),-1] [(0),1] [(9),-1] 0x500 0x508 0x510 0x518 0x520 0x528
上面使用两个索引（0 和 5）表示的链表有两个链表：一个用于实际值，另一个用于空节点。具有实际值的链表在地址 0x500 -> 0x510 -> 0x528 处具有节点，而具有空节点的链表在地址 0x520 -> 0x508 -> 0x518 处具有节点。可以看出，现在找空节点（即自己写类似malloc()的API）应该会比较快，因为我们可以快速找到空闲节点。在现实世界的嵌入式程序中，一个固定的内存块（通常称为内存池）仅由模块使用 malloc() 分配一次。然后该内存池（基本上是一个数组）的管理由该模块本身使用前面提到的技术完成。有时，有多个内存池，每个内存池具有不同大小的节点。当然，自己的内存管理还有其他几个方面，但我们将把它留在这里。但值得一提的是，有几种方法可以进一步改进插入（需要我们自己分配内存）和删除（需要我们自己释放内存）。
如果我们仔细观察，可以注意到内存的 Heap 部分基本上是一个由底层操作系统 (OS) 管理的大字节数组。OS 正在通过 malloc()、free() 等向程序员提供这种内存管理服务。啊哈！！
本文的重要内容总结如下：
A) 数组表示连续内存。它可以存在于任何内存部分，无论是数据、堆栈还是堆。
B) 链表意味着非连续的链接内存。它可以存在于任何内存部分，无论是堆、数据还是堆栈。
C) 作为程序员，从内存角度看数据结构可以让我们在选择特定数据结构甚至设计新数据结构时有更好的洞察力。例如，我们可能会创建一个链表数组等。
