数据结构之ArrayList与顺序表(有源码剖析)（一）+https://developer.aliyun.com/article/1413527
注意:
1. ArrayList是以泛型的形式实现的，必须要先实例化
2.ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
3.ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
4. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
5，ArrayList是线程不安全的，在多线程中常使用Vector或者 CopyOnWriteArrayList
6.ArrayList底层是一段连续的内存空间，可以动态扩容
补充:
1.RandomAccess接口是Java中的"标记接口(marker interface)",用于指示列表是否能高效的进行数据的访问，对于ArrayList接口来说，他能够根据索引快速的进行数据的访问。但是对于链表(LinkedList)则没有被标记，因为链表通过索引访问数据的开销和时间复杂度很高
2.在Java中，Serializable也是一个标记接口（marker interface），用于表明一个类的对象可以被序列化。序列化指的是将对象转换为字节流，以便在网络上传输或保存到文件系统中，同时也可以通过反序列化将字节流重新转换为对象。
3.transient关键字：用于标记某些属性在序列化的时候应该被忽略，翻译为"短暂的，暂时的"
四. ArrayList使用
1.构造方法
1.无参构造
ArrayList()
2.指定容量
ArrayList(int initCapacity)
3.利用其他集合构建 ArrayList
ArrayList(Collection<? extends E> c)
代码实现:
public static void main(String[] args) { // 1.无参构造 推荐使用向上转型 List<Integer> list = new ArrayList<>(); list.add(1); list.add(2); list.add(3); System.out.println(list.toString()); // 2.有参构造 设置容量为10 List<Integer> list2 = new ArrayList<>(10); list2.add(1); list2.add(2); list2.add(3); // 3.利用其他Collection 来构建ArrayList List<Integer> list3 = new ArrayList<>(list2); System.out.println(list3.toString());// 输出1，2，3 }
2 ArrayList常见操作
ArrayList虽然提供的方法比较多，但是常用方法其实不多，使用到其他方法时可自行查阅
1.add
在ArrayList接口中，对应的也有两个add方法
1.bollean add(E e) 尾插e
2.void add(int index,E element) 将e插入到index位置
2.addAll
boolean addAll(Collection<? extends E> c) 尾插 c 中的元素
这个方法适合将另一个集合中的元素尾插到创建的list中
3.remove
E remove(int index) 删除 index 位置元素，并返回删除的元素
boolean remove(Object o) 删除遇到的第一个 o
4. get和set
E get(int index) 获取下标 index 位置元素
E set(int index, E element) 将下标 index 位置元素设置为 element
源码:
public E get(int index) { rangeCheck(index); return elementData(index); }
public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; }
5.clear
void clear() 清空
public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; }
注意：GC指的是“垃圾回收”（Garbage Collection）是Java中用于处理使用过的内存资源的一种机制，用于提高效率
6.contains
boolean contains(Object o) 判断 o 是否在线性表中
源码剖析
7.indexOf
int indexOf(Object o) 返回第一个 o 所在下标
源码：
public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) if (elementData[i]==null) return i; } else { for (int i = 0; i < size; i++) if (o.equals(elementData[i])) return i; } return -1; }
8.lastIndexOf
int lastIndexOf(Object o) 返回最后一个 o 的下标
源码:
public int lastIndexOf(Object o) { if (o == null) { for (int i = size-1; i >= 0; i--) if (elementData[i]==null) return i; } else { for (int i = size-1; i >= 0; i--) if (o.equals(elementData[i])) return i; } return -1; }
9.subList
List subList(int fromIndex, int toIndex) 截取部分 list 并返回被截取的集合
3.ArrayList的遍历
ArrayList的遍历方式有三种，for循环+下标，for each循环，迭代器
public static void main(String[] args) { List<Integer> list = new ArrayList<>(); list.add(1); list.add(2); list.add(3); // 使用for循环+下标 for (int i = 0; i < list.size(); i++) { System.out.print(list.get(i) + " ");// 输出1，2，3 } // 使用for each循环 for (Integer i : list) { System.out.print(i + " ");// 输出1，2，3 } // 使用迭代器 Iterator iterator = list.listIterator(); while (iterator.hasNext()) { // iterator.next()用于获取list中的下一个元素 // 注意 迭代器指针刚开始并不指向第一个元素 System.out.print(iterator.next() + " ");// 输出1，2，3 } }
五.ArrayList的扩容机制(源码剖析)
先来观察一下以下代码
public static void main(String[] args) { List<Integer> list = new ArrayList<>(); for (int i = 0; i < 100; i++) { list.add(i); } }
这段代码有缺陷么？首先，我们知道ArrayList的构造方法有三种，不带参数的构造方法会自动为数组分配一个默认容量，这个默认容量是10，很明显，我们这里插入了100个元素，则必然会触发扩容机制，我们需要知道 ArrayList是怎么扩容的？以及他的扩容方式是否真的合理呢？
先来看ArrayList 的相关属性
观察一下源码中是如何触发扩容机制的
下面讲解扩容机制
总结：
1.检测是否真的需要扩容，如果需要，使用grow进行扩容
2.预估需要的新内存大小
- 先按照原先1.5倍的大小进行扩容
- 如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容
- 真正扩容之前检测是否能扩容成功，防止太大导致扩容失败(判断扩容后的大小与> MAX_ARRAY_SIZE的关系)
3.使用copyOf进行扩容
六. ArrayList的一道题目
https://leetcode.cn/problems/pascals-triangle/
代码实现:
class Solution { public List<List<Integer>> generate(int numRows) { // 先创建一个List用于存放杨辉三角 List<List<Integer>> ret = new ArrayList<>(); // 处理第一行 List<Integer> row = new ArrayList<>(); row.add(1); ret.add(row);// 把第一行插入到ret中 // 处理中间行 for (int i = 1; i <numRows ; i++) { List<Integer> curRow = new ArrayList<>(); curRow.add(1);// 每一行的第一个元素都是1 // 处理中间元素 // 先获取前一行 ret.get(i-1) List<Integer> prevRow = ret.get(i-1); for (int j = 1; j < i ; j++) { int x = prevRow.get(j-1)+prevRow.get(j); curRow.add(x); } curRow.add(1);// 每一行的最后一个元素都是1 // 最后不要忘记把curRow插入到ret中 ret.add(curRow); } return ret; } }
七.ArrayList的问题及思考
1.
ArrayList的底层使用连续的内存空间，虽然数据检索的效率很高，但是对于数据的插入和删除操作均需要挪动大量的数据，效率较慢
2.
ArrayList的扩容机制是按照原数组大小的1.5倍进行扩容，但是有可能扩容之后造成大量空间的浪费(有很多空间并没有被使用)，同时增容需要拷贝数据，释放旧空间，会有不小的消耗
给大家留一个思考题：如何解决上述问题呢？答案请见下期博客！！！
