【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)。
💦泛型总结
- 泛型是为了解决某些容器、算法等代码的通用性而引入,并且能在编译期间做类型检查。
- 泛型利用的是 Object 是所有类的祖先类,并且父类的引用可以指向子类对象的特定而工作。
- 泛型是一种编译期间的机制,即 MyArrayList 和 MyArrayList 在运行期间是一个类型。
- 泛型是 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 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 的打印
- 直接打印(底层调用 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 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 的使用练习