线性表

线性表是n个相同类型元素的有限序列，逻辑上连续物理上不一定是连续的，存储结构上分为顺序存储和链式存储，常见的线性表有：顺序表，链表，栈，队列……

ArrayList

数据结构

ArrayList（顺序表）是Java中的一个集合类，背后的数据结构是一个动态的数组，相比于一般的数组，ArrayList可以进行动态的增删改查（底层有一定的扩容机制），ArrayList内部将这些方法封装了起来以面向对象的方法供开发者使用。

ArrayList的构造方法

ArrayList的构造方法有三种，如下：

1. 无参构造
   无参构造底层会默认构造出一个长度为10的动态数组（但是这里必须是第一次add元素之后才会构造成功），下面我将用源码的方式给大家展开讲述；
   
   我们可以发现当我们没有add元素的时候，底层只是给我们初始化了一个长度为0的默认数组，我们现在add一下之后再看一下源码
   
   当我们add(1)之后，发现底层调用了grow方法让数组申请了10个空间，当顺序表满了之后也是调用grow方法给顺序表进行1.5倍扩容。
2. 第二种构造方法是利用Collection来构建ArrayList，需要满足两个条件：1.必须是继承与Collection接口 2.必须是泛型E本身或E的子类
   代码如下：

public class Test3 {public static void main(String[] args) {ArrayList arrayList = new ArrayList<>();arrayList.add(1);arrayList.add(2);arrayList.add(3);ArrayList arrayList1 = new ArrayList<>(arrayList);LinkedList linkedList = new LinkedList<>();LinkedList linkedList1 = new LinkedList<>();ArrayList arrayList2 = new ArrayList<>(linkedList);ArrayList arrayList3 = new ArrayList<>(linkedList1);}
}

注意：
1.注释1和注释2中的arrayList和linkedList所对应的类都实现了Collection接口满足条件1，且传入的参数都是Integer类型符合条件2，故编译通过；
2.注释3处虽然linkedlist1所对应的类实现了Collection接口但是传入的是String类型的参数不符合条件2，故编译失败。

3. 第三种构造方法是指定容量的构造方法，在构造时制定了顺序表的空间大小

总结：
1.检测是否真正需要扩容，如果是调用grow准备扩容；
2.预估需要库容的大小；
初步预估按照1.5倍大小扩容
如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容
真正扩容之前检测是否能扩容成功，防止太大导致扩容失败
3.使用copyOf进行扩容。

遍历

**遍历ArrayList的方式有三种：1.for循环 2.foreach 3.迭代器遍历
分别针对这三种方法写个代码如下：

import java.util.Iterator;public class Test3 {public static void main(String[] args) {ArrayList arrayList = new ArrayList<>();//arrayList中进行插入元素arrayList.add(1);arrayList.add(2);arrayList.add(3);arrayList.add(4);//for循环遍历for (int i = 0; i < arrayList.size(); i++) {System.out.print(arrayList.get(i) + " ");}System.out.println();//foreach遍历//这里涉及到了自动拆包for (int x: arrayList) {System.out.print(x + " ");}System.out.println();//迭代器遍历Iterator it = arrayList.iterator();//new一个迭代器对象while (it.hasNext()) {System.out.print(it.next() + " ");}System.out.println();}
}

以上就是三种遍历ArrayList集合的三种方式，需要注意的是：用迭代器进行遍历的时候需要满足该集合类实现了Iterator接口。