【数据结构】ArrayList详解

前言

1. 线性表

2. 顺序表

3. ArrayList的介绍和使用

3.1 语法格式

3.2 添加元素

3.3 删除元素

3.4 截取部分arrayList

3.5 其他方法

4. ArrayList的遍历

5.ArrayList的扩容机制

6. ArrayList的优缺点

结语

前言

在集合框架中，ArrayList就是一个普通的类，它实现了List接口。作为我们学习初阶数据结构的入门知识，ArrayList还是很好理解的，在学习它之前，我们也得先来简单了解下线性表以及顺序表

1. 线性表

线性表（Linear List）是零个或多个相同类型数据元素的有限序列。它是一种被广泛使用的数据结构，常见的线性表有：顺序表、链表、栈、队列……

线性表在逻辑上是线性结构，我们可以看作一条连续的直线，但是在物理结构上不一定是连续的，像顺序表，它在逻辑结构上和物理结构上都是连续的；而链表在物理结构上就不是连续的

2. 顺序表

从上面的图中我们可以看出，顺序表是物理结构和逻辑结构都连续的线性表，一般情况下采用数组存储，说白了，顺序表就是一个数组。ArrayList可以被认为是顺序表的一种实现

3. ArrayList的介绍和使用

3.1 语法格式

ArratList类位于java.util包当中，我们在使用前得先导包

import java.util.ArrayList;

ArrayList<E> arrayList = new ArrayList<>();

又因为ArrayList实现了List接口，所以我们也可以用接口来引用ArrayList对象，List类也需要导包

import java.util.List;
import java.util.ArrayList;

List<E> list = new ArrayList<>();

E：泛型数据类型，为可以用来限制arrayList的类型，但是只能引用数据类型
对于两种arrayList的创建，我更推荐使用第一种，这样能实现的方法也会更多

除了以上两种构造（无参），其实还有另外两种构造方法

//指定顺序表的初始容量
ArrayList<E> arrayList = new ArrayList<>(int initialCapacity);

//利用其他Collection构建ArrayList
ArrayList<E> arrayList = new ArrayList<>(Collection<? extends E> c);

我们经常使用的就是第一、二种，第三种比较少用到

3.2 添加元素

boolean add（E e）：在列表尾处插入e

void add（int index，E element）：将element插入到下标为index位置

        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        System.out.println(arrayList);
        arrayList.add(1,200);
        System.out.println(arrayList);

而且我们还可以直接打印list，因为它已经重写了toString方法。运行结果如下

boolean addAll（Collection<? extends E> c）：尾插一组数据（可以是其他顺序表）

        ArrayList<Integer> arrayList1 = new ArrayList<>();
        arrayList1.add(1);
        arrayList1.add(2);
        arrayList1.add(3);
        ArrayList<Integer> arrayList2 = new ArrayList<>(arrayList1);
        System.out.println(arrayList2);

运行结果如下

3.3 删除元素

E remove（int index）：删除下标为index的元素

boolean remove（Object o）：删除遇到的第一个o元素

        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        System.out.println(arrayList);
        arrayList.remove(1);//删除下标为1的元素
        arrayList.remove(Integer.valueOf(2));//删除值为2的元素
        System.out.println(arrayList););

运行结果如下

注意：当我们想通过值来删除元素的时候，传进去的值要记得装箱，也就是将基本类型转为引用类型。像上面的例子，我们想要删除元素2，就得传入Integer.valueOf(2)才能实现

3.4 截取部分arrayList

List<E> subList（int fromIndex，int toIndex）：截取部分list（左闭右开）

要注意，该方法返回类型为List<E>，所以我们必须用List<E>去引用过arrayList对象
该方法实际上不是生成一个新的顺序表，而是直接引用了arrayList里的地址，所以当我们改变list里的值时，arrayList里的值也会发生改变

        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        //截取部分list [左闭右开)
        List<Integer> list = arrayList.subList(0,2);
        System.out.println(list); //1,2
        //但是它并不是重新生成，而是指向同一引用
        list.set(0,100);
        System.out.println(arrayList);//arrayList里的元素也会被改变

运行结果如下

3.5 其他方法

有需要时就直接查询，文档链接：ArrayList （Java SE 17 和 JDK 17） (oracle.com)

4. ArrayList的遍历

ArrayList有三种遍历方法：

for循环
foreach循环
使用迭代器

        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        //打印一：for
        for (int i = 0; i < arrayList.size(); i++) {
            System.out.print(arrayList.get(i)+" ");
        }
        //打印二：foreach
        for (Integer x : arrayList) {
            System.out.print(x + " ");
        }
        System.out.println();

运行结果如下

使用迭代器打印，我们就只能使用List<E>接口来引用arrayList，还有要导包

import java.util.Iterator; import java.util.ListIterator;

        //打印三：迭代器
        //默认是从 0 下标开始打印
        System.out.println("===Iterator===");
        Iterator<Integer> it =  arrayList.iterator();//创建迭代器
        while (it.hasNext()) {
            System.out.print(it.next() +" ");
        }
        System.out.println();

        System.out.println("===listIterator倒着打印===");
        //从 指定位置 开始打印     list1.size()
        ListIterator<Integer> it2 =  arrayList.listIterator(arrayList.size());
        while (it2.hasPrevious()) {
            System.out.print(it2.previous() +" ");
        }
        System.out.println();

运行结果如下