开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【Java---数据结构】ArrayList -> 正文阅读

[数据结构与算法]【Java---数据结构】ArrayList

一、初识泛型

💦泛型的引入

实现过的顺序表，只能保存 int 类型的元素，如果现在需要保存指向 Person 类型对象的引用的顺序表，应该如何解决？

首先，多态中已知，父类的引用可以指向子类的对象。
其次，Object 是 java 中所有类的祖先类。
要解决上述问题，就是将顺序表的元素类型定义成 Object 类型，这样 Object 类型的引用就可以指向 Person 类型的对象或者指向 String 类型的对象。

🌊代码示例：

class MyArrayList{
    private Object[] array; //保存Object类型的顺序表元素
    private int usedSize; //顺序表有效数据个数
    public MyArrayList(){
        this.array = new Object[10];
    }
    //插入元素
    public void add(Object val){
        this.array[usedSize] = val;
        usedSize++;
    }
    //获取pos位置的元素
    public Object get(int pos){
        return this.array[pos];
    }
}

class Person{
    private String name;
    private int age;
}
public class TestDemo2 {
    public static void main(String[] args) {
        MyArrayList myArrayList1 =new MyArrayList();
        myArrayList1.add(new Person());
        MyArrayList myArrayList2 = new MyArrayList();
        myArrayList2.add(1);
        myArrayList2.add("abc");
        //myArrayList2 引用指向的数组，下标为1的元素是字符串
        //但是myArrayList2 引用指向的数组的返回值是Object类型，所以要强制类型转换
        String ret =(String) myArrayList2.get(1);
    }
}

将顺序表的元素类型定义成 Object 类型就可以很自由的存储指向任意类型对象的引用到顺序表。
但是每次取出数据都需要强制类型转换。所以需要一种机制，可以增加编译期间的类型检查；取消类型转换的使用。
因此就产生了泛型。

💦泛型的定义

这里只是简单介绍一下泛型，泛型的具体内容会在后面的文章中详细介绍。

// 1. 尖括号 < > 是泛型的标志
// 2. E 是类型变量(Type Variable)，变量名一般要大写
// 3. E 在定义时是形参，代表的意思是 MyArrayList 最终传入的类型，但现在还不知道
class MyArrayList<E>{
    private E[] array; //保存Object类型的顺序表元素
    private int usedSize; //顺序表有效数据个数
    public MyArrayList(){
        this.array = (E[]) new Object[10]; //这并不是一个正确的写法，只是为了演示代码
        //正确的写法是通过反射进行创建。
    }
    //插入元素
    public void add(E val){
        this.array[usedSize] = val;
        usedSize++;
    }
    //获取pos位置的元素
    public E get(int pos){
        return this.array[pos];
    }
}

注意：泛型类可以一次有多个类型变量，用逗号分割。

public class MyArrayList<E,S> {
    private E[] array;
    private int usedSize;
    ...
}

泛型是作用在编译期间的一种机制，即运行期间没有泛型的概念。
泛型代码在运行期间，就是上面提到的，利用 Object 达到的效果。

💦泛型类的使用

（1）在编译期间自动对类型进行检查

public class TestDemo2 {
    public static void main(String[] args) {
        MyArrayList<String> myArrayList = new MyArrayList<>();
        myArrayList.add("ABC");
        //myArrayList.add(12); error
    }
}

（2）自动对类型进行强制类型转换

public class TestDemo2 {
    public static void main(String[] args) {
        MyArrayList<String> myArrayList = new MyArrayList<>();
        myArrayList.add("ABC");
        myArrayList.add("DEF");
        String ret = myArrayList.get(1);
        System.out.println(ret);
    }
}

//运行结果：DEF

?泛型类的使用方式：

只需要在所有类型后边跟尖括号，并且尖括号内是真正的类型，即E可以看作的最后的类型。
String 只能想象成 E 的类型，但实际上 E 的类型还是 Object。

?泛型中尖括号里的内容不参与类型的组成

public class TestDemo2 {
    public static void main(String[] args) {
        //myArrayList1 引用的类型： MyArrayList<String>
        MyArrayList<String> myArrayList1 = new MyArrayList<>();
        MyArrayList<Integer> myArrayList2 = new MyArrayList<>();
        //打印内容：类型@地址值
        System.out.println(myArrayList1);
        System.out.println(myArrayList2);
    }
}

//运行结果：
MyArrayList@4554617c
MyArrayList@74a14482

打印的内容：类型 @ 地址值，类型中并没有尖括号里面内容。

面试问题：泛型是怎么编译的？

泛型是编译时期的一种机制，称为擦除机制。（将尖括号中的内容全部擦成Object）。

