链表与数组优缺点

共计 893 个字符,预计需要花费 3 分钟才能阅读完成。

概念

链表

链表是一种物理存储单元非连续、非顺序存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。

数组

说到链表,就不得不提另外一种数据结构,数组

所谓数组,是有序的元素序列。 若将有限个类型相同的变量的集合命名,那么这个名称为数组名。组成数组的各个变量称为数组的分量,也称为数组的元素,有时也称为下标变量。用于区分数组的各个元素的数字编号称为下标。数组是在程序设计中,为了处理方便, 把具有相同类型的若干元素按无序的形式组织起来的一种形式。 这些无序排列的同类数据元素的集合称为数组。

数组是用于储存多个相同类型数据的集合。

特性

数组的优势,在于可以方便的遍历查找需要的数据。在查询数组指定位置(如查询数组中的第4个数据)的操作中,只需要进行1次操作即可,时间复杂度为O(1)。但是,这种时间上的便利性,是因为数组在内存中占用了连续的空间,在进行类似的查找或者遍历时,本质是指针在内存中的定向偏移。然而,当需要对数组成员进行添加和删除的操作时,数组内完成这类操作的时间复杂度则变成了O(n)。

链表的特性,使其在某些操作上比数组更加高效。例如当进行插入和删除操作时,链表操作的时间复杂度仅为O(1)。另外,因为链表在内存中不是连续存储的,所以可以充分利用内存中的碎片空间。除此之外,链表还是很多算法的基础,最常见的哈希表就是基于链表来实现的。基于以上原因,我们可以看到,链表在程序设计过程中是非常重要的。

在链表中进行插入操作的平均时间复杂度通常为 O(1)。
这是因为在链表中插入一个节点,只需要修改几个指针即可。
如果是在链表头部插入,直接修改头指针指向新节点,新节点的 next 指针指向原来的头节点,这个操作的时间复杂度是常数级别,为 O(1)。
如果是在链表中间或尾部插入,需要先遍历找到插入位置,这个遍历的时间复杂度为 O(n),但实际的插入操作(修改指针)仍然是 O(1)。综合起来,平均情况下链表的插入操作时间复杂度为 O(1)。

正文完
 
Dustin
版权声明:本站原创文章,由 Dustin 2019-12-11发表,共计893字。
转载说明:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。