ArrayList和顺序表(上)

1. ArrayList的介绍

在介绍ArrayList之前,我们需要认识一下线性表和顺序表

线性表: 是n个具有相同特性的数据元素的有限序列.常见的线性表:顺序表,链表,栈,队列...

线性表在逻辑上是线性结构,也就是一条连续的直线.但是在物理结构上不一定是连续的,线性表在物理上存储的时候,常常以数组和链式结构的形式存储.

顺序表: 物理地址连续的存储单元组成的线性结构,一般情况用数组来存储.在数组的基础上进行增删查改.总而言之,顺序表就是一个动态扩容的数组.

ArrayList的简介

在集合框架里面,ArrayList就是一个普通类,以下是它的具体架构图

1. ArrayList实现RandomAccess接口,说明ArrayList支持随机访问

2. ArrayList实现了Cloneable接口,说明ArrayList是可以clone的

3. ArrayList实现了Serializable接口,说明ArrayList是支持序列化的

4. ArrayList继承了AbstractList类,这个类又实现了List接口,因此我们可以使用List一系列的方法

5. ArrayList是泛型类,使用的时候要指定使用的引类型.

2. ArrayList的自我实现

为了更好的理解ArrayList,我们先不介绍它的方法,我们先模仿它的底层自己实现一下ArrayList.

2.1 Ilist的创建

我们模仿ArralList先写一个Ilist接口,里面写了这个接口的抽象方法,以便后续实现类来进行扩充.

以下是Ilist的具体代码

