1.1 顺序表
线性表：线性表是具有相同特征数据元素的有限序列。
- 相同特征：把同一类事物归类，方便批量处理。
- 有限：表中元素个数为n，n有限大，n可以为零。
- 序列：表中元素排成一列，体现了一对一的逻辑特征（除第一个元素外，每个元素有且只有一个直接前驱，除最后一个元素外，每个元素有且只有一个直接后继）
- 线性表中第一个元素称为表头元素，最后一个元素称为表尾元素。
线性表的存储结构有两种：顺序存储和链式存储，分别对应顺序表和链表。
1.1.1 定义
线性表的顺序存储是使用一组连续地址的存储单元（如Java中的数组），依次存储线性表中的数据元素。顺序存储的线性表也称为顺序表。
对于顺序表而言，元素在存取操作上，时间复杂度为O(1)，将带有这种特点的存储结构，称为随机存取结构，顺序存储和随机存取是顺序表的显著优点。
1.1.2 建立顺序表
- 静态建表
首先在内存中找到一块连续的存储空间，将元素以次存放即可。在静态建表时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据将产生溢出，从而导致程序的崩溃（没这么严重，Java中也就是元素无法插入，抛出一个异常而已）。
顺序表需要三个部分
- 存储空间的起始地址
- 顺序表最大存储容量
- 顺序表的当前长度
C语言中对于顺序表的描述
在Java中，也可也参照C的方式定义一个类，类中定义一个成员变量，类型为数组，同时设置一个变量，用来记录实际存储的有效元素个数。实际上ArrayList底层就是这样来做的，只是它更偏向于动态建表。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
//创建一个对象数组，用来存储元素，没有显示的指定大小，运行时默认分配10个大小的内存空间
transient Object[] elementData; // non-private to simplify nested class access
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
//用来保存数组中的有效元素个数
private int size;
...
- 动态建表
动态分配方式就是存储数组的空间是在程序执行过程中，通过动态的方式来分配。
注意：动态分配并不是链式存储，它同样属于顺序存储结构，只是分配的空间大小在运行时决定。
针对于动态建表，在Java中，也是有具体实现的，还是以ArrayList为例
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
//创建一个对象数组，用来存储元素，没有显示的指定大小，运行时默认分配10个大小的内存空间
transient Object[] elementData; // non-private to simplify nested class access
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
//用来保存数组中的有效元素个数
private int size;
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
//存储空间动态分配和动态增长
grow(minCapacity);
}
//下面是ArrayList的存储空间动态分配和增长的方式
//首次会开辟10个大小的空间作为对象数组的长度
//每当对象数组满了后，就扩容为原数组的1.5倍，并将原数组内容拷贝到新数组中
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
当然动态建表时，所创建的数组类型并不一定是对象数组类型，还可以是int数组，char数组等。
1.1.3 顺序表的操作
针对于顺序表的操作主要有，插入元素，删除元素，遍历顺序表，取值等
- 顺序表插入元素
插入过程描述如下，将待插入位置后的元素后移，然后再插入元素
- 可插入下表位置p的取值范围是：0到length（包含length）
针对于这个Length，你一定存在疑问，在length处插入元素表示什么含义呢？实际上空表在插入元素，length自增后，每次length指向顺序表的最后一个元素的下一个位置，如空表插入元素1，记为array[0]=1，length自增为1，这样length就指向array[1]，尽管array[1]没有被赋值，这样在length处插入元素就相当于原来的顺序表后面添加一个元素。 - 当表长度length等于数组长度maxsize的时候，就不可以再插入元素
和前面的解释类似，length值和元素在数组的下标之间总是相差1，当length=maxsize时，说明数组已经满了，也即线性表已经满了。 - 移动元素从后向前进行
注意：这个length指的是顺序表中实际存储元素的个数，有别于数组的长度“maxsize-1”。
先看C语言如何实现这个操作：
sqList为要操作的数组，length为数组的长度，p为元素要插入的位置，e为要插入的元素。
执行流程描述：
- 判断插入位置是否合法：由于数组的下标是从0开始的，所以插入位置要在[0,length]之间，如果数组中的元素个数leng等于了maxisize，则表示数组满了，也不能执行插入
- 将插入位置后的元素后移一位
- 将要插入的元素复制到待插入的位置
- 数组元素个数自增
- 返回插入成功
在Java中是如何实现的呢？下面还是以ArrayList为例进行讲解，实际上它们的操作过程都是一样的：
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
//首先检查插入位置是否合规
rangeCheckForAdd(index);
//查看数组是否需要扩容，检查容量是否够，不够扩容为原来1.5倍
ensureCapacityInternal(size + 1); // Increments modCount!!
//将待插入位置后的元素向后移动一个单位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//将待插入元素放到待插入位置
elementData[index] = element;
//元素个数自增
size++;
}
/**
* A version of rangeCheck used by add and addAll.
*/
private void rangeCheckForAdd(int index) {
//插入位置，要在[0,size]区间内
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
- 顺表删除元素
删除元素是过程如下所示，下图是删除索引为2上的元素，将索引2后的所有元素向前移动，并修改length长度
- 可删除元素下标p的取值范围为：0到length-1
为什么是length-1呢？在前面插入元素的时候，我们讲解过length指向最后一个元素的下一个位置，也就是没有元素，当然谈不上删除元素了。 - 当表长度length等于0的时候，不可以再删除元素
length等于零，表示数组中没有元素，也即顺序表中没有元素。 - 移动元素从前向后运行
使用C语言实现：
sqlList是待操作顺序表，lengt指的是顺序表长度，p指的是待删除元素的位置，e指的是待删除元素
执行过程解读：
-
首先判断待删除位置是否合法
-
如果合法，则将待删除位置元素的值赋值给e，保留该值
-
将待删除位置后的所有元素向前移动一个单位
-
将length长度减去1
通过上面的代码，删除元素完成后，但是这是否意味着此时length指向的位置没有元素了呢？
非也，此时这个值，是原来的线性表的最后一个元素的值，不信的话，可以观察如下代码：
public class demo03 {
public static void main(String[] args) {
Object[] obj=new Object[10];
obj[0]=1;
obj[1]=2;
obj[2]=3;
obj[3]=4;
obj[4]=5;
//原来的Ojb [1, 2, 3, 4, 5, null, null, null, null, null]
System.out.println(Arrays.asList(obj));
//将3所在位置之后的元素前移一个单位
System.arraycopy(obj, 3,obj,2,2);
//移动后 [1, 2, 4, 5, 5, null, null, null, null, null]，索引4上仍然有元素存在，类比到顺序表，length就指向这个索引为4的元素，然后它的值并不为null
System.out.println(Arrays.asList(obj));
//将索引4的值设置为null
obj[4]=null;
//删除最后一个元素后，[1, 2, 4, 5, null, null, null, null, null, null]
System.out.println(Arrays.asList(obj));
}
}
在很多C程序中删除顺序表中元素的操作，都是这样来写的，不过该问题，无伤大雅，因为它们在顺序表遍历或者取值时，都完美的避开了这个问题，遍历或取值的时候，只允许操作区间为[0,length)，length处并不取值。
我们可以看Java中是如何实现删除顺序表元素操作的，还是以ArrayList为例：
在ArrayList中，删除元素是通过“remove”方法来实现的，它的底层实现是这样的
public E remove(int index) {
//检查所传入的索引是否合法
rangeCheck(index);
modCount++;
//在对象数组中，得到要删除位置上的元素
E oldValue = elementData(index);
//得到待删除位置后的元素个数
int numMoved = size - index - 1;
if (numMoved > 0)
//也就是将待删除位置后的所有元素，向前移动一个位置
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//将数组长度减1，然后原数组最后的元素释放，针对于末尾元素，它和C在处理上存在显著不同
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
而在进行取值（取指定位置上的元素）的时候，这样的：
public E get(int index) {
//检查索引是否合法
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
//索引大小不能超过或等于size大小
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
return (E) elementData[index];
}
再看查找指定元素：
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
//遍历顺序表中的元素，并非整个对象数组，注意这个范围也是[0,size)
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
1.1.4 顺序表的优缺点
- 优点：
-
存储密度大：不需要为表中元素之间的逻辑关系增加额外的存储空间（这是相对于链表而言的）
-
随机存取：可以快速存取表中任一位置上的元素（这也是相对于链表而言的）
- 缺点：
-
插入和删除操作需要移动大量的元素
-
对于存储空间要求高，会产生存储空间的碎片
参考代码来源：JDK1.8 https://github.com/wupeixuan/JDKSourceCode1.8/blob/master/src/java/util/ArrayList.java