07.数据结构：线性表入门
大家好，我是王有志。
从今天开始就进入到数据结构的部分了，整体分为3个部分：线性表，树和图，从认识每种数据结构到它们的高级应用。今天我们先从最简单的线性表和数组开始。
什么是线性表？
线性表是我们工作中最常用的数据结构之一，同时它也是我们接触到的最简单的数据结构。
根据操作节点的自由度，我们可以将线性表分为两大类：非受限线性表和受限线性表。
- 非受限线性表：数组，链表
- 受限线性表：栈，队列
除此之外，字符串也是一种特殊的线性表。
在频繁的使用过程中，你有没有思考过什么是线性表？
我们一起来看下百度百科中线性表的定义：
线性表（linear list），是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。
线性表的概念还是很容易理解的，接着来看点头疼的：
线性表中的个数n定义为线性表的长度，n=0时称为空表。在非空表中每个数据元素都有一个确定的位置，如用ai表示数据元素，则i称为数据元素ai在线性表中的位序。
线性表的相邻元素之间存在着序偶关系。如用（a1，…，ai-1，ai，ai+1，…，an）表示一个顺序表，则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2，…，n-1时，ai有且仅有一个直接后继，当i=2，3，…，n时，ai有且仅有一个直接前驱。
这些看起来是不是就有些头疼了？我们举个简单的例子，糖葫芦都吃过吧？如果我说糖葫芦就是一个线性表呢？
线性糖葫芦.png
我们来看看糖葫芦是不是符合线性表的定义：
- 相同特性的数据元素：都是山楂；
- 有限：总共5个山楂；
- 序列：给山楂编上号就是完整的序列。
很多小伙伴可能忘记了序列的特点，序列存在顺序关系（可以是混乱的顺序，但是要固定）和排成一列（不会有分支，前后一对一的关系）。
通过这串糖葫芦，也给出位序，前驱节点和后继节点的解释：
- 位序：山楂在签子上确定位置的编号，就是通过这个编号可以找到指定的山楂；
- 前驱节点：以2号山楂为例，排在2号前面的都是前驱节点；
- 直接前驱节点：还是2号山楂，排在2号山楂，并且紧挨2号山楂的1号山楂就是直接前驱节点；
- 后继节点：和前驱节点反过来；
- 直接后继节点：和直接前驱节点反过来。
再通俗点解释，可以用“一根线”穿起来的相同物件（元素），并保持固定顺序的就是线性表。
这样理解起来是不是比定义中的数学符号简单多了？
数组
知道了什么是线性表之后，我们来看线性表中最简单的数据结构：数组。
还记得我们在[[02.预备知识：概念和存储结构#物理存储结构]]提到的顺序存储结构吗？数组正是使用了顺序存储结构。
另外在[[02.预备知识：概念和存储结构#内存地址]]中我们提到过每块内存都有自己的编号。这种顺序存储结构加上内存编号，使得数组具有了强大的随机存取能力。
数组的优点
数组最大的优点就是随机存取的能力，换句话说就是在数据中查找指定下标的元素速度非常快。
因为计算机可以通过一步简单的计算得到存储该元素的内存地址：起始地址+下标X类型大小。
这是不是数组下标从零开始的原因之一呢？
数组的缺点
计算机的世界中没有能解决一切问题的“银弹”，随机存取的能力不仅仅给了数组快速查找元素的资本，也使得数组在插入和删除元素后必须要“整理”内存，顺序存储结构。
数组在插入元素后，为了保持随机存取的特性，必须要向后移动元素。
数组插入元素.png
数组在删除元素后，为了保持随机存取的特性，必须要向前移动元素。
数组删除元素.png
当然，也并不是全部的插入删除都要移动元素。最好的情况下，在数组的尾部插入和删除元素，不需要移动任何元素，此时的时间复杂度是
除了数组的插入和删除外，还有一种情况我们不得不考虑，如果我们在插入元素时，紧邻数组的内存已经被分配了怎么办？
数组的扩容
我们先来看一段代码：
// 第一种
int numbers1 = {0, 1, 2};
// 第二种
int numbers2 = new int[3];
// 第三种
int[] numbers3 = {};
numbers3[0] = 0;
numbers3[1] = 1;
numbers3[2] = 2;
这3种创建数组的代码，哪个会有编译时异常？哪个会有运行时异常？
答案是，都能通过编译，但是第三种在运行时会抛出ArrayIndexOutOfBoundsException异常。
强制要求创建数组时进行初始化或者指定数组大小，是为了能够给数组分配合适的内存。但是这么做就带来另一个问题，创建数组时，大小已经固定，如果想添加更多的元素该怎么办？
相信你一定非常熟悉ArrayList了吧？
ArrayList正是Java中提供的可动态扩容的数组，它的底层是Object[]，扩容的方式也非常的“粗暴”，当数组大小不足时，重新申请内存（1.5倍），将原数组元素拷贝到新的数组上，并修改引用。
结语
数组的内容就到此结束了，仅仅从数据结构的角度来看数组，还是非常简单的。
可能很多小伙伴会说，工作中都是使用ArrayList了，数组要退出舞台了。
我的想法是，大部分场景选择ArrayList是没有任何问题的，在追求极致性能，且没有插入删除的场景时，数组或许会是一个不错的选择。
练习
- 尝试实现一个动态数组
- 1.两数之和
- 53.最大子数组和
- 88.合并两个有序数组
本篇内容的代码仓库：
好了，今天就到这里了，Bye~~
