数组和链表的区别

数组和链表是两种在内存中组织数据的方式。在理解数组和链表的区别之前，我们先来看看数组和链表。

什么是数组？

数组是一种 数据结构，它包含相同类型的数据元素。数据结构是组织数据的一种方式；数组是一种数据结构，因为它以顺序方式组织数据。数组是一大块内存，内存被划分为小块，每个小块都可以存储一个值。

假设我们创建了一个包含 10 个值的数组，那么每个块将存储整数类型的值。如果我们尝试在不同类型的数组中存储值，那么它就不是一个正确的数组，并且会引发编译时错误。

数组声明

数组可以声明为

要声明数组，我们首先需要指定数组的类型，然后指定数组的名称。在方括号内，我们需要指定数组应包含的元素数量。

让我们通过一个例子来理解。

在上面的例子中，我们声明了一个包含 5 个元素的数组，其名称为 'a'，数据类型为 整数。

什么是链表？

链表是随机存储的节点的集合。每个节点包含两个字段，即数据和链接。这里，数据是存储在该特定节点的值，而链接是指向下一个节点的指针。

数组和链表之间的区别

我们无法说哪种数据结构更好，即数组还是链表。有可能一种数据结构适用于一种需求，而另一种数据结构适用于另一种需求。有各种因素，例如对数据结构执行的频繁操作是什么，或者数据的大小，以及其他因素，我们可以在此基础上选择数据结构。现在我们将根据一些参数来看数组和链表之间的一些区别。

1. 访问元素的成本

在数组的情况下，无论数组大小如何，数组访问元素都需要恒定的时间。在数组中，元素以连续的方式存储，因此如果我们知道元素的基地址，那么我们就可以轻松获得数组中任何元素的地址。我们需要执行简单的计算来获得数组中任何元素的地址。因此，在时间复杂度方面，访问数组中的元素是O(1)。

在链表中，元素不是以连续的方式存储的。它由多个块组成，每个块表示为一个节点。每个节点有两个字段，即一个用于数据字段，另一个用于存储下一个节点的地址。要查找链表中的任何节点，我们首先需要确定第一个节点，称为头节点。如果我们必须查找列表中的第二个节点，那么我们需要从第一个节点开始遍历，在最坏的情况下，要查找最后一个节点，我们需要遍历所有节点。访问元素的平均情况是 O(n)。

我们得出结论，数组中访问元素的成本低于链表。因此，如果我们有访问元素的需求，那么数组是一个更好的选择。

2. 插入元素的成本

插入可能出现三种情况

• 在开头插入元素：要在开头插入新元素，我们首先需要将现有元素向右移，以便在第一个位置创建一个空间。因此，时间复杂度将与列表的大小成正比。如果 n 是数组的大小，则时间复杂度为 O(n)。

在链表的情况下，要在链表的开头插入元素，我们将创建一个新节点，并将第一个节点的地址添加到新节点中。这样，新节点就成为第一个节点。因此，时间复杂度与列表的大小无关。时间复杂度将是恒定的，即 O(1)。

• 在末尾插入元素

如果数组未满，则可以通过索引直接添加新元素。在这种情况下，时间复杂度将是恒定的，即 O(1)。如果数组已满，我们首先需要将数组复制到另一个数组中并添加新元素。在这种情况下，时间复杂度将为 O(n)。

要在链表的末尾插入元素，我们必须遍历整个列表。如果链表包含 n 个元素，则时间复杂度为 O(n)。

• 在中间插入元素

假设我们想在数组的第 i^个位置插入元素；我们需要将 n/2 个元素向右移动。因此，时间复杂度与元素数量成正比。对于平均情况，时间复杂度为 O(n)。

在链表的情况下，我们必须遍历到要插入新元素的那个位置。即使我们不必执行任何移动操作，但我们必须遍历到 n/2 的位置。所需时间与 n 个元素数量成正比，平均情况下的时间复杂度为 O(n)。

最终的链表是

• 易用性

与链表相比，数组的实现更加容易。在使用链表创建程序时，程序更容易出现段错误或内存泄漏等错误。因此，在创建链表程序时需要非常小心。

• 大小动态

链表的大小是动态的，而数组的大小是静态的。这里的静态并不意味着我们不能在运行时决定大小，而是指一旦决定了大小就不能改变。

3. 内存需求

由于数组中的元素存储在 contiguous 的内存块中，因此数组的大小是固定的。假设我们有一个大小为 7 的数组，并且该数组仅包含 4 个元素，则其余空间未被使用。这 7 个元素占用的内存

内存空间 = 7*4 = 28 字节

其中 7 是数组中的元素数量，4 是整数类型的字节数。

在链表的情况下，没有未使用的内存，但指针变量会占用额外的内存。如果数据是整数类型，则一个节点总共占用的内存是 8 字节，即 4 字节用于数据，4 字节用于指针变量。如果链表包含 4 个元素，则链表占用的内存空间将为

内存空间 = 8*4 = 32 字节

如果数据部分尺寸较大，链表将是更好的选择。假设数据尺寸为 16 字节。数组占用的内存空间将为 16*7=112 字节，而链表占用 20*4=80 字节，这里我们将 20 字节指定为 16 字节用于数据大小加上 4 字节用于指针变量。如果我们选择较大数据部分，链表将消耗较少内存；否则，取决于我们用于确定大小的因素。

让我们以表格形式看看数组和链表之间的区别。