程序员必知的数据结构与算法基础：线性表数据结构之数组
黑马程序员2020-06-15 14:01
什么是数据结构和算法
很多教材或者教程再开篇的时候都会来介绍这两个概念，但是概念毕竟是抽象的，所以我们不需要死扣定义，毕竟我们不是为了考试而学的，但这并不是说我们不需要理解其概念，我们只是说不要陷入概念的怪圈。
下面我们来介绍一下相关概念：
1. 数据结构包括数据对象集以及它们在计算机中的组织方式，即它们的逻辑结构和物理存储结构，一般我们可以认为数据结构指的是一组数据的存储结构。
2. 算法就是操作数据的方法，即如何操作数据效率更高，更节省资源。这只是抽象的定义，我们来举一个例子，你有一批货物需要运走，你是找小轿车来运还是找卡车来运？这就是数据结构的范畴，选取什么样的结构来存储；至于你货物装车的时候是把货物堆放在一起还是分开放这就是算法放到范畴了，如何放置货物更有效率更节省空间。
数据结构和算法看起来是两个东西，但是我们为什么要放在一起来说呢？那是因为数据结构和算法是相辅相成的，数据结构是为算法服务的，而算法要作用在特定的数据结构之上，因此，我们无法孤立数据结构来讲算法，也无法孤立算法来讲数据结构。
在学习算法之前我们先来学习几个最基本的数据结构，这是后续学习其他数据结构和算法的基础，也就是我们今天要来学习的：数组，链表，栈，队列。这个四个数据结构又可称之为线性表数据结构。
线性表概念
所谓的线性表，就是将数据排成像一条长线一样的结构，数组，链表，栈，队列都是线性表结构，线性表上的每个数据最多只有前后两个方向，下面以一幅图的形式来展现一下线性表结构
与这种线性结构对应的就是非线性结构，比如后续要学习的数，堆，图等，在这些非线性数据结构中，数据之间并不是简单的前后关系，如下图：
好，理解完线性表的概念之后，接下来正式学习今天的四个数据结构
数组
概念
数组是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。这里我们要抽取出三个跟数组相关的关键词：线性表，连续内存空间，相同数据类型；数组具有连续的内存空间，存储相同类型的数据，正是该特性使得数组具有一个特性：随机访问。但是有利有弊，这个特性虽然使得访问数组边得非常容易但是也使得数组插入和删除操作会变得很低效，插入和删除数据后为了保证连续性，要做很多数据搬迁工作。
逻辑结构和物理结构
所谓的数组的逻辑结构指的是我们可以用什么的表示方式来描述数组元素，比如有一个数组 a,数组中有 n 个元素，我们可以用(a1,a2,a3,.....an)来描述数组中的每个元素，当然后面我们会将具体如何访问数组中的每个元素。数组的物理结构指的是数组元素实际的存储形式，当然了从概念我们可以看出数组的物理存储空间是一块连续的内存单已，为了说明白这个事情，这里给大家准备了一副图
从图中我们可以看出访问数组中的元素是通过下标来访问的，那是如何做到的呢？
1.数组元素的访问
我们拿一个长度为 10 的数组来举例，int [] a= new int[10]，在下面的图中，计算机给数组分配了一块连续的空间，100-139，其中内存的起始地址为baseAddress=100
我们知道，计算机给每个内存单元都分配了一个地址，通过地址来访问其数据，因此要访问数组中的某个元素时，首先要经过一个寻址公式计算要访问的元素在内存中的地址：
a[i] = baseAddress + i * dataTypeSize
其中 dataTypeSize 代表数组中元素类型的大小，在这个例子中，存储的是 int 型的数据，因此 dataTypeSize=4 个字节
2.数组下标为什么从 0 开始
数组的下标为什么要从 0 开始而不是从 1 开始呢？
从数组存储的内存模型上来看，"下标"最确切的定义应该是"偏移（offset）"。前面也讲到，如果用 array 来表示数组的首地址，array[0] 就是偏移为 0 的位置，也就是首地址，array[k] 就表示偏移 k 个 type_size 的位置，所以计算 array[k] 的内存地址只需要用这个公式:
array[k]_address = base_address + k * type_size
但是如果下标从 1 开始，那么计算 array[k]的内存地址会变成：array[k]_address = base_address + (k-1)*type_size
对比两个公式，不难发现从数组下标从 1 开始如果根据下标去访问数组元素，对于 CPU 来说，就多了一次减法指令。
当然另一方面也是由于历史原因，c 语言设计者使用 0 开始作为数组的下标，后来的高级语言沿用了这一设计。
数组的特点
1.高效的随机访问
通过前面的学习我们已经知道，数组元素的访问是通过下标来访问的，计算机通过数组的首地址和寻址公式能够很快速的找到想要访问的元素
2.低效插入和删除
前面我们已经讲到数组是一段连续的内存空间，因此为了保证数组的连续性会使得数组的插入和删除的效率变的很低，下面我们来分析一下，
插入
假设数组的长度为 n，现在如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来给新来的数据，我们需要将第 k～n 这部分的元素都顺序地往后挪一位。如下图所示：
那数组插入有没有相对优化的方案呢？
如果数组中的数据是有序的，我们在某个位置插入一个新的元素时，就必须按照刚才的方法搬移 k 之后的数据。但是，如果数组中存储的数据并没有任何规律，数组只是被当作一个存储数据的集合。在这种情况下，如果要将某个数组插入到第 k个位置，为了避免大规模的数据搬移，我们还有一个简单的办法就是，直接将第 k位的数据搬移到数组元素的最后，把新的元素直接放入第 k 个位置。这种处理思想会在快排中用到
删除
如果我们要删除第 k 个位置的数据，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了。
实际上，在某些特殊场景下，我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行，删除的效率是不是会提高很多呢？举个例子数组 a[6] 中存储了 6 个元素：a1,a2,a3,a4,a5,a6。现在，我们要依次删除 a1,a2 这两个元素。
为了避免 a3,a4,a5,a6 这几个数据会被搬移两次，我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。
如果你了解 JVM，你会发现，这不就是 JVM 标记清除垃圾回收算法的核心思想吗？
没错，数据结构和算法的魅力就在于此，很多时候我们并不是要去死记硬背某个数据结构或者算法，而是要学习它背后的思想和处理技巧，这些东西才是最有价值的。如果你细心留意，不管是在软件开发还是架构设计中，总能找到某些算法和数据结构的影子
数组的应用
针对数组类型，很多语言都提供了容器类，比如 Java 中的 ArrayList、C++ STL 中的 vector。在项目开发中，什么时候适合用数组，什么时候适合用容器呢？
这里我拿 Java 语言来举例。如果你是 Java 工程师，几乎天天都在用 ArrayList，对它应该非常熟悉。那它与数组相比，到底有哪些优势呢？
我个人觉得，ArrayList 最大的优势就是可以将很多数组操作的细节封装起来。比如前面提到的数组插入、删除数据时需要搬移其他数据等。另外，它还有一个优势，就是 支持动态扩容 。数组本身在定义的时候需要预先指定大小，因为需要分配连续的内存空间。如果我们申请了大小为 10 的数组，当第 11 个数据需要存储到数组中时我们就需要重新分配一块更大的空间，将原来的数据复制过去，然后再将新的数据插入。如果使用 ArrayList，我们就完全不需要关心底层的扩容逻辑，ArrayList 已经帮我们实现好了。每次存储空间不够的时候，它都会将空间自动扩容为 1.5 倍大小。不过，这里需要注意一点，因为扩容操作涉及内存申请和数据搬移，是比较耗时的。所以，如果事先能确定需要存储的数据大小，最好在创建ArrayList 的时候事先指定数据大小。
如果你对以上关于 ArrayList 的讲解不太明白，完全不用担心，因为接下来我们就针对 java 中 ArrayList 底层操作逻辑进行分析，理解数组的应用及 ArrayList 底层的扩容逻辑。
1.ArrayList 源码分析
首先我们要明确，ArrayList 底层是采用数组来进行数据的存储，其次 ArrayList 提供了相关的方法来对底层数组中的元素进行操作，包括数据的获取，数据的插入，数据的删除等，此次课程中不会完全讲解所有的操作，笔者将会从两个个方面来进行 ArrayList 底层源码发剖析。
2.容器构建及添加元素
这里有一段非常简短的代码
publicstaticvoidmain(String[] args){//初始化集合List<String> list = new ArrayList<String>(); //向集合中添加元素 list.add("itcast"); }
下面我们以断点调试的方式查看一下，当我们创建集合对象的时候发生了什么事
通过分析可以知道：
1：创建 ArrayList 时采用默认的构造函数创建集合然后往里添加元素，第一次添加时将数组扩容到 10 的大小，之后添加元素都不会在扩容，直到第 11 次添加然后扩容 1.5 倍取整，此后如果需要扩容都是 1.5 倍取整，但是扩容到的最大值是Integer.MAX_VALUE
2：每次扩容时都会创建一个新的数组，然后将原数组中的数据搬移到新的数组中所以回到开始我们所说的： 如果事先能确定需要存储的数据大小，最好在创建ArrayList 的时候事先指定数据大小
我们可以查看 ArrayList 的带参构造函数：
public ArrayList(int initialCapacity) {if (initialCapacity > 0) {//直接使用传递的容量大小创建数组，这样的话只会在不够存储的时候才会需要扩容this.elementData = new Object[initialCapacity];} elseif (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA; } else {thrownew IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }
比如我们要从数据库中取出 10000 条数据放入 ArrayList。我们看下面这几行代码，你会发现，相比之下，事先指定数据大小可以省掉很多次内存申请和数据搬移操作。
ArrayList<User> users = new ArrayList(10000);for (int i = 0; i < 10000; ++i) {users.add(xxx); }
3.获取元素
接下来我们写一段代码来分析一下从集合中获取元素
publicstaticvoidmain(String[] args){//初始化集合List<String> list = new ArrayList<String>(1); //向集合中添加元素 list.add("itcast"); //获取刚刚存入的元素 String ele = list.get(0); }
分析查看集合的 get 方法
到这里我们关于 ArrayList 的底层源码解析就结束了，当然了我们只分析了ArrayList 中很小一部分源码，它还提供了很多的方法，大家不妨自己去分析分析看！同时通过我们的分析，你能不能自己手动实现一个基于数组并且支持动态扩容的集合类呢？写写看吧！
作为高级语言编程者，是不是数组就无用武之地了呢？当然不是，有些时候，用数组会更合适些，我总结了几点自己的经验。
1.Java ArrayList 无法存储基本类型，比如 int、long，需要封装为 Integer、Long 类，而 Autoboxing、Unboxing 则有一定的性能消耗，所以如果特别关注性能，或者希望使用基本类型，就可以选用数组。
2.如果数据大小事先已知，并且对数据的操作非常简单，用不到 ArrayList 提供的大部分方法，也可以直接使用数组。
我总结一下，对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一丢丢性能，完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。
至此，数组部分的学习就完成了，接下来我们进入链表的学习。
举报/反馈
0
0
收藏
分享
