Java学习笔记 06 动态数组与链表

00 学习目标通过手动编写动态数组相关的核心代码理解动态数组的原理为学习各种集合框架知识打下基础集合框架 线性表数组 链表 队列 栈 集合数组 链表 Map:K-V(键值对)01 泛型泛型 是一种类型模板符号在定义类的时候在类名的右边写一个 括号中使用一个字母或单词代表一种未知的类型在这个类中就可以使用这个字母(泛型名) 替代 所有 需要使用类型声明的地方(参数类型 返回值类型 转型类型)泛型名不能实例化对象new即不能作为数据类型创建对象Java的泛型是编译期特性。为了兼容旧版本Java采用类型擦除来实现泛型。这意味着编译时编译器会检查泛型类型是否正确。运行时所有泛型信息如E都被“擦除”了E会被替换成它的上界Object。因此当写下E时编译器看到的E在运行时已经变成了Object。如果能编译通过E实际上会变成Object这完全违背了创建特定类型对象的初衷。JVM在运行时根本不知道E具体是什么类也就无法去调用正确的构造函数来创建对象。当这个类在创建对象的时候可以在类名的右边使用指定一个具体的类型使用对象调用方法时这个方法中参数类型 返回值类型 都会替换为具体的类型如果创建对象时 没有指定一个具体的类型那么所有的地方都会默认为Object类型Object 类 是Java所有类的父类任何类型的对象都可以存到Object类中。默认隐式直接继承了Object。但存储任意类型的数据会导致混乱因此不使用02 动态数组的属性与方法01 属性打开ArrayList类我们可以找到它的核心属性默认容量 private static final int DEFAULT_CAPACITY 10;存储元素的数组 transient Object[] elementData; //前缀需改为private大小 private int size;02 初始化初始化按照类里的自己写public LArrayList(int initialCapacity) { //输入初始容量 if (initialCapacity 0) { elementData new Object[initialCapacity]; //用初始容量初始化 } else if (initialCapacity 0) { elementData new Object[DEFAULT_CAPACITY]; //用默认容量初始化 } else { // throw new IllegalArgumentException(Illegal Capacity: 显示容量不合法 // initialCapacity); System.out.println(输入的容量不合法); } }也可以更简单public LArrayList(int initCapacity){ if(initCapacity10){ initCapacityDEFAULT_CAPACITY; //初始化容量小于10则改为10 } elementData new Object[initCapacity]; //否则用初始化容量 }03 功能方法.基础//显示大小 public int size(){ return size; } //显示是否为空 public boolean isEmpty(){ return size0; } // 打印数组 public void printArr(){ System.out.print(数组元素为【); for(int i0;isize;i){ System.out.print(elementData[i] ); } System.out.println(】); }04 增删查改比较排序00 文档注释/** */01 末尾添加elementData.size经常使用可以把它写成属性 private int length;// 方便调用public void add(E e){ if(sizelength){ // 需要扩容 int oldLength length; //1效果上相当于除以 2 后向负无穷取整floor(n / 2 int newLength oldLength(oldLength1);// 1.5倍扩容 // 创建一个更大的数组 Object[] newElementData new Object[newLength]; // 将原数组的数据存入新数组中 for(int i 0; ioldLength;i){ newElementData[i]elementData[i]; } // 替换原数组名存储的数组地址为新数组的地址 elementData newElementData; //注意Java不用指针可以用数组名赋值数组 lengthnewLength; System.out.println(扩容完成~ len:length); System.gc();// 让系统主动调用 垃圾回收系统回收原来的数组占用的空间 } elementData[size]e; }Java中对象创建后会一直存在直到不引用它这就是为什么可以用for内创建的数组名赋值02 批量添加通过数组批量添加元素。要注意需要修改扩容算法防止扩容后依然装不下所有数字。可以写一个扩容方法方便重复调用/** * 扩容 * param minCapacity 最小需要的容量 */ public void grow(int minCapacity){ int oldLen length; int newLen oldLen(oldLen1); if(minCapacitynewLen-size){ //一般的1.5倍扩容 Object[] newElementData new Object[newLen]; for (int i 0; i size; i) { newElementData[i]elementData[i]; } elementDatanewElementData; lengthnewLen; }else if(minCapacitynewLen-size){ //1.5倍扩容不足 Object[] newElementData new Object[minCapacitysize];// 一次性扩容 for (int i 0; i size; i) { newElementData[i]elementData[i]; } elementDatanewElementData; lengthminCapacitysize; } System.out.println(扩容完成~ len:length); }public void addAll(E[] es){ //添加整个数组的数据 // 计算扩容 1 es的长度小于等于数组空闲空间 // 2 es长度小于1.5倍扩容之后的空余空间 // 3: es长度大于1.5倍扩容之后的空余空间 // 一次性扩容到位 int eslen es.length; //所需容量 int capacity length-size; //空余容量 if(eslencapacity){ grow(eslen); } for(int i0;ies.length;i){ elementData[size]es[i]; } }要记住数组的数据类型也要是封装类03 按下标插入元素public void insert(int index,E e){ if(sizelength){ grow(1); //扩容 } for (int i size-1; i index; i--) { //用size-1防止溢出 从末尾数据开始 elementData[i1]elementData[i]; //后一个的数据变为前一个 } elementData[index]e; size; }03 排序ArrayList的排序方法可以进行按条件排序数组名.sort((需要排序的参数名,需要排序的参数名)- 一个int值。若大于0则互换位置);普通数组也可以用原理类似冒泡排序两个参数名自动检测为前后的数值完整版list1.sort(new ComparatorUser() { Override public int compare(User o1, User o2) { return o1.age-o2.age; } });