【Java集合】ArrayList

关于泛型的小小了解 泛型的分类

泛型类

泛型方法

泛型类的定义的简单演示

关于泛型类的定义，这里只是了解即可，我们重点学习泛型类的使用。

// 1. 尖括号 <> 是泛型的标志 
// 2. E 是类型变量(Type Variable)，变量名一般要大写 
// 3. E 在定义时是形参，代表的意思是 MyArrayList 最终传入的类型，但现在还不知道 
public class MyArrayList { 
    private E[] array; 
    private int size; 
    ... 
}

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

泛型类的使用

// 定义了一个元素是 Book 引用的
MyArrayList MyArrayList books = new MyArrayList(); 
books.add(new Book()); 

// 会产生编译错误，Person 类型无法转换为 Book 类型 
books.add(new Person()); 

// 不需要做类型转换 
Book book = book.get(0); 

// 不需要做类型转换 
// 会产生编译错误，Book 类型无法转换为 Person 类型 
Person person = book.get(0);

通过以上代码，我们可以看到泛型类的一个使用方式：只需要在所有类型后边跟尖括号，并且尖括号内是真正的类型，即 E 可以看作的最后的类型。

注意： Book 只能想象成 E 的类型，但实际上 E 的类型还是 Object

泛型总结

泛型是为了解决某些容器、算法等代码的通用性而引入，并且能在编译期间做类型检查。

泛型利用的是 Object 是所有类的祖先类，并且父类的引用可以指向子类对象的特定而工作。

泛型是一种编译期间的机制，即 MyArrayList 和 MyArrayList 在运行期间是一个类型。

泛型是 java 中的一种合法语法，标志就是尖括号 <>

包装类的认识

Object引用可以指向任意类型的对象，但有例外出现了，8 种基本数据类型不是对象，那岂不是刚才的泛型机制要失效了？

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

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

基本数据类型	包装类
byte	Byte
short	Short
int	Integer
long	Long
float	Float
double	Double
char	Character
boolean	Boolean

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

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

int i = 10; 

// 装箱操作，新建一个 Integer 类型对象，将 i 的值放入对象的某个属性中 
Integer ii = Integer.valueOf(i); 
Integer ij = new Integer(i);

// 拆箱操作，将 Integer 对象中的值取出，放到一个基本数据类型中 
int j = ii.intValue();

自动装箱(autoboxing)和自动拆箱(autounboxing)

可以看到在使用过程中，装箱和拆箱带来不少的代码量，所以为了减少开发者的负担，java 提供了自动机制。

int i = 10; 

Integer ii = i; // 自动装箱 
Integer ij = (Integer)i; // 自动装箱 

int j = ii; // 自动拆箱 
int k = (int)ii; // 自动拆箱

**注意：**自动装箱和自动拆箱是工作在编译期间的一种机制。

List的常用方法

方法	解释
boolean add(E e)	尾插e
void add(int index, E element)	将e插入到index位置
boolean addAll(Collection c)	尾插c中元素
E remove(int index)	删除index位置元素
boolean remove(Object o)	删除遇到的第一个o
E get(int index)	获取下标index位置元素
E set(int index, E element)	将下标index位置元素设置为element
void clear()	清空
boolean contains(Object o)	判断o是否在线性表中
int indexOf(Object o)	返回第一个o所在下标
int lastIndexOf(Object o)	返回后最后一个o的下标
List subList(int fromIndex, int toIndex)	截取部分list

ArrayList简介

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xkygsJMO-1642841178781)(C:/Users/78581/AppData/Roaming/Typora/typora-user-images/image-20220119233038765.png)]

【说明】

ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问

ArrayList实现了Cloneable接口，表明ArrayList是可以clone的

ArrayList实现了Serializable接口，表明ArrayList是支持序列化的

和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者CopyOnWriteArrayList

ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

ArrayList使用 ArrayList 的构造

方法	解释
ArrayList()	无参构造
ArrayList(Collection c)	利用其他 Collection 构建 ArrayList
ArrayList(int initialCapacity)	指定顺序表初始容量

