每日一学之线性表NO.1-顺序存储

图片来自于百度图片

特点

每两个元素具有序偶关系，如前一个元素是后一个元素的直接前驱，后一个元素则是前一个元素的直接后续

线性表中的数据类型相同

表的长度随着增加、删除而减少

与数组的区别

线性表是一种抽象概念，而数组是一种具体的数据结构

线性表是具有1对1的线性关系的数据元素集合，而数组是元素到下标的一一映射

线性表中的数据不一定是连续存储在内存中，数组的相邻数据是连续存贮在内存中的

线性表要找某一个数据只能一个一个的按顺序找，数组则可以根据下标直接定位到数据

数组可实现线性表

线性表的顺序存储

线性表的顺序存储使用一组连续的存储单元来存储线性表的数据，大家应该可以看出这个顺序存储非常契合数组的特点，因此常用数组来实现线性表的顺序存储。

插入

从图中我们可以看出，如果在i的位置插入一个数据，那么i后面的每一个数据都需要往后平移一位。删除同插入，都会有数据平移的现象。最理想的情况是i==n-1；

查询

数组的查询的方式很多，最简单的为顺序查找，具体的实现方式将在后续为大家提供实例。线性表的查询效率还是比较高的，如果在知道下标的情况下，get到数据的效率更快。

顺序存储的实现-ArrayList

其实ArrayList就是一种线性表的实现。我们首先认识一下源码中是怎么创建一个ArrayList。

没错，在创建一个ArrayList的同时也创建了一个Object的数组。如果说你使用了new ArrayList()创建ArrayList，那么数组的长度默认为10。

那么是否使用new ArrayList(50)就表示数组长度与ArrayList长度为50呢？

执行上面的代码，你会发现list.size() == 0；且会出现IndexOutOfBoundsException异常，那么这又是怎么回事呢？

首先要说明的是，数组长度肯定是50，那么这个size难道不是数组的长度吗？没关系，我们来看源码是怎么写的。

在源码中返回的size是在类中定义的一个变量，而不是在构造函数中的elementData的长度。因此当创建一个ArrayList的时候，其实size的值是。

那么既然数组的长度为50，为什么会出现下标越界的异常呢？我们就得看看在执行add(int index , E element)的时候ArrayList做了什么判断。

看了上面的代码，那么大家就应该知道为什么我们创建了一个50个长度的数组，但是确不能在程序开始就为下标为30的地方新增数据的原因了。

因此如果我们要使用add(int index , E element)的方式直接在某个下标新增数据，必须保证你传递的index要小于或者等于当前size。且当index == size与直接调用add方法的效果一致，直接在当前下标+1的位置放置数据。

大家可能发现了一个问题，那就是第一次ArrayList新增数据时，如果使用add(int index , E element)方法，index只能为。

大家可以按照同样的分析方式看一下list.set(index, element)方法。

下期提要

下期主要分享线性表中的链式存储的相关知识。敬请期待！