[Java集合]ArrayList

ArrayList介绍

ArrayList是一个带类型参数的泛型类,其隶属于Java集合框架.
初期学习Java时,我将其当作自动扩容的数组使用,可以说最是熟悉不过.
现在以Java集合框架角度讨论.

ArrayList实现了List接口,List是著名的线性表,说明了ArrayList是一个顺序容器.
底层结构:
Object[] elementData
int size
一个数组和跟踪数组有效数据大小.

ArrayList基础使用

构造器

public ArrayList() ; :构造一个空的数组列表.
public ArrayList(int initialCapacity) ;: 指定容量构造一个空数组列表.
public ArrayList(Collection<? extends E> c) ;: 创建一个包含指定集合元素的 ArrayList 对象．

基本操作

1. public boolean add(E e):在数组列表的末尾追加元素,返回值始终为true.
   该方法最早出现在Collection接口,这里具体实现.
2. int size():返回当前数组列表存储的元素个数.
   该方法最早出现在Collection接口,这里具体实现.
3. void add(int index, E element) :往指定位置插入元素.
   该方法最早出现在List接口,这里具体实现.
4. boolean addAll(Collection<? extends E> c) :尾插 c 中的元素.
   该方法最早出现在Collection接口,这里具体实现.
5. E remove(int index) :删除 index 位置元素,并将后面的元素依次往前移.
   该方法最早出现在List接口,这里具体实现.
6. boolean remove(Object o) :删除遇到的第一个 o,返回值
   该方法最早出现在Collection接口,这里具体实现.
7. void clear() :清空数组列表.
   该方法最早出现在Collection接口.
8. boolean contains(Object o) 判断 o 是否在数组列表内.
   内部实现是调用indexOf()方法返回的值是否有效判断.
9. int indexOf(Object o) 返回第一个 o 所在下标.顺序查找
10. int lastIndexOf(Object o) 返回最后一个 o 的下标.逆序查找
11. List<E> subList(int fromIndex, int toIndex) 截取部分 list.

获取长度不是.length,也不是.length(),而是size().—我以前经常弄错
关于E remove(int index) 和boolean remove(Object o) 这两个方法.
假设我要如此调用list.remove(2);编译器会怎么理解呢?会报错吗?
Java 支持自动装箱和拆箱,int类型在传参时会自动装箱成Integer.
这里的2理解为index,还是o?Java编译器默认选择前者,会认为你执行的操作是删除下标为2的值(前者),而不是理解为删除第一次出现值2的数(后者).
因此,为避免这种混淆.
list.remove(Integer.valueOf(2));//手动装箱一下这样可以正确索引到Object o的方法.
相比最初的Collection数组列表的增删操作可以添加索引操作
subList:subList不是拷贝了列表对应区间部分.而是在内存上引用了对应部分.
比如下文的subList的[0,1]区间对应原list的[1,2]区间,它们是同一块内存.
意味着通过其中一方修改可以从另外一方反映出来.
另外,参数中的fromIndex和toIndex是左闭右开区间,和String的subString方法相同.

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);System.out.println("修改前:"+ list);List<Integer> subList = list.subList(1,3);//获取[1,3)区间的子列表.subList.set(1,666);System.out.println("修改后:"+ list);}

打印结果证明,对subList的修改影响了原list,说明是指向同一块内存.
修改前:[1, 2, 3, 4, 5]
修改后:[1, 2, 666, 4, 5]

访问数组列表元素.

虽然称为数组列表,但我们不能像数组那样通过[]访问甚至修改元素.
而且Java不支持程序员搞C++那样的运算符重载.
所以相关操作,都通过对应方法调用实现.
List接口提供了两种方法.

1. E get(int index) :获取下标 index 位置元素.

 public E get(int index) {Objects.checkIndex(index, size);return elementData(index);}

2. E set(int index, E element):将下标 index 位置元素设置为 element,并返回修改前的值.

   public E set(int index, E element) {Objects.checkIndex(index, size);E oldValue = elementData(index);elementData[index] = element;return oldValue;}

3. E elementData(int index) { return (E) elementData[index]; }:上面调用的elementData方法,用于获取数组元素,不公开接口.

ArrayList的遍历操作.

1. 通过索引Index set,get方法 和 循环:请自己实现相关代码,不举例
2. fo each循环:

List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);for(Integer x:list){System.out.print(x+" ");}

3. 迭代器遍历

迭代器

Java迭代器（Iterator）是 Java 集合框架中的一种机制,用于遍历实现Collection接口的类对象.本质是因为Collection继承Iterable接口.该接口提供了一个生成迭代器对象的接口.
记住,实现Map的接口的类不能使用迭代器,如HashMap,TreeMap这类映射关系不能使用.
其它如List,Queue,Deque,Set.都直接或间接继承Collection接口.其后的实现类可以通过iterator()方法,生成一个迭代器对象.
先看一下例子吧:

	 List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);Iterator<Integer> it = list.iterator();while(it.hasNext()){System.out.println(it.next());}

