1.顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

接口的实现

public class SeqList {
  private int[] array;
  private int size;
  // 默认构造方法
  SeqList(){ }
  // 将顺序表的底层容量设置为initcapacity
  SeqList(int initcapacity){ }
  // 新增元素,默认在数组最后新增
  public void add(int data) { }
  // 在 pos 位置新增元素
  public void add(int pos, int data) { }
  // 判定是否包含某个元素
  public boolean contains(int toFind) { return true; }
  // 查找某个元素对应的位置
  public int indexOf(int toFind) { return -1; }
  // 获取 pos 位置的元素
  public int get(int pos) { return -1; }
  // 给 pos 位置的元素设为 value
  public void set(int pos, int value) { }
  //删除第一次出现的关键字key
  public void remove(int toRemove) { }
  // 获取顺序表长度
  public int size() { return 0; }
  // 清空顺序表
  public void clear() { }
  // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
  public void display() { }
}

2.ArrayList简介

【说明】

1. ArrayList是以泛型方式实现的，使用时必须要先实例化
2. ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
3. ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
4. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
5. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者
   CopyOnWriteArrayList
6. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

3.ArrayList使用

ArrayList的构造

public static void main(String[] args) {
  // ArrayList创建，推荐写法
  // 构造一个空的列表
  List<Integer> list1 = new ArrayList<>();
  // 构造一个具有10个容量的列表
  List<Integer> list2 = new ArrayList<>(10);
  list2.add(1);
  list2.add(2);
  list2.add(3);
  // list2.add("hello"); // 编译失败，List<Integer>已经限定了，list2中只能存储整形元素
  // list3构造好之后，与list中的元素一致
  ArrayList<Integer> list3 = new ArrayList<>(list2);
  // 避免省略类型，否则：任意类型的元素都可以存放，使用时将是一场灾难
  List list4 = new ArrayList();
  list4.add("111");
  list4.add(100);
}

ArrayList常见操作

ArrayList虽然提供的方法比较多，但是常用方法如下所示，需要用到其他方法时，自行查看ArrayList的帮助
文档。

ArrayList的遍历

ArrayList 可以使用三方方式遍历：for循环+下标、foreach、使用迭代器

public static void main(String[] args) {
  List<Integer> list = new ArrayList<>();
  list.add(1);
  list.add(2);
  list.add(3);
  list.add(4);
  list.add(5);
  // 使用下标+for遍历
  for (int i = 0; i < list.size(); i++) {
    System.out.print(list.get(i) + " ");
  } 
  System.out.println();
  // 借助foreach遍历
  for (Integer integer : list) {
    System.out.print(integer + " ");
  } 
  System.out.println();
  Iterator<Integer> it = list.listIterator();
  while(it.hasNext()){
    System.out.print(it.next() + " ");
  } 
  System.out.println();
}

注意：

1. ArrayList最长使用的遍历方式是：for循环+下标 以及 foreach
2. 迭代器是设计模式的一种

ArrayList的扩容机制

public static void main(String[] args) {
  List<Integer> list = new ArrayList<>();
  for (int i = 0; i < 100; i++) {
    list.add(i);
  }
}
Object[] elementData; // 存放元素的空间
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 默认空间
private static final int DEFAULT_CAPACITY = 10; // 默认容量大小
public boolean add(E e) {
  ensureCapacityInternal(size + 1); // Increments modCount!!
  elementData[size++] = e;
  return true;
}
private void ensureCapacityInternal(int minCapacity) {
  ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    return Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
  modCount++;
  // overflow-conscious code
  if (minCapacity - elementData.length > 0)
    grow(minCapacity);
  }
  private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 private void grow(int minCapacity) {
  // 获取旧空间大小
  int oldCapacity = elementData.length;
  // 预计按照1.5倍方式扩容
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  // 如果用户需要扩容大小 超过 原空间1.5倍，按照用户所需大小扩容
  if (newCapacity - minCapacity < 0)
      newCapacity = minCapacity;
  // 如果需要扩容大小超过MAX_ARRAY_SIZE，重新计算容量大小
  if (newCapacity - MAX_ARRAY_SIZE > 0)
      newCapacity = hugeCapacity(minCapacity);
      // 调用copyOf扩容
  elementData = Arrays.copyOf(elementData, newCapacity);
}  
private static int hugeCapacity(int minCapacity) {
  // 如果minCapacity小于0，抛出OutOfMemoryError异常
  if (minCapacity < 0)
  throw new OutOfMemoryError();
  return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

【总结】

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