Java顺序表（2）

🐵本篇文章将对ArrayList类进行讲解

一、ArrayList类介绍

上篇文章我们对顺序表的增删查改等方法进行了模拟实现，实际上Java提供了ArrayList类，而在这个类中就包含了顺序表的一系列方法，这样在用顺序表解决问题时就不用每次都去实现它的方法了

再ArrayList类中有下面几个字段：

上述字段会在下面的解释中进行讲解

二、ArrayList的构造方法

ArrayList的构造方法一共有三种

2.1 第一种构造方法

上述代码中，先定义了数组EMPTY_ELEMENTDATA，该数组为空，之后又定义了数组elementData，接下来红色框部分的就是构造方法，该方法有一个参数initialCapacity（即顺序表的初始容量），当initialCapacity > 0时，为elementData分配了长度为initialCapacity大小的空间，当initialCapacity = 0时，将elementData赋值为EMPTY_ELEMENTDATA，也就是此时elementData为空数组，即顺序表现在为空，若initialCapacity为负数，则抛出异常

总结：该构造方法就是给顺序表分配空间的

ArrayList<Integer> arrayList = new ArrayList<>(5); //此时顺序表的长度为5
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);

2.2 第二种构造方法

可以看到此时elementData为一个空数组，那么看下面的代码

ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);

构造方法并没有给顺序表分配空间，为什么此代码编译运行都没有问题？下面通过源码进行解释，首先不带参的构造方法确实没有给顺序表分配空间，那么没有报错的原因只可能是在add方法上

add方法中调用了ensureCapacityInternal方法：

在该方法中调用了ensureExplicitCapacity方法，其参数为calculateCapacity方法的返回值，该方法的参数分别为elementData数组和minCapacity先看calculateCapacity方法：

上述代码中的DEFAULT_CAPACITY是默认容量：10，minCapacity为1，所以这里将10作为该方法的返回值并作为ensureExplicitCapacity的参数，再去看ensureExplicitCapacity方法：

接下来看grow方法：

总结：

1.对于空的顺序表，第一个add方法会进行扩容，将顺序表的扩容为默认容量10

2.add方法的扩容是按照1.5倍扩容的

2.3 第三种构造方法

该构造方法的参数部分：

Collection<? extends E>为类型，c是变量

Collection是一个接口，ArrayList类实现了这个接口，所以这里的变量c可以是ArrayList类型，尖括号中？是通配符，继承了E类，意思就是尖括号中的泛型必须是E类型或E的子类型

三、ArrayList的一些方法

ArrayList类提供的方法大部分和上篇文章中模拟实现的方法一致，这里讲解一些没有模拟实现的方法：

1. boolean addAll(Collection<? extends E> c)

该方法为将一个顺序表的所有元素尾插到另一个顺序表：

public static void main(String[] args) {
    ArrayList<Integer> arrayList = new ArrayList<>();
    arrayList.add(1);
    arrayList.add(2);
    ArrayList<Integer> list = new ArrayList<>();
    list.add(3);
    list.addAll(arrayList);
    System.out.println(list); //结果为 [3, 1, 2]
}

2. E remove(int index)

删除index位置的元素：

    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.remove(0);
        System.out.println(arrayList); //结果为 [2]
    }

3. List<E> subList(int fromIndex, int toIndex)

以左闭右开的区间截取顺序表中从fromIndex到toIndex的元素，注意：这里的截取并不是指向一个新的对象，它依然指向原来的对象

    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);

        List<Integer> list = arrayList.subList(0, 2);//list依然指向原来的对象
        System.out.println(list); //结果为 [1, 2]

        list.set(0, 100);
        System.out.println(list); //[100, 2]
        System.out.println(arrayList); //[100, 1, 2]
    }

四、ArrayList的遍历

先创建一个顺序表：

ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);

4.1 for循环

for (int i = 0; i < arrayList.size(); i++) {
    System.out.print(arrayList.get(i) +" ");
}

4.2 for-each循环

for(Integer x : arrayList) { //:左边为顺序表中元素的类型+变量
    System.out.print(x +" ");
}

4.3 迭代器

1.Iterator接口中iterator()方法

Iterator<Integer> it = arrayList.iterator();
while(it.hasNext()) { 
    System.out.print(it.next() +" ");
    //判断是否有下一个元素，如果有则打印下一个元素，并将it指向下一个元素
}

2.ListIterator接口中listIterator()方法

ListIterator接口继承了Iterator接口，也可以作为迭代器遍历ArrayList

ListIterator<Integer> it1 = arrayList.listIterator();
while(it1.hasNext()) {
    System.out.print(it1.next() +" ");
}

3.利用迭代器从后往前打印

ListIterator<Integer> it2 = arrayList.listIterator(arrayList.size());
                                                    //这里要将顺序表的长度作为参数传过去
while(it2.hasPrevious()) {
    System.out.print(it2.previous() +" ");
    //判断是否有前一个元素，如果有则打印前一个元素，并将it指向前一个元素
}