Array and Linked List are compared in time complexity


Array

Array,在计算器科学中,数组数据结构,简称数组,是由相同类型的元素的集合所组成的数据结构,分配一块连续的内存来存储。利用元素的索引可以计算出该元素对应的存储地址。

由下图可以更好地展示出数组的定义。

图来源: https://brilliant.org/wiki/arrays-adt/

对于数组,最常见的操作就是增删改查,接下来,我们将看一下它们的时间复杂度。

上图表示,在原 Array 第 5 个位置(index = 4)处新增 E 元素,由于 Array 在内存中是连续的,所以一般新增处后面的元素都会向后移动 1 个位置。

特殊地,最好的情况是插入 Array 尾部(index = array.length),后面将没有元素可以移动,所以时间复杂度就是 O(1);那么最坏情况插入最头部(index = 0)时,原 Array 中所有元素将进行后移 1 位置,所以时间复杂度是 O(n)。

所以平均下来时间复杂度为 O(n/2),其实就相当于 O(n)。

同样的,删除与插入类似,删除某个元素时,可能会产生元素向前移动的情况,所以从时间复杂度上讲也是 O(n)

访问某个元素时,我们通常传数组的 index,得到数组的元素节点,实际上内部过程是这样:内存控制器会通过数组 index 只进行一次操作就能访问到数组元素,所以在时间复杂度上是 O(1)。

同样的,更改与查询相似,更改某个元素时,需要先定位到对应元素,并修改里面的值,所以时间复杂度为 O(n)。

于是,通过上面内容就有了以下表格。

Action Time Complexity
Access O(1)
Update O(1)
Delete 平均 O(n)
Insert 平均 O(n)

那么有没有让插入和删除操作更快的数据结构,答案是有的,Linked List

Linked List

Linked List,链表是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针。由于不必须按顺序存储,链表在插入的时候可以达到 O(1) 的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间,而顺序表相应的时间复杂度分别是 O(logn) 和 O(1)。

单向单指针(next) Linked List 结构图

图来源:Linked List | Set 1 (Introduction) - GeeksforGeeks

除了此类型 Linked List 外,还有单向双指针(prev、next)、带有头尾指针的 Linked List、旋转 Linked List 等的变型。

图来源:Linked List | Set 2 (Inserting a node) - GeeksforGeeks

上图表示在 B 节点后面新增一个节点,需要先断开 B 和 C 中间指针,将 B 的 next 指针指向 E,E 的 next 指针指向 C,这样就完成了插入操作,进行了两次 next 操作,是一种常数级时间复杂度,所以时间复杂度为 O(1)。

图来源:Linked List | Set 3 (Deleting a node) - GeeksforGeeks

上图表示删除 C 节点,直接将 B 的 next 指针指向 D,然后在内存中释放 C,这样就完成了删除操作,可见时间复杂度也是 O(1)的。

查询第 5 位置时,需要从头往后查 4 此才能查到节点,所以平均下来时间复杂度为 O(n)。

同样的,更改第 5 位置节点值时,需要从头往后查 4 此才能查到节点,然后更改里面值,所以平均下来时间复杂度为 O(n)。

于是,通过上面内容就有了以下表格。

Action Time Complexity
Access 平均 O(n)
Update 平均 O(n)
Delete O(1)
Insert O(1)

所以,Linked List 在插入、删除操作上更优于 Array,而在查询与更改上,Array 更胜一筹!