【数据结构】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 arrayList = new ArrayList<>();

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

import java.util.List;
import java.util.ArrayList;
 
List list = new ArrayList<>();

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

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

//指定顺序表的初始容量
ArrayList arrayList = new ArrayList<>(int initialCapacity);
 
//利用其他Collection构建ArrayList
ArrayList arrayList = new ArrayList<>(Collectionextends E> c);

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

---

3.2 添加元素

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

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

        ArrayList 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 c）：尾插一组数据（可以是其他顺序表）

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

运行结果如下 

---

3.3 删除元素

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

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

        ArrayList 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 subList（int fromIndex，int toIndex）：截取部分list（左闭右开）

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

        ArrayList arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        //截取部分list [左闭右开)
        List 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有三种遍历方法：

1. for循环
2. foreach循环
3. 使用迭代器

        ArrayList 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接口来引用arrayList，还有要导包

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

        //打印三：迭代器
        //默认是从 0 下标开始打印
        System.out.println("===Iterator===");
        Iterator it =  arrayList.iterator();//创建迭代器
        while (it.hasNext()) {
            System.out.print(it.next() +" ");
        }
        System.out.println();
 
        System.out.println("===listIterator倒着打印===");
        //从 指定位置 开始打印     list1.size()
        ListIterator it2 =  arrayList.listIterator(arrayList.size());
        while (it2.hasPrevious()) {
            System.out.print(it2.previous() +" ");
        }
        System.out.println();

运行结果如下

这个方法适当了解就行 

---

5.ArrayList的扩容机制

在前面的学习中，我们使用到了add（）方法来添加元素，但我们在创建顺序表的时候却没有给它指定容量大小，它的大小肯定为0，那为什么还能正常添加而不报错呢？

其实ArrayList它是一个动态类型的顺序表，我们在插入元素的过程中，它会自动扩容，因此不需要我们担心容量太小而不够添加元素

6. ArrayList的优缺点

优点：因为ArrayList是一个顺序表，非常适合根据下标查找和更新的场景，此时的时间复杂度为O（1）

缺点：也正是因为ArrayList是一个顺序表，因此当我们想在任意位置插入或删除元素时，往往需要将后面一堆的元素进行移动，时间复杂度为O（n）；再则，当我们想要存放数据是，它的扩容机制是为1.5倍或2倍扩容，这样可能会导致内存空间的浪费

结语

今天我们一起学习了ArrayList，知道了它的构造，使用方法，优缺点……而想要解决ArrayList的痛点，我们可以使用链表来规避这些问题，这就是我们下篇博文要写的内容，敬请期待吧

希望大家能喜欢这篇文章，有总结不到位的地方还请多多谅解，若有出现纰漏，希望大佬们看到错误之后能够在私信或评论区指正，博主会及时改正，共同进步！