package ArrayList和顺序表.mylist;public interface Ilist {// 新增元素,默认在数组最后新增void add(int data);// 在 pos 位置新增元素void add(int pos, int data);// 判定是否包含某个元素boolean contains(int toFind);// 查找某个元素对应的位置int indexOf(int toFind);// 获取 pos 位置的元素int get(int pos);// 给 pos 位置的元素设为 valuevoid set(int pos, int value);//删除第一次出现的关键字keyvoid remove(int toRemove);// 获取顺序表长度int size();// 清空顺序表void clear();// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的void display();boolean isFull();//判断当前顺序表有没有满boolean isEmpty();//判断是不是空的}

2.2 MyArrayList的实现

我们开始写我们自己的ArrayList,取名为MyArrayList.,就像ArrayList一样,我们实现Ilist接口,然后重写里面的方法.

先介绍以下一些我们自己的变量设定:

elem是我们创建的数组,我们会在里面进行增删查改

usedSize是表示有效数据的大小(假设你里面存了4个连续数据,usedSize就为4)

DEFAULT_SIZE这是一个常量,如果用户没有设定MyArralList的大小,这个常量值就是我们elem数组的默认大小.

再介绍我们的构造方法,此处我们设定了俩个构造方法,一个有参数一个没参数,有参数的就是用户自己设定数组的大小,没有参数就是把DEFAULT_SIZE常量值设置为默认数组大小.

我们现在来介绍里面具体重写的方法

1> display()方法: 遍历,打印有效数据

我们就直接把数组进行遍历,注意我们这里的边界值是usedSize,我们遍历的是有效数据,而不是遍历全部的MyArrayList.

2> isFull()方法: 判断这个数组的实际长度和有效数据的长度是否相同,如果相同的话,用来作为后续扩容的判断条件.

3> checkCapacity()方法: 这个是用来判断是否需要扩容的方法,判断条件是isFull()方法的返回值,如果确实数据的有效长度和数组的实际长度一样,我们便会使用Arrays.copyOf()方法,对数组进行拷贝,然后长度设为原先的2倍,也就是二倍扩容.(这个方法不是重写的,是我们MyArrayList自己写的)

4> add(int data)方法我们在usedSize位置上放置我们新增的数据,在放置的时候,我们需要通过checkCapacity()来对数组容量进行判断,如果是满的就2倍扩容.

5> add(int pos,int data)方法,我们在指定的pos位置上放置数据.这个地方要注意俩个地方,其一:我,们要判断放置的位置的合法性.其二:我们要判断数组的大小是否支持扩容.

其中我们判断pos的位置,需要写一个checkPoseAdd(pos)方法

如果pos<0或者pos>usedSize(为什么不取=,是因为add里面的usedSize有扩容机制,不会发生在usedSize下标超出数组界限的情况),如果满足这个情况,我们就抛出一个异常,这个异常是我们自己写的异常,PosIllegality.

当这些判断都结束,并且没问题,我们就要进行数据的搬运了,因为我们是在指定位置上对数据进行添加,我们就不能单纯的在那个位置上把数据的值赋值过来,这样会覆盖原先数据的值,我们应该把在这个位置上的数据到最后一个数据往后移动一个位置,进行一个整体的搬运才行.

6> contains(int toFind)方法:判断某个元素是不是在这个数组里面,我们需要先判断,我们的数组是不是为空,也就要使用到isEmpyty()方法,如果usedSize == 0那就说明为空.然后我们再遍历整个数组看里面是不是有这个元素,如果有就返回turn.

注意: 如果是查找引用数据类型,一定呀记住重写equals方法

7> indexOf(int toFind)方法:这个就是返回查找元素的下标,也是先要进行判断,看这个数组是不是空的,再遍历数组,如果找到就返回这个元素的下标.

8> get(int pos)方法:获取pos位置下的数据值,这里需要判断我们寻找的下标是不是合法的,并且判断这个数组是不是空的,

判断是否下标合法

这个地方很有意思,因为它和刚刚add里面的判断位置有些不同,就是它甚至把usedSize这个位置也设置成非法位置,这个原因是我们的get方法并没有实现扩容,所以usedSize有可能就会引起下标越界(假设数组长度为5,usedSize也为5,此时我们没有扩容机制,因此,我们如果使用这个下标,就会引起越界)

判断数组是不是空

这个里面,如果get到的数组其实是空的,我们就要抛出自己写的异常MyArrayListEmpty,提示一下数组是空的.

如果上述条件都通过,我们就会直接返回该下标的值

9> set(int pos,int value)方法:我们设置pos下标的值为value.此处我们需要判断pos位置的合法性,若合法就直接把value值覆盖pos下标的值即可

10> remove(int toRemove)方法: 删除这个数据.我们先要判断并找到这个数据的位置,因此要用到indexOf方法,然后我们需要把该位置后面的数据全部整体前移一个位置,把该数据覆盖

这里我们设置i的边界是<usedSize-1,而不是<usedSize是因为如果usedSize刚刚好是最后一个元素,后续我们i+1位置就会越界.

10> size()方法:我们直接返回usedSize大小即可

11> clear()方法:因为我们现在是操纵的引用数据类型,因此我们直接把usedSize设置为0即可.

注意:如果是引用数据类型,我们只是设置为0是不行的,这个会导致内存泄露,JVM只有当对象没有引用的时候才会自动帮我们回收内存,因此我们需要把每一个引用设为null.

2.3 测试

我们写一个Test类来对我们自己的MyArrayList进行创建,并且使用里面的方法

结果:

2.4 整体代码展现

package ArrayList和顺序表.mylist;import java.util.Arrays;public class MyArrayList implements Ilist{//实现Ilist接口,重写所有的方法public int[] elem;public int usedSize;//放一个元素useSize++,usedSize表示有效数据的大小//顺序表的默认大小public static final int DEFAULT_SIZE = 10;//相当于常量public MyArrayList() {this.elem = new int[DEFAULT_SIZE];}//指定大小public MyArrayList(int capacity) {this.elem = new int[capacity];}//遍历,打印有效数据@Overridepublic void display() {//遍历有效数据for (int i = 0; i < this.usedSize; i++) {System.out.print(this.elem[i] + " ");}System.out.println();}@Overridepublic boolean isFull() {return this.usedSize == this.elem.length;}// 新增元素,默认在数组最后新增@Overridepublic void add(int data) {//如果满了不能放
//        if(isFull()) {
//            //扩容
//           this.elem = Arrays.copyOf(this.elem,this.elem.length*2);//二倍扩容,拷贝数组
//        }我们直接写成一个方法,实现复用//往数组放东西checkCapacity();this.elem[usedSize] = data;usedSize++;}//判断是否需要扩容private void checkCapacity() {if(isFull()) {//扩容this.elem = Arrays.copyOf(this.elem,this.elem.length*2);//二倍扩容,拷贝数组}}// 在 pos 位置新增元素@Overridepublic void add(int pos, int data) {
//        //先检查容量
//        checkCapacity();
//        if (pos < 0 || pos > usedSize) {//
//            System.out.println("不合法!");//自己试一下用异常来搞一下
//            return;
//        }检查pose位置,我们也可以封装复用一下//先需要判断pos的位置try {checkPoseAdd(pos);}catch (PosIllegality e) {e.printStackTrace();return;//因为已经捕获了所以我们后续代码还可以进行,因此需要return直接返回,结束程序}//再看是否需要扩容checkCapacity();//我们移到的地方,如果有元素,我们就要往后移动一下//1.从最后一个有效数据开始往后移动for (int i = usedSize; i >= pos ; i--) {elem[i + 1] = elem[i];}//2.当i < pos 就结束//3.存放元素到pos位置elem[pos] = data;//4.usedSize++usedSize++;}private void checkPoseAdd(int pos) throws PosIllegality{//告诉别人调用这个方法会抛出异常if (pos < 0 || pos > usedSize) {////抛个异常,而不是单纯打印日志throw new PosIllegality("插入元素下标异常: " + pos);}}//判断某个元素是不是在这里面@Overridepublic boolean contains(int toFind) {//先判断是否为空if (isEmpty()) {//如果不判断的话,要是为空,我们还进行下标的访问,就会空指针异常return false;}//不是空的,就遍历数组,看里面是不是有这个元素for (int i = 0; i < usedSize; i++) {//如果是查找引用数据类型,一定记住要重写方法 equalsif(elem[i] == toFind) {return true;//在进行比较的时候,要想清楚,想比较的是地址还是内容}}return false;}public boolean isEmpty() {return usedSize == 0;}
//返回指定位置的下标@Overridepublic int indexOf(int toFind) {//先判断是否为空if (isEmpty()) {return -1;}//不是空的,就遍历数组,看里面是不是有这个元素for (int i = 0; i < usedSize; i++) {//如果是查找引用数据类型,一定记住要重写方法 equalsif(elem[i] == toFind) {return i;//在进行比较的时候,要想清楚,想比较的是地址还是内容}}return -1;}//获取pos 的值@Overridepublic int get(int pos) throws MyArrayListEmpty{//调用这个方法就要抛出异常//看是否在合法下标内获取到checkPoseGetAndSet(pos);//判断这个数组是否是空的if(isEmpty()) {throw new MyArrayListEmpty("获取指定下标元素的时候顺序表为空!");}return elem[pos];}private void checkPoseGetAndSet(int pos) throws PosIllegality{//告诉别人调用这个方法会抛出异常if (pos < 0 || pos >= usedSize) {//add是可以在usedSize位置上添加元素的,相当于在尾巴上面加元素,而get和set,在used//抛个异常,而不是单纯打印日志throw new PosIllegality("获取指定元素下标异常: " + pos);}}//给pos位置修改value@Overridepublic void set(int pos, int value) {checkPoseGetAndSet(pos);elem[pos] = value;}@Overridepublic void remove(int toRemove) {//1.先找到要删除的数据的位置int index = indexOf(toRemove);if(index == -1) {throw new RuntimeException("没有这个元素");//自己创建一个异常}//2.找到之和就把后面一个覆盖前面一个for (int i = index; i < usedSize - 1 ; i++) {//i一定是usedSize-1,因为usedSize在覆盖过程中并没有改变它的大小,所以当搞到最后一个的时候i+1会越界elem[i] = elem[i+1];}//3.usedSize--usedSize--;}@Overridepublic int size() {return this.usedSize;}@Overridepublic void clear() {//如果是基本数据类型this.usedSize = 0;//而如果是引用数据类型,只和上面这么搞,会导致内存泄露//JVM回收算法//1.当前对象没有人引用的时候//elem = null/for(){elem[i] = null;}}}