来年加薪必备，2020年攻破数据结构与算法学习笔记-数据结构篇

著名数据专家沃斯曾说：算法+数据结构=程序

今天我们就来讲讲数据结构

1. 数组

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。具有的特性：

1. 线性表
2. 连续的内存空间
3. 相同类型的数据
4. 可以随机访问
5. 数据操作比较低效，平均情况时间复杂度为 O(n)

数组为什么下标从0开始

1. 由于数组是是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。 所以:

• 如果下标从0开始: 计算下标为k的对象的地址的公式为：a[k]_address = base_address + k * type_size
• 如果下标从1开始: 计算下标为k的对象的地址的公式为：a[k]_address = base_address + (k-1) * type_size 对于 CPU 来说，就是多了一次减法指令。

1. C 语言设计者用 0 开始计数数组下标，之后的 Java、JavaScript 等高级语言都效仿了 C 语言。

容器能否完全替代数组？

例如Java的ArrayList，ArrayList 最大的优势就是可以将很多数组操作的细节封装起来。比如前面提到的数组插入、删除数据时需要搬移其他数据等。另外，它还有一个优势，就是支持动态扩容。

那么，作为高级语言编程者，是不是数组就无用武之地了呢？当然不是，有些时候，用数组会更合适些，总的来说，对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一丢丢性能，完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。

2. 链表 （Linked list）

不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用。

image

免责声明：

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

阅读原文内容投诉