Java ArrayList顺序表 + 接口实现 + 底层

顺序表

1. 顺序表是动态扩容的一个数组
2. 顺序表物理地址和逻辑地址都是连续的

接口的实现

package myList;import java.util.Arrays;public class MyArrayList implements IList{// 动态扩容的一个数组public int[] arr;public static final int numsize = 2;int usesize;// 统计数组中有多少个有效元素// 静态大小的数组public MyArrayList(){this.arr = new int[numsize];}// 动态的大小的数组public MyArrayList(int capacity){this.arr = new int[capacity];}/*遍历顺序表*/public void display() {for(int i = 0;i < this.usesize;i++){System.out.print(this.arr[i]+" ");}System.out.println();}@Overridepublic boolean isFull() {if(this.numsize == this.usesize) return true;return false;}// 在数组的最后尾插一个元素@Overridepublic void add(int data) {checkCapacity();this.arr[this.usesize] = data;this.usesize++;}// 在指定位置(pos位置)新增元素@Overridepublic void add(int pos, int data) {try{checkPos(pos);}catch(PosIllegality e){e.printStackTrace();// 处理异常return;}checkCapacity();for(int i = usesize - 1;i >= pos;i--){arr[i+1] = arr[i];}this.arr[pos] = data;this.usesize++;}// 检查下标的合法性private void checkPos(int pos) throws PosIllegality{if(pos < 0 || pos > usesize){System.out.println("下标不合法");// 抛异常throw new PosIllegality("下标不合法异常");}}// 检查容量够不够函数private void checkCapacity(){if(isFull()){// 扩容arr = Arrays.copyOf(arr,arr.length*2);}}// 判定是否包含某个元素@Overridepublic boolean contains(int toFind) {if(isEmpty()) return false;for(int i = 0;i < usesize;i++){// 如果是查找引用数据类型,一定要重写 比较方法if(toFind == arr[i]) return true;}return false;}public boolean isEmpty(){if(usesize == 0) return true;else return false;}// 查找某个元素对应的位置@Overridepublic int indexOf(int toFind) {if(isEmpty()) return -1;for(int i = 0;i < usesize;i++){// 如果是查找引用数据类型,一定要重写 比较方法if(toFind == arr[i]) return i;}return -1;}@Overridepublic int get(int pos) throws MyArrayEmpty {checkPosOnGet(pos);if(isEmpty()){// 抛异常throw new MyArrayEmpty("获取指定下标元素时,顺序表为空");}return arr[pos];}private void checkPosOnGet(int pos) throws PosIllegality{if(pos < 0 || pos >= usesize){System.out.println("下标不合法");// 抛异常throw new PosIllegality("下标不合法异常");}}private void checkPosOnSet(int pos) throws PosIllegality{if(pos < 0 || pos >= usesize){System.out.println("下标不合法");// 抛异常throw new PosIllegality("下标不合法异常");}}@Overridepublic void set(int pos, int value) {checkPosOnSet(pos);arr[pos] = value;}// 删除第一次出现的元素@Overridepublic void remove(int toRemove) {int k = indexOf(toRemove);if(k == -1){System.out.println("没有找到这个数");return;}for(int i = k;i < this.usesize - 1;i++){arr[i] = arr[i+1];}this.usesize--;}@Overridepublic int size() {return this.usesize;}// 清空顺序表@Overridepublic void clear() {this.usesize = 0;}
}// MyArrayEmpty的异常的写法
package myList;public class MyArrayEmpty extends RuntimeException {public MyArrayEmpty(String msg){super(msg);}
}// PosIllegality异常的写法
package myList;public class PosIllegality extends RuntimeException{public PosIllegality(String msg){super(msg);}
}

clear

1. clear清空数组，如果类型是基本数据类型，可以把有效的长度置为0，如果为引用数据类型该怎么办呢？
   垃圾回收的机制：当这个对象没有被引用的时候可以被回收
   引用类型可以用for循环一个一个置空，然后有效元素个数置为0
   

ArrayList的使用

import java.util.ArrayList;public class test {public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(0,99);for(int i = 0;i < list.size();i++){System.out.print(list.get(i) + " ");}System.out.println();System.out.println(list);}
}

构造方法

1. 带一个参数的构造方法（传入要扩容的空间大小）
2. 不带参数的构造方法（在add的时候扩容10个空间大小）

3. 扩容：第一次add会分配大小为10的内存
对于ArrayList来说是1.5倍扩容，如果超过1.5倍大小，则按照用户所需大小进行扩容
使用copyOf进行扩容

底层：

4. 用另一个对象构造新的对象，Collection是接口

1.ArrayList实现了Collection接口，那么Collection接口可以引用ArrayList的对象
2.list泛型类的类型是？（通配符），它的上界要是list2的子类或者其本身，list传给c
3. 只要实现了这个接口都可以传递给Collection

使用：

ArrayList<Integer> list = new ArrayList<>();
ArrayList<Number> list1 = new ArrayList<>(list);
// list必须是Number的子类或者是它本身(Integer)

函数使用

        // 1. addAllArrayList<Number> list12 = new ArrayList<>();// list12.addAll(list);// 将list对象中的内容都复制入list12对象中System.out.println(list12);// 2. remove// 删除下标2对应的内容list12.remove(2);// 删除3这个对象list12.remove(new Integer(3));// 3. get和setSystem.out.println(list12.get(1));list12.set(1,2);// 4. clear// list12.clear();// 5. boolean contains(Object o) 判断o是否在线性表中// 6. int indexOf(Object o) 返回出现o所在的第一个下标// 7. int lastIndexOf(Object o) 返回最后一个o的下标  */ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);System.out.println(list);// subList不会创建新的对象，只是让list1指向原对象的1下标位置List<Integer> list1 = list.subList(1,3);System.out.println(list1);// 2 3list1.set(0,99);System.out.println(list1);// 99 3System.out.println(list);// 1 99 3 4 5

遍历

System.out.println(list);for(Integer x : list){System.out.print(x);}System.out.println();// 迭代器Iterator<Integer> it = list.iterator();while(it.hasNext()){System.out.print(it.next() + " ");// it.next()自动向下执行}System.out.println();

应用

杨辉三角

class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> list = new ArrayList<>();List<Integer> list1 = new ArrayList<>();list1.add(1);list.add(list1);for(int i = 1;i < numRows;i++){// 1.先插入第一个数字1List<Integer> rowList = new ArrayList<>();rowList.add(1);// 拿到前一行的数组List<Integer> prevList = list.get(i-1);// 2.再插入中间数据for(int j = 1;j < i;j++){int val = prevList.get(j) + prevList.get(j-1);rowList.add(val);}// 3. 插入最后一个数字1rowList.add(1);// 4. 在插入到二维数组中list.add(rowList);} return list;}
}