public static void main(String[] args) { 
    // ArrayList创建，推荐写法 
    // 构造一个空的列表 
    List list1 = new ArrayList<>(); 
    
    // 构造一个具有10个容量的列表 
    Listlist2 = new ArrayList<>(10); 
    list2.add(1); list2.add(2); 
    list2.add(3); /
        / list2.add("hello"); // 编译失败，List已经限定了，list2中只能存储整形元素 
    // list3构造好之后，与list中的元素一致 
    ArrayList list3 = new ArrayList<>(list2); 
    
    // 避免省略类型，否则：任意类型的元素都可以存放，使用时将是一场灾难 
    List list4 = new ArrayList(); 
    list4.add("111"); 
    list4.add(100); 
}

ArrayList 的常见操作

ArrayList虽然提供的方法比较多，但是常用方法如下所示，需要用到其他方法时，自行查看ArrayList的帮助文档。

方法	解释
boolean add(E e)	尾插 e
void add(int index, E element)	将 e 插入到 index 位置
boolean addAll(Collection c)	尾插 c 中的元素
E remove(int index)	删除 index 位置元素
boolean remove(Object o)	删除遇到的第一个 o
E get(int index)	获取下标 index 位置元素
E set(int index, E element)	将下标 index 位置元素设置为 element
void clear()	清空
boolean contains(Object o)	判断 o 是否在线性表中
int indexOf(Object o)	返回第一个 o 所在下标
int lastIndexOf(Object o)	返回最后一个 o 的下标
List subList(int fromIndex, int toIndex)	截取部分 list

public static void main(String[] args) { 
   List list = new ArrayList<>(); 
   list.add("JavaSE"); 
   list.add("JavaWeb"); 
   list.add("JavaEE"); 
   list.add("JVM"); 
   list.add("测试"); 
   System.out.println(list); 
   
   // 获取list中有效元素个数 
   System.out.println(list.size()); 
   
   // 获取和设置index位置上的元素，注意index必须介于[0, size)间 	
   System.out.println(list.get(1)); 
   list.set(1, "JavaWEB"); System.out.println(list.get(1)); 
   // 在list的index位置插入指定元素，index及后续的元素统一往后搬移一个位置 
   list.add(1, "Java数据结构"); 
   System.out.println(list); 
   // 删除指定元素，找到了就删除，该元素之后的元素统一往前搬移一个位置 
   list.remove("JVM"); 
   System.out.println(list); 
   // 删除list中index位置上的元素，注意index不要超过list中有效元素个数,否则会抛出下标越界异常 
   list.remove(list.size()-1); 
   System.out.println(list); 
   
  	// 检测list中是否包含指定元素，包含返回true，否则返回false
   if(list.contains("测试")){ 
       list.add("测试"); 
   }
   
   // 查找指定元素第一次出现的位置：indexOf从前往后找，lastIndexOf从后往前找 
   list.add("JavaSE"); 
   System.out.println(list.indexOf("JavaSE")); 
   System.out.println(list.lastIndexOf("JavaSE")); 
   
   // 使用list中[0, 4)之间的元素构成一个新的ArrayList返回 
   List ret = list.subList(0, 4); 
   System.out.println(ret); 
   list.clear(); 
   System.out.println(list.size()); 
}

ArrayList 的遍历

ArrayList 可以使用三方方式遍历：for循环+下标、foreach、使用迭代器

public static void main(String[] args) { 
    List list = new ArrayList<>(); 
    list.add(1); 
    list.add(2); 
    list.add(3); 
    list.add(4); 
    list.add(5); 
    // 使用下标+for遍历 
    for (int i = 0; i < list.size(); i++) { 
        System.out.print(list.get(i) + " "); 
    }
    System.out.println(); 
    // 借助foreach遍历 
    for (Integer integer : list) { 
        System.out.print(integer + " "); 
    }
    System.out.println(); 
    //使用迭代器遍历
    Iterator it = list.listIterator(); 
    while(it.hasNext()){ 
        System.out.print(it.next() + " "); 
    }
    System.out.println(); 
}

ArrayList的扩容机制

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

ArrayList是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容：以下是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); // Increments modCount!! 
    elementData[size++] = e; 
    return true; 
}

private void ensureCapacityInternal(int minCapacity) { 									ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); 
}

private static int calculateCapacity(Object[] elementData, int minCapacity) { 
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
        return Math.max(DEFAULT_CAPACITY, minCapacity); 
    }
    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; 
}

【总结】 1. 检测是否真正需要扩容，如果是调用grow准备扩容
2. 预估需要库容的大小
初步预估按照1.5倍大小扩容
如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容
真正扩容之前检测是否能扩容成功，防止太大导致扩容失败
3. 使用copyOf进行扩容