💦泛型总结

泛型是为了解决某些容器、算法等代码的通用性而引入，并且能在编译期间做类型检查。
泛型利用的是 Object 是所有类的祖先类，并且父类的引用可以指向子类对象的特定而工作。
泛型是一种编译期间的机制，即 MyArrayList<Person> 和 MyArrayList<Book> 在运行期间是一个类型。
泛型是 java 中的一种合法语法，标志就是尖括号 <>。

二、包装类(Wrapper Class）

Object 引用可以指向任意类型的对象。但有例外，8 种基本数据类型不是对象，那岂不是刚才的泛型机制要失效了？实际上也确实如此。

为了解决这个问题，java 引入了一类特殊的类，即这 8 种基本数据类型的包装类，在使用过程中，会将类似 int 这样的值包装到一个对象中去。

💦基本数据类型和包装类直接的对应关系

?基本就是类型的首字母大写，除了 Integer 和 Character。

💦包装类的使用，装箱(boxing)和拆箱(unboxing)

装箱（装包）：将简单类型的数据转变为包装类类型的数据
拆箱（拆包）：将包装类类型的数据转变为将简单类型的数据

🍓隐式的装箱、拆箱

public class TestDemo1 {
    public static void main(String[] args) {
        Integer a = 20;//【隐式的】装箱（装包）
        int b = a; //【隐式的】拆箱（拆包）
        System.out.println(a+" "+b);
    }
}

//运行结果：20 20

底层的实现

🍓显式的装箱、拆箱

public class TestDemo1 {
    public static void main(String[] args) {
        Integer a1 = Integer.valueOf(20); //【显式的】装箱（装包）
        Integer a2 = new Integer(20); //【显式的】装箱（装包）

        int b1 = a1.intValue(); //【显式的】拆箱（拆包）
        double b2 = a1.doubleValue(); //【显式的】拆箱（拆包）
        System.out.println(a2+" "+b2);
    }
}

//运行结果：20 20.0

?面试题：

public class TestDemo1 {
    public static void main(String[] args) {
        Integer a1 = 123;
        Integer a2 = 123;
        System.out.println(a1==a2);
        System.out.println("==============");
        Integer b1 = 129;
        Integer b2 = 129;
        System.out.println(b1==b2);
    }
}

运行结果：
true
==============
false

这里使用隐式的装箱，在底层调用了valueOf()方法，既然调用了为了valueOf()方法，那么为了解决这个问题，就要从这个方法开始入手。

🚆有了前面内容的铺垫，接下来就可以进入 List 的学习

三、ArrayList与顺序表

💦ArrayList简介

在集合框架中，ArrayList是一个普通的类，实现了List接口，具体框架图如下：

?说明：

ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者
CopyOnWriteArrayList
ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

💦ArrayList使用

?ArrayList 的构造

🌊代码示例：

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

public class TestDemo2 {
    public static void main(String[] args) {
        List<String> list0 = new ArrayList<>();
        //也可以用ArrayList创建
        ArrayList<String> list = new ArrayList<>(10);//可以给容量
        ArrayList<String> list1 = new ArrayList<>(); //如果不给容量默认大小为0
        list1.add("hello");
        list1.add("JAVA");
       // list1.add(1); 编译失败，ArrayList<String>已经限定了，list1中只能存储String类型的元素
        
       //使用另外一个 ArrayList 对list2进行初始化
        ArrayList<String> list2 = new ArrayList<>(list1); // list2 构造好之后，与 list1 中的元素一致
    }
}

?ArrayList 的打印

直接打印（底层调用 toString()方法）
for循环+下标
foreach（因为ArrayList实现了Iterable接口）
使用迭代器

🌊代码示例：

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

public class TestDemo2 {
    public static void main(String[] args) {
        ArrayList<String> list1 = new ArrayList<>();
        list1.add("hello");
        list1.add("JAVA");
        list1.add("ABCD");
        //直接打印
        System.out.println(list1); //底层调用 toString() 方法
        System.out.println("==============");
        //使用下标+for打印
        for (int i = 0;i<list1.size();i++){
            System.out.print(list1.get(i)+" ");
        }
        System.out.println();
        System.out.println("==============");
        //使用foreach打印
        for (String s:list1) {
            System.out.print(s+" ");
        }
        System.out.println();
        System.out.println("==============");
        //使用迭代器打印
       Iterator<String> it1 =  list1.iterator();
       while (it1.hasNext()){
           System.out.print(it1.next()+" ");
       }
        System.out.println();
        System.out.println("==============");
       //使用迭代器List相关打印
        ListIterator<String> it2 =  list1.listIterator();
        while (it2.hasNext()){
            System.out.print(it2.next()+" ");
        }
        System.out.println();
    }
}

//运行结果：
[hello, JAVA, ABCD]
==============
hello JAVA ABCD 
==============
hello JAVA ABCD 
==============
hello JAVA ABCD 
==============
hello JAVA ABCD

💦迭代器 Iterator 与 ListIterator

1、迭代器中的 remove() 方法

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

public class TestDemo2 {
    public static void main(String[] args) {
        ArrayList<String> list1 = new ArrayList<>();
        list1.add("hello");
        list1.add("JAVA");
        list1.add("ABCD");
        Iterator<String> it1 =  list1.iterator();
        while (it1.hasNext()){
            String ret = it1.next();
            if(ret.equals("hello")){
                it1.remove();
            }else {
                System.out.print(ret+" ");
            }
        }
        System.out.println();
        System.out.println("============");
        //使用迭代器List相关打印
        ListIterator<String> it2 =  list1.listIterator();
        while (it2.hasNext()) {
            String ret = it2.next();
            if (ret.equals("hello")) {
                it2.remove();
            } else {
                System.out.print(ret + " ");
            }
        }
        System.out.println();
    }

//运行结果：
JAVA ABCD 
============
JAVA ABCD

Iterator 与 ListIterator 中的 remove()方法用法相同。

?注意：

首先需要使用next方法迭代出集合中的元素，然后才能调用remove()方法，否则集合可能会因为对同一个 Iterator remove 了多次而抛出 IllegalStateException 异常。

2、迭代器中的 add() 方法

ListIterator 中有 add()方法
Iterator 中没有add()方法。

🌊代码示例：

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

public class TestDemo2 {
    public static void main(String[] args) {
        ArrayList<String> list1 = new ArrayList<>();
        list1.add("hello");
        list1.add("JAVA");
        list1.add("ABCD");
        ListIterator<String> it2 =  list1.listIterator();
        while (it2.hasNext()) {
            String ret = it2.next();
            if (ret.equals("hello")) {
                it2.add("world");
            } else {
                System.out.print(ret + " ");
            }
        }
        System.out.println();
        System.out.println("==========");
        System.out.println(list1);
    }
}

运行结果：
JAVA ABCD 
==========
[hello, world, JAVA, ABCD]

💦ArrayList常见操作

1、add(E e) 方法的使用（尾插 e）

🌊代码示例：

import java.util.ArrayList;

public class TestDemo2 {
    public static void main(String[] args) {
        ArrayList<String> list1 = new ArrayList<>();
        list1.add("JavaSE");
        list1.add("JavaWeb");
        list1.add("JavaEE");
        list1.add("JVM");
        System.out.println(list1);
    }
}

//运行结果：[JavaSE, JavaWeb, JavaEE, JVM]

🌌底层 add(E e) 方法

2、add(int index, E element) 方法的使用（将 e 插入到 index 位置）

🌊代码示例：

import java.util.ArrayList;

public class TestDemo2 {
    public static void main(String[] args) {
        ArrayList<String> list1 = new ArrayList<>();
        list1.add("JavaSE");
        list1.add("JavaWeb");
        list1.add("JavaEE");
        list1.add("JVM");
        System.out.println(list1);
        System.out.println("==========");
        list1.add(2,"数据结构");
        System.out.println(list1);
    }
}

//运行结果：
[JavaSE, JavaWeb, JavaEE, JVM]
==========
[JavaSE, JavaWeb, 数据结构, JavaEE, JVM]

🌌底层 add(int index, E element) 方法 ?

3、addAll(Collection<? extends E> c) 方法的使用（尾插 c 中的元素）

此方法是将一个数组中的所有内容插入到另一个数组的后面

🌊代码示例：

import java.util.ArrayList;

public class TestDemo2 {
    public static void main(String[] args) {
        ArrayList<String> list1 = new ArrayList<>();
        list1.add("JavaSE");
        list1.add("JavaWeb");
        list1.add("JavaEE");
        list1.add("JVM");
        System.out.println(list1);
        System.out.println("==============");
        ArrayList<String> list2 = new ArrayList<>();
        list2.add("我是测试list1");
        list2.add("我是测试list2");
        list1.addAll(list2);
        System.out.println(list1);
    }
}

//运行结果：
[JavaSE, JavaWeb, JavaEE, JVM]
==============
[JavaSE, JavaWeb, JavaEE, JVM, 我是测试list1, 我是测试list2]

4、remove(int index) 方法的使用（删除 index 位置元素）

🌊代码示例：

import java.util.ArrayList;

public class TestDemo2 {
    public static void main(String[] args) {
        ArrayList<String> list1 = new ArrayList<>();
        list1.add("JavaSE");
        list1.add("JavaWeb");
        list1.add("JavaEE");
        list1.add("JVM");
        System.out.println(list1);
        System.out.println("==============");
        String ret = list1.remove(2);
        System.out.println(ret);
        System.out.println(list1);
    }
}

//运行结果：
[JavaSE, JavaWeb, JavaEE, JVM]
==============
JavaEE
[JavaSE, JavaWeb, JVM]

🌌底层 remove(int index) 方法

5、remove(Object o) 方法的使用（删除遇到的第一个 o）

🌊代码示例：

import java.util.ArrayList;

public class TestDemo2 {
    public static void main(String[] args) {
        ArrayList<String> list1 = new ArrayList<>();
        list1.add("JavaSE");
        list1.add("JavaWeb");
        list1.add("JVM");
        list1.add("JavaEE");
        list1.add("JVM");
        System.out.println(list1);
        System.out.println("==============");
        boolean ret = list1.remove("JVM");
        System.out.println(ret);
        System.out.println(list1);
    }
}

//运行结果：
[JavaSE, JavaWeb, JVM, JavaEE, JVM]
==============
true
[JavaSE, JavaWeb, JavaEE, JVM]

🌌底层 remove(Object o) 方法?

6、get(int index) 方法的使用（获取下标 index 位置元素）

🌊代码示例：

import java.util.ArrayList;

public class TestDemo2 {
    public static void main(String[] args) {
        ArrayList<String> list1 = new ArrayList<>();
        list1.add("JavaSE");
        list1.add("JavaWeb");
        list1.add("JavaEE");
        list1.add("JVM");
        System.out.println(list1);
        String ret = list1.get(1);
        System.out.println(ret);
    }
}

//运行结果：
[JavaSE, JavaWeb, JavaEE, JVM]
JavaWeb

🌌底层 get(int index) 方法 ?

7、set(int index, E element) 方法的使用（将下标 index 位置元素设置为 element）

🌊代码示例：

import java.util.ArrayList;

public class TestDemo2 {
    public static void main(String[] args) {
        ArrayList<String> list1 = new ArrayList<>();
        list1.add("JavaSE");
        list1.add("JavaWeb");
        list1.add("JavaEE");
        list1.add("JVM");
        System.out.println(list1);
        String ret = list1.set(3,"hello");
        System.out.println("原来的字符串："+ret);
        System.out.println(list1);
    }
}

//运行结果：
[JavaSE, JavaWeb, JavaEE, JVM]
原来的字符串：JVM
[JavaSE, JavaWeb, JavaEE, hello]

🌌底层 set(int index, E element) 方法 ??

8、clear() 方法的使用（清空）

🌊代码示例：

import java.util.ArrayList;

public class TestDemo2 {
    public static void main(String[] args) {
        ArrayList<String> list1 = new ArrayList<>();
        list1.add("JavaSE");
        list1.add("JavaWeb");
        list1.add("JavaEE");
        list1.add("JVM");
        System.out.println(list1);
        list1.clear();
        System.out.println(list1);
    }
}

//运行结果：
[JavaSE, JavaWeb, JavaEE, JVM]
[]

🌌底层 clear() 方法 ??

9、contains(Object o) 方法的使用（判断 o 是否在线性表中）

🌊代码示例：

import java.util.ArrayList;

public class TestDemo2 {
    public static void main(String[] args) {
        ArrayList<String> list1 = new ArrayList<>();
        list1.add("JavaSE");
        list1.add("JavaWeb");
        list1.add("JavaEE");
        list1.add("JVM");
        System.out.println(list1);
        System.out.println(list1.contains("JavaEE"));
    }
}

//运行结果：
[JavaSE, JavaWeb, JavaEE, JVM]
true

10、indexOf(Object o) 方法的使用（返回第一个 o 所在下标）

🌊代码示例：

import java.util.ArrayList;

public class TestDemo2 {
    public static void main(String[] args) {
        ArrayList<String> list1 = new ArrayList<>();
        list1.add("JavaSE");
        list1.add("JavaEE");
        list1.add("JavaEE");
        list1.add("JVM");
        System.out.println(list1);
        System.out.println(list1.indexOf("JavaEE"));
    }
}

//运行结果：
[JavaSE, JavaEE, JavaEE, JVM]
1

11、lastIndexOf(Object o) 方法的使用（返回最后一个 o 的下标）

🌊代码示例：

import java.util.ArrayList;

public class TestDemo2 {
    public static void main(String[] args) {
        ArrayList<String> list1 = new ArrayList<>();
        list1.add("JavaSE");
        list1.add("JavaWeb");
        list1.add("JavaWeb");
        list1.add("JVM");
        System.out.println(list1);
        System.out.println(list1.lastIndexOf("JavaWeb"));
    }
}

//运行结果：
[JavaSE, JavaWeb, JavaWeb, JVM]
2

12、subList(int fromIndex, int toIndex) 方法的使用（截取部分 list ,左闭右开）

🌊代码示例：

import java.util.ArrayList;

public class TestDemo2 {
    public static void main(String[] args) {
        ArrayList<String> list1 = new ArrayList<>();
        list1.add("JavaSE");
        list1.add("JavaWeb");
        list1.add("JavaEE");
        list1.add("JVM");
        list1.add("hello");
        List<String> ret = list1.subList(1,3); //[1,3)
        System.out.println(ret);
    }
}

//运行结果：
[JavaWeb, JavaEE]

?subList() 方法并不是将数组中的元素截取出来，而是通过引用指向subList截取的起始位置。

🌊代码示例：?

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

public class TestDemo2 {
    public static void main(String[] args) {
        ArrayList<String> list1 = new ArrayList<>();
        list1.add("JavaSE");
        list1.add("JavaWeb");
        list1.add("JavaEE");
        list1.add("JVM");
        list1.add("hello");
        List<String> ret = list1.subList(1,3);
        System.out.println(ret);
        System.out.println(list1);
        System.out.println("===========");
        ret.set(0,"ABC");
        System.out.println(ret);
        System.out.println(list1);
    }
}

//运行结果：
[JavaWeb, JavaEE]
[JavaSE, JavaWeb, JavaEE, JVM, hello]
===========
[ABC, JavaEE]
[JavaSE, ABC, JavaEE, JVM, hello]

通过运行结果可以看到，修改使用subList()方法截取的内容，原数组中的内容也会被修改。

💦ArrayList的扩容机制

import java.util.ArrayList;

public class TestDemo1 {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < 100; i++) {
            list.add(i);
        }
    }
}

