数据结构（Java）：顺序表集合类ArrayList

1、线性表

线性表，在逻辑结构上是连续的（可理解为连续的一条直线，一对一的关系），而在物理结构上不一定连续，通常以数组和链式结构进行存储。

线性表是一种在实际中广泛使用的数据结构，常见的线性表有：顺序表、链表、栈、队列......

2、顺序表

顺序表是线性表的一种，其物理地址是连续的，并采用数组的的存储结构，在数组上完成数据的增删查改。

3、集合类ArrayList

在Java集合框架中，ArrayList是一个泛型类，并且实现了List接口，是Java为我们封装好的顺序表。

当我们想存储哪种类型的元素时，都可以通过泛型传参来构建相应类型的顺序表。

接下来，让我为大家仔细讲解一下ArrayList这个集合类。

3.1 ArrayList的成员变量

我们通过观察ArrayList的源码，得到其成员变量如下：

已知，DEFAULT_CAPACITY是指默认容量（10），elementData是用来实际存储数据的数组，size记录顺序表数据的数量，剩下的两个数组均为空数组。

想要知道他们的用途，我们还需要观察ArrayList的构造方法。

3.2 ArrayList的构造方法

通过观察源码，我们依然可以得出其构造方法：

接下来，我们逐个分析。

3.2.1 带参构造之public ArrayList(int initialCapacity)

不难看出，我们传入的参数就是我们初始化顺序表时的容量（即大小）。

通过if-else语句可以看出：

1.传入的参数为正数时，初始化的大小即为参数值。

2.传入的参数为0时，该顺序表数组的引用指向的就是成员变量中的空数组。

3.传入的参数为负数时，则会抛出异常（数组大小肯定为正数）。

public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>(10);//初始容量为10
    }

3.2.2 无参构造之public ArrayList()

这个构造方法就更简单了，无参构造时，该顺序表数组的引用指向的也是成员变量中的空数组。

public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
    }

3.2.1 带参构造之public ArrayList(Collection<? extends E> c)

大家看到这个构造方法时，是不是愣住了一下子，哈哈哈~，不要慌张，听我道来。

我们先来看这个参数Collection，Collection是一个接口，不知道大家是否还有印象，它曾出现在集合框架中的顶层：

而<>中的内容，"？"是指通配符（这里了解即可），extends我们在讲解泛型时就已经知道，这规定了通配符的上界为E。

也就是说，该构造方法所传参数必须满足以下几点：

1.实现了Collection接口

2.所具备的泛型必须是E或者E的子类

也就说，我们也可以将另一个顺序表当做这个顺序表构造方法的参数传入。

代码示例：

public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        ArrayList<Integer> list1 = new ArrayList<>(list);//将list当做顺序表构造方法的参数传入
        list1.add(99);
        list1.add(100);
        System.out.println(list1);//[1, 2, 3, 99, 100]
    }

3.3 ArrayList的扩容机制

在上面讲顺序表的构造方法时，我们讲当构造方法为无参构造或者传入的参数为零时，数组是空数组。既然是空数组，那么我们如何进行数据的添加或者插入呢？以及当数组容量满时，如何进行数据的添加或者插入呢？

实际上，当无参构造或者传入的参数为零时，经过源码的处理，也是将数组的初始容量设置成了DEFAULT_CAPACITY（10）。

且，ArrayList是一个动态顺序表，即：在插入元素的过程中会以1.5倍自动扩容（调用Arrays的copyOf方法进行扩容）。

3.4 ArrayList的常用方法

ArrayList提供了很多的方法，在这里，我将列举较常用的方法。

3.4.1 add方法（数据插入）

该方法实现了重载，分别在顺序表尾部插入和在指定下标位置插入。

3.4.1.1 尾部插入数据

方法格式：

代码示例：

3.4.1.2 指定位置插入数据

方法格式：

代码示例：

3.4.2 addAll方法

方法格式：

同样的道理，传入的参数必须实现了Collection接口，并且其泛型参数的上界为E（上文已经进行了讲解）。

调用该方法，可以将参数的数据尾插到当前顺序表当中。

代码演示：

3.4.3 remove方法（数据删除）

3.4.3.1 删除指定下标数据

方法格式：

注意：该方法的返回值，为所删除的数据。

3.4.3.2 删除确定数值的数据

方法格式：

因为ArrayList是一个泛型类，数组中的元素都为一个对象，所以我们应该传入相应类型的对象作为参数。

代码示例：

注意：我们看到，remove方法中的参数被划上了横线，这说明该方法的这种传参调用方式被废弃了（不常用了），但是我们仍然可以使用。

3.4.4 get方法（获取数据）

方法格式：

传入下标，返回指定下标的数据。

3.4.5 set方法（修改数据）

方法格式：

修改指定下标的数据。、

3.4.6 set方法（清空顺序表）

方法格式：

该方法的底层就是：将有效数据修改为null（各元素为引用类型），再将size（数组大小）置为0。

3.4.7 subList方法（截取顺序表）

方法格式：

该方法能够截取顺序表的指定区间（区间为左闭右开），并返回截取后的顺序表（注意：返回类型为List，是ArrayList实现的一个接口）。

代码示例：

需要注意的，新截取的顺序表list1和原来的顺序表list，指向的的是同一块空间：

也就是说，修改顺序表list1中的数据，list中的数据也会被修改。

3.5 ArrayList的遍历

3.5.1 for循环遍历

代码示例：

public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        int size = list.size();
        for (int i = 0; i < size; i++) {
            int data = list.get(i);//得到i下标的元素
            System.out.print(data+" ");
        }
        System.out.println();
    }

3.5.2 for-each循环遍历

因为顺序表实际上是个数组，我们可以通过for-each循环来遍历顺序表：

public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        for (int data : list) {
            System.out.print(data+" ");
        }
    }

3.5.3 迭代器遍历

3.5.3.1 Iterator迭代器

在ArrayList中，存在iterator方法：

通过调用这个方法，我们可以得到一个迭代器对象，再通过这个对象将数据一个一个打印，直到全部打印完成。

public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        
        Iterator<Integer> iterator =  list.iterator();
        while (iterator.hasNext()) {//hasNext方法 用来判断是否有下一个数据
            int data = iterator.next();//next方法是 得到下一个数据
            System.out.print(data+" ");
        }
    }

hasNext方法用来判断是否有下一个数据。

next方法是得到下一个数据。

3.5.3.2 ListIterator迭代器

与Iterator迭代器用法相同，我们可以通过listIterator来遍历顺序表：

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

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

3.5.3.3 Iterator迭代器和ListIterator迭代器的关系

首先，这两者均为接口。

其次，我们通过源码可以发现，ListIterator拓展了Iterator，也就是说，ListIterator迭代器拓展了Iterator迭代器的功能，其方法更加丰富。

3.5.3.3.1 ListIterator迭代器的新增功能

这里，我们演示一个ListIterator的新增方法。

通过源码，我们可以发现ArrayList的listIterator方法可以传入参数，

调用listIterator方法并传入参数，得到的迭代器就会来到该下标的元素之后的位置，

我们再使用ListIterator新增的hasPrevious和previous方法就可以实现对顺序表从后往前的遍历：

代码：

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

        int size = list.size();
        ListIterator<Integer> listIterator = list.listIterator(size);
        while (listIterator.hasPrevious()) {
            int data = listIterator.previous();
            System.out.print(data+" ");
        }
    }

OK~本次博客到这里就结束了，

感谢大家的阅读~欢迎大家在评论区交流问题~

如果博客出现错误可以提在评论区~

创作不易，请大家多多支持~