> 文档中心 > 【Java---数据结构】ArrayList

【Java---数据结构】ArrayList


目录

一、初识泛型

💦泛型的引入

💦泛型的定义

💦泛型类的使用

💦泛型总结

二、包装类(Wrapper Class)

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

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

三、ArrayList与顺序表

💦ArrayList简介

💦ArrayList使用

💦迭代器 Iterator 与 ListIterator

💦ArrayList常见操作

💦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{    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 {    private E[] array;    private int usedSize;    ...}
  • 泛型是作用在编译期间的一种机制,即运行期间没有泛型的概念。
  • 泛型代码在运行期间,就是上面提到的,利用 Object 达到的效果。

💦泛型类的使用

(1)在编译期间自动对类型进行检查

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

(2)自动对类型进行强制类型转换

public class TestDemo2 {    public static void main(String[] args) { MyArrayList 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 MyArrayList myArrayList1 = new MyArrayList(); MyArrayList myArrayList2 = new MyArrayList(); //打印内容:类型@地址值 System.out.println(myArrayList1); System.out.println(myArrayList2);    }}//运行结果:MyArrayList@4554617cMyArrayList@74a14482
  • 打印的内容:类型 @ 地址值,类型中并没有尖括号里面内容。

面试问题:泛型是怎么编译的?

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

💦泛型总结

  1. 泛型是为了解决某些容器、算法等代码的通用性而引入,并且能在编译期间做类型检查。
  2. 泛型利用的是 Object 是所有类的祖先类,并且父类的引用可以指向子类对象的特定而工作。
  3. 泛型是一种编译期间的机制,即 MyArrayList 和 MyArrayList 在运行期间是一个类型。
  4. 泛型是 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接口,具体框架图如下:

说明:

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

💦ArrayList使用

⭐ArrayList 的构造

🌊代码示例:

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

ArrayList 的打印

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

🌊代码示例:

import java.util.ArrayList;import java.util.Iterator;import java.util.ListIterator;public class TestDemo2 {    public static void main(String[] args) { ArrayList 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 it1 =  list1.iterator();while (it1.hasNext()){    System.out.print(it1.next()+" ");} System.out.println(); System.out.println("==============");//使用迭代器List相关打印 ListIterator 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 list1 = new ArrayList(); list1.add("hello"); list1.add("JAVA"); list1.add("ABCD"); Iterator 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 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 list1 = new ArrayList(); list1.add("hello"); list1.add("JAVA"); list1.add("ABCD"); ListIterator 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 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 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 c) 方法的使用(尾插 c 中的元素)

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

🌊代码示例:

import java.util.ArrayList;public class TestDemo2 {    public static void main(String[] args) { ArrayList list1 = new ArrayList(); list1.add("JavaSE"); list1.add("JavaWeb"); list1.add("JavaEE"); list1.add("JVM"); System.out.println(list1); System.out.println("=============="); ArrayList 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 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 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 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 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 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 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 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 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 list1 = new ArrayList(); list1.add("JavaSE"); list1.add("JavaWeb"); list1.add("JavaEE"); list1.add("JVM"); list1.add("hello"); List 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 list1 = new ArrayList(); list1.add("JavaSE"); list1.add("JavaWeb"); list1.add("JavaEE"); list1.add("JVM"); list1.add("hello"); List 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 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 = hugeCapacity(minCapacity);    // 调用copyOf扩容    elementData = Arrays.copyOf(elementData, newCapacity);} private static int hugeCapacity(int minCapacity) {    // 如果minCapacity小于0,抛出OutOfMemoryError(越界)异常    if (minCapacity  MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;}

✨结论:

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

ArrayList 的使用练习