数组与链接列表
阵列是最常用的数据结构，用于存储元素的收集。大多数编程语言都提供了轻松声明数组中的数组和访问元素的方法。链接列表，更精确的单连接列表也是一种数据结构，可用于存储元素的集合。它由一个节点序列组成，每个节点都对序列中的下一个节点进行引用。
图1中显示的是通常用于声明和分配值为数组的代码。图2描绘了内存中的数组的样子。
上面的代码定义了一个可以存储5个整数的数组，并使用索引0到4访问它们。数组的一个重要属性是将整个数组分配为单个内存块，并且每个元素在数组中都有自己的空间。定义阵列后，其大小为固定。因此，如果您不确定编译时阵列的大小，则必须定义足够大的阵列才能在安全的一侧。但是，在大多数情况下，我们实际上将使用比分配的元素数量少。因此，实际上浪费了大量的内存。另一方面，如果“足够大的数组”实际上还不够大，则该程序将会崩溃。
链接列表将内存分别分别在其自己的内存块中分别分配给其元素，并且通过将这些元素链接为链中的链接来获得整体结构。链接列表中的每个元素都有两个字段，如图3所示。数据字段保存了存储的实际数据，下一个字段保留对链中下一个元素的引用。链接列表的第一个元素存储为链接列表的头部。
| 数据 | 下一个 |
图3：链接列表的元素
图4描绘了带有三个元素的链接列表。每个元素都存储其数据和所有元素，除了最后一个存储一个对下一个元素的引用。最后一个元素在其下一个字段中具有空值。列表中的任何元素都可以通过从头部开始并遵循下一个指针来访问，直到您满足所需的元素为止。
即使阵列和链接列表也相似，因为它们俩都用于存储元素的集合，但由于它们用于将内存分配给其元素的策略而产生的差异。数组将内存分配给其所有元素作为一个块，并且必须在运行时确定数组的大小。在您不知道编译时数组的大小的情况下，这将使阵列效率低下。由于链接列表将内存分别分别分配给其元素，因此在您不知道编译时列表大小的情况下，这将是非常有效的。与您使用其索引中直接访问数组中的元素相比，链接列表中的声明和访问元素不会直接。
发表评论