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

1. 数组是什么?

数组是一种数据结构,数组中包含相同类型的元素。 数据结构是组织数据的一种方式。 数组是一种数据结构,因为它顺序地组织数据。 数组是一个很大的内存块,内存分为小块到小块,每个块都能够存储一些值。

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

数组声明

数组可以声明为:

data_type name of the array[no of elements]

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

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

int a[5];

2. 链表是什么?

链表是随机存储的节点的集合。 每个节点包括两个字段,即数据和链接。 此处,数据是存储在该特定节点上的值,而链接是保存下一个节点地址的指针。

3. 数组和链表的区别

不能说哪种数据结构(即数组或链表)更好。 一个数据结构可能适合一种需求,而另一种数据结构可能适合另一种需求。 有多种因素,例如对数据结构执行的频繁操作或数据大小,以及根据其选择数据结构的其他因素。 现在,我们将看到基于某些参数的数组和链表之间的一些区别。

3.1. 访问元素的成本

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

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

我们得出的结论是,访问数组中元素的成本低于链表。 因此,如果对访问元素有效率要求,数组是一个更好的选择。

3.2. 2.插入元素的成本

插入中可能存在三种情况:

  • 在开始处插入元素:要在开始处插入新元素,首先需要将元素向右移动以在第一个位置创建一个空格。 因此,时间复杂度将与列表的大小成正比。 如果n是数组的大小,则时间复杂度将为O(n)。

    对于链表,要在链表的开头插入一个元素,我们将创建一个新节点,并将第一个节点的地址添加到新节点。 这样,新节点将成为第一个节点。 因此,时间复杂度与列表的大小不成比例。 时间复杂度将是恒定的,即O(1)。

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

欢迎任何形式的转载,但请务必注明出处,尊重他人劳动成果。
转载请注明:文章转载自 有区别网 [http://www.hasdiffer.com]
本文标题:数组与链表的区别
本文链接:http://www.vsdiffer.com/array-vs-linked-list.html
免责声明:本站部分内容除注明转载外,均为本站网站用户投稿或互联网整理。对于该内容的正确性如何,本站不负任何责任。同时,如本网站内容无意之中冒犯了您的权益,请联系站长,邮箱:1478761107#qq.com(使用@代替#),我们核实并会尽快处理。

随机