常见数据结构-数组

简介: 常见数据结构-数组

一,如何实现随机访问?

数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。数组的两个特点是:

  • 线性表
  • 连续的内存空间和相同类型的数据(随机访问

计算机需要随机访问数组中的某个元素时,它会首先通过下面的寻址公式,计算出该元素存储的内存地址:

a[i]_address = base_address + i * data_type_size
// 如果数组从 1 开始计数
a[k]_address = base_address + (k-1)*type_size
复制代码

数组从 1 开始编号,是因为根据寻址公式,每次随机访问数组元素都多了一次减法运算,对于 CPU 来说,就是多了一次减法指令。

注意:数组支持随机访问,根据下标随机访问的时间复杂度为 O(1)O(1)O(1),但找的时间复杂度并不为 O(1)O(1)O(1)。,毕竟即便是排好序的数组,用二分查找,时间复杂度也是 O(logn)O(logn)O(logn)

这点很多博客没有注明。

二,低效的“插入”和“删除”

假设数组的长度为 n,现在,如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来,给新来的数据,我们需要将第 k~n 这部分的元素都顺序地往后挪一位。平均情况时间复杂度为 (1+2+...n)/n=O(n)(1+2+...n)/n=O(n)(1+2+...n)/n=O(n)

三,容器能否完全替代数组?

C++JAVA 等语言都提供了类似数组的容器类,比如 C++STL 中的 vector。根据我的经验,一般情况下,推荐用容器开发,简单省事、代码易懂,底层和高性能开发用数组,毕竟容器的灵活性还是牺牲了一定性能的。

参考资料

《数据结构与算法之美》


相关文章
|
29天前
|
存储 Java 程序员
数据结构之 - 深入了解数组数据结构
数据结构之 - 深入了解数组数据结构
35 6
|
29天前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
85 64
|
22天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
21 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
22天前
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
19 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
|
2月前
|
存储 Java
java数据结构,线性表顺序存储(数组)的实现
文章介绍了Java中线性表顺序存储(数组)的实现。线性表是数据结构的一种,它使用数组来实现。文章详细描述了线性表的基本操作,如增加、查找、删除、修改元素,以及其他操作如遍历、清空、求长度等。同时,提供了完整的Java代码实现,包括MyList接口和MyLinearList实现类。通过main函数的测试代码,展示了如何使用这些方法操作线性表。
|
4月前
|
存储
【数据结构OJ题】轮转数组
力扣题目——轮转数组
39 2
【数据结构OJ题】轮转数组
|
3月前
|
存储 Java 程序员
"揭秘HashMap底层实现:从数组到链表,再到红黑树,掌握高效数据结构的秘密武器!"
【8月更文挑战第21天】HashMap是Java中重要的数据结构,采用数组+链表/红黑树实现,确保高效查询与更新。构造方法初始化数组,默认容量16,负载因子0.75触发扩容。`put`操作通过计算`hashCode`定位元素,利用链表或红黑树处理冲突。`get`和`remove`操作类似地定位并返回或移除元素。JDK 1.8优化了链表转红黑树机制,提升性能。理解这些原理能帮助我们更高效地应用HashMap。
41 0
|
5月前
|
存储 算法 调度
【数据结构与算法】详解循环队列:基于数组实现高效存储与访问
【数据结构与算法】详解循环队列:基于数组实现高效存储与访问
|
5月前
|
存储 JavaScript 前端开发
JavaScript中的数组是核心数据结构,用于存储和操作序列数据
【6月更文挑战第22天】JavaScript中的数组是核心数据结构,用于存储和操作序列数据。创建数组可以使用字面量`[]`或`new Array()`。访问元素通过索引,如`myArray[0]`,修改同样如此。常见方法包括:`push()`添加元素至末尾,`pop()`移除末尾元素,`shift()`移除首元素,`unshift()`添加到开头,`join()`连接为字符串,`slice()`提取子数组,`splice()`进行删除、替换,`indexOf()`查找元素位置,`sort()`排序数组。还有其他如`reverse()`、`concat()`等方法。
129 2
|
5月前
|
算法 索引 Python
数据结构 数组部分小结
数据结构 数组部分小结