数据结构：顺序表

1. 线性表

线性表（List）：零个或多个数据元素的有限序列。

也就是说，这些元素之间是有顺序的，且成一个序列。如果存在多个元素，则第一个元素无前驱，最后一个元素无后继，中间的其他元素中的每一个元素也只有一个前驱和一个后继。

比如，幼儿园小朋友放学了，老师会按照身高把小朋友排成一队，每个小朋友拉着前面小朋友的衣服，这样就很清楚了，第一个小朋友没有衣服可以拉，最后一个小朋友后面也没有人拉，中间的小朋友都拉着前面的小朋友，也被后面的小朋友拉着衣服。

常见的线性表有：顺序表、链表、栈、对列...

当然，线性表在逻辑上是线性连续的，但是在物理结构上不一定是一条直线，在物理上存储时，通常是以数组和链式结构组成的。

2. 顺序表

顺序表也叫做--线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

比如说你去学校的图书馆学习，你宿舍一共六个人，他们让你帮忙在图书馆占个位置，然后你就在图书馆找了个六连坐，然后把你的书和其他东西放在位子上占住，等他们来。

因此，通过占位的方式，就相当于开辟了一段顺序表的存储空间，你坐在第一个位置，旁边的座位上都是你占位的东西，那就很明显了，你是这段顺序表的起始位置，最大容量MaxSize = 6。

当然，不是所有学生都爱去图书馆的，你室友可能因为一些事情去不了，那么如果去了三个人，真正使用的座位是4个（算上自己）。

如果后面剩下的两个室友也来了，也就自然的往后面排着坐了，这就涉及到顺序表的插入，但是不能超过当前线性表的存储容量，如果你的一个室友也带着女朋友来了，那就会有一个人没有位置。

OK，接下来就要说到顺序表的插入，删除，查找，修改了。

3. ArrayList

在Java中，我们一般使用List来表示一个表，在集合框架中ArrayList是一个普通的类，实现了List接口。ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态形的顺序表。

插入：如果在顺序表中插入一个数据元素，可以选择直接插入尾部，或者插入指定位置位置。尾插很好理解，就把元素之间放到原表中最后一个元素的后面，然后MaxSize+=1。如果要在指定位置插入，那么就需要让指定位置的元素和其后面的元素都向后移动一个位置，然后把插入元素放入指定位置。

删除：一般就是指定位置元素的删除，并没有“尾删”。步骤是先删除指定位置元素，然后让其后面元素依次往前移动一个位置，然后MaxSize-=1。

修改：改变指定位置的元素，其底层逻辑就是先将指定位置元素删除，然后再插入。

查找：获取指定位置的元素，就和数组中查询下标的元素一样。

4. ArrayList的使用

在Java中ArrayList是怎么使用呢的

插入：尾插和指定位置插入

        尾插c中的所有元素

删除：指定位置删除和删除遇到的第一个o元素

查找：查找指定位置元素

修改：将指定位置元素修改

清空：清空表内的所有元素，将元素设为null

包含：判断o是否在表中

返回第一个o和最后一个o的下标

截取：部分的list，[fromindex, toindex)，左闭右开

这些只是我们常用的一些方法，还有一些其他方法比如拷贝，扩容等。

5. ArrayList的扩容机制

 我们查看ArrayList的源码会看到，它的初始容量会默认为10，扩容是按照原容量的1.5倍进行的。

当前容量：oldCapacity
最小增长量：minCapacity - oldCapacity
首选增长量：oldCapacity >> 1（即当前容量的一半）

然后使用 Arrays.copyOf() 创建新数组并复制原有元素。

6. ArrayList的遍历方式

ArrayList的遍历方式有三种：for循环下标，for each循环以及迭代器循环。

for循环下标：和数组的for循环下标一样。

for each循环：写法更简单，就是无法控制遍历的区间。

迭代器循环：使用了Iterator这个类，用的也比较少。

三种循环方法都能够遍历ArrayList顺序表，最常用的还是前两个。

7. ArrayList的优缺点

优点：ArrayList的优点很明显，就是作为顺序表的适合静态数据的查找和更新。

缺点：不适合插入和删除，因为添加和删除元素的效率较低，需要移动后面的元素。而且扩容也会出现浪费空间的情况（满额的情况下，多增加一个元素，就会扩容至1.5倍）。

8. 总结

以上就是线性表的其中一个表现形式顺序表ArrayList。优点和缺点也都很明显，其作为入门的数据结构也不难理解。