需注意Iterable与Iterator的区别.
Iterable是提供生成迭代器的方法接口.----就是提供一个返回类型为Iterator的函数
Iterator是迭代器内部遍历的方法(),hasNext()).

Iterator接口

它本质是一个工具接口.独立于集合框架.但功能是遍历有关集合元素.
如先前的Compareable,Cloneable接口,Arrays工具类.独立,于集合类及接口无任何继承拓展关系.
E next(); - 返回迭代器的下一个元素，并将迭代器的指针移到下一个位置。
next的方法用于遍历集合类对象,如果已经走到末尾,则抛出NoSuchElelementException
boolean hasNext() ;- 用于判断集合中是否还有下一个元素可以访问。
void remove(); - 从集合中删除迭代器最后访问的元素。—(可选项)

使用说明:
初始你可以认为起始位置指向数组下标-1处.next()方法使得先偏移一位并返回值.hasNext()方法检测是否走到末尾.
推荐先调用hasNext(),再调用next()方法.这样可以避免next抛异常终止程序.

for each循环本质是迭代器遍历,只不过编译器帮助我们转化了这一步,使得操作简便一点,不用像这样反复调函数.
所以其使用条件和迭代器一样,必须对实现Iterable接口,也可以说实现Collection接口的集合类对象适用.

Iterable

还是说明一下Iterable接口的方法.

public interface Iterable<E>{Iterator<E> iterator();//......
}

你可能还是很疑惑,迭代器到底怎么回事?
怎么实现的?
粗略来说(不准确,仅供理解),就是各个具体类都有一个内部类实现Iterator接口,然后其类自身实现Iterator<E> iterator();方法.
这样通过c.iterator(),让一个迭代器变量接收.调用上面三个方法达到遍历的效果.
尽情地去翻源码吧,或者看到这儿给你个链接.

后续有关ListIterator会在其它集合类说明,包括set,queue接口的迭代器使用等等.

Oj练习

杨辉三角

public List<List<Integer>> generate(int numRows){List<List<Integer>> matrix = new ArrayList<>();//处理第一行:var list0 = new ArrayList<Integer>();list0.add(1);matrix.add(list0);for(int i=1;i<numRows;i++){//从第二行开始,根据公式构建List<Integer> list = new ArrayList<>();matrix.add(list);list.add(1);for(int j=1;j<i;j++){//计算中间元素:int val = matrix.get(i-1).get(j-1)+matrix.get(i-1).get(j);list.add(val);}list.add(1);}return matrix;}

Shuff Array

class Solution {private ArrayList<Integer> list;private int[] initArray;public Solution(int[] nums) {initArray = Arrays.copyOf(nums,nums.length);list = new ArrayList<>();for(int i=0;i<nums.length;i++){list.add(nums[i]);}}public int[] reset() {return Arrays.copyOf(initArray,initArray.length);}private void swap(ArrayList<Integer> nums,int i,int j){int tmp = nums.get(i);nums.set(i,nums.get(j));nums.set(j,tmp);}public int[] shuffle() {int n=list.size();Random rand = new Random();for(int i=n-1;i>0;i--){//随机选择一个索引并交换,范围[0..j];int j = rand.nextInt(i+1);swap(list,i,j);}int[] shuffledArray = new int[n];for(int i = 0; i < n; i++) {shuffledArray[i] = list.get(i);}return shuffledArray;}
}

Remove Element

class Solution {public int removeElement(int[] nums, int val) {ArrayList<Integer> list = new ArrayList<>();for(int x:nums){//将数组元素拷贝到数组列表list.add(x);}//循环删除特定元素.while(list.remove(Integer.valueOf(val)));//计算列表长度,即是"删除操作"后的数组长度int size = list.size();for(int i=0;i<size;i++){//拷贝有效值nums[i] = list.get(i);}//返回列表大小.return size;}
}

class Solution {
//正经解法public int removeElement(int[] nums, int val) {int src = 0;int dst = 0;while (dst < nums.length){if (nums[dst] != val){nums[src++] = nums[dst++];}else{dst++;}}return src;}
}

结尾

回顾数据结构所学.
ArrayList支持随机访问,给定下标查询速度为$O(1)$.
get_At(i);
set_At(i,x);
不支持频繁插入删除,时间复杂度$O(n).$
delete_last(); insert_last时间复杂度:$O(1)$
delete_first(); insert_first时间复杂度:$O(n)$
delete_At(i); insert_At(i)时间复杂度:$O(n)$