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