?ArrayList 底层代码分析：

既然数组的大小为0，那么为什么在存放元素的时候并没有发生越界？

这是因为ArrayList是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容。（在add()方法中会对数组进行扩容）

🌊ArrayList 源码中的扩容方式：

Object[] elementData; // 存放元素的空间
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 默认空间
private static final int DEFAULT_CAPACITY = 10; // 默认容量大小

public boolean add(E e) {
    确定一个真正的容量【把检查顺序表和判断满并扩容放在了一起】
    ensureCapacityInternal(size + 1); 
    elementData[size++] = e;
    return true;
} 

private void ensureCapacityInternal(int minCapacity){
    //计算出需要的容量
    int capacity = calculaterCapacity(elementData,minCapacity);
    //拿着计算出的容量进行判断（空的或者满了就进行扩容）
    ensureExplicitCapacity(capacity);
}

//计算是否分配容量
private static int calculateCapacity(Object[] elementData,int minCapacity){
    //判断 elementData 是否分配过大小
    if(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
        //如果没有分配容量，就返回 DEFAULT_CAPACITY（值为10）（DEFAULTCAPACITY_EMPTY_ELEMENTDATA 值为0）
        return Math.max(DEFAULT_CAPACITY, minCapacity);
        //return Math.max(10,minCapacity);
    }
    //分配过容量，就返回usedSize+1后的值
    return minCapacity;
}
 
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
} 

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
    // 获取旧空间大小
    int oldCapacity = elementData.length;

    // 预计按照1.5倍方式扩容
    int newCapacity = oldCapacity + (oldCapacity >> 1);

    // 如果用户需要扩容大小 超过 原空间1.5倍，按照用户所需大小扩容
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;

    // 如果需要扩容大小超过MAX_ARRAY_SIZE，重新计算容量大小
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        //说明所需要的容量非常大
        newCapacity = hugeCapacity(minCapacity);

    // 调用copyOf扩容
    elementData = Arrays.copyOf(elementData, newCapacity);
} 

private static int hugeCapacity(int minCapacity) {
    // 如果minCapacity小于0，抛出OutOfMemoryError（越界）异常
    if (minCapacity < 0)
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

?结论：

如果ArrayList 调用了不带参数的构造方法，那么顺序表的大小是0。
当第一个调用add()方法时，整个顺序表的大小变为10。
当放满10个元素后，会以1.5倍的方式进行扩容。
如果调用的是给定容量的构造方法，那么顺序表的大小就是给定的容量，放满后还是会以1.5倍的方式进行扩容。

ArrayList 的使用练习