文章目录

• ArrayList简介
• ArrayList模拟实现
• • 打印顺序表
  • 获取顺序表的长度
  • 判断当前的顺序表是不是满的
  • 判断当前顺序表是不是空的
  • 数组扩容
  • 新增元素,默认在数组最后新增
  • 在指定pos位置新增元素
  • 判定是否包含某个元素
  • 查找某个元素对应的位置
  • 获取指定pos位置的元素
  • 将指定pos位置的元素替换成value
  • 删除第一次出现的关键字key
  • 清空顺序表
• 完整代码

ArrayList简介

ArrayList 类是一个可以动态修改的数组，与普通数组的区别就是它是没有固定大小的限制，我们可以添加或删除元素。ArrayList 继承了 AbstractList ，并实现了 List 接口。

简单来说ArrayList的底层就是一个动态的顺序表。
而顺序表的底层就是数组.
因此要模式实现ArrayList就相当于基于数组实现一些操作，例如增删查改等。

ArrayList模拟实现

	public int[] elem;public int usedSize;//记录有效数据的个数//默认容量private static final int DEFAULT_SIZE = 10;public MyArraylist() {this.elem = new int[DEFAULT_SIZE];}

将数据放在elem这个数组中，usedSize用于计算有效数据的个数，DEFAULT_SIZE是elem的默认容量。

打印顺序表

打印顺序表，我们可以使用循环对顺序表中的数据进行打印。

    /*** 打印顺序表:* 根据usedSize判断即可*/public void display() {for (int i = 0; i < this.usedSize; i++) {System.out.print(this.elem[i] + " ");}System.out.println();}

注意：顺序表中elem的有效数据是从[0,usedSize)，不能直接将整个数组打印完，我们存放的数据不一定能将数组放满。

获取顺序表的长度

此处的顺序表长度并不是底层数组的长度,而是数组种有效数据的个数.因此我们直接返回usedSize即可

	public int size() {return this.usedSize;}

判断当前的顺序表是不是满的

要想判断当前的顺序表是不是满的,只需要看看usedSize(有效数据的个数)是不是大于等与底层数组的长度 如果是满的,返回true.如果不是满的,就返回false

    /*** 判断当前的顺序表是不是满的！*/public boolean isFull() {if (size() >= this.elem.length) {return true;}return false;// 更简单的写法// return size() >= this.elem.length;}

判断当前顺序表是不是空的

判断当前顺序表是不是空的,只要看顺序表的有效数据是不是等于0即可

    //判断顺序表是否为空private boolean isEmpty() {return size()==0;}

数组扩容

在实现增加元素之前,我们要考虑一下,当数组满了之后,应该怎么做.顺序表不是链表,不用考虑满不满的这种情况,但顺序表不一样,数组长度是我们事先定好的.
如果数组长度设置的过大,而数据量很少,势必会造成空间的浪费.设置的过小,可能无法把所有元素存放进去.
为了避免这种情况,我们就可以使用动态顺序表.虽然听上去很高大上,但其实也就是加了一个动态扩容的过程

扩容也并不复杂,使用Arrays.copyOf方法即可

数组名 = Arrays.copyOf(要拷贝的数组,拷贝数组的长度);

在拷贝时,如果要拷贝数组的长度超过了原数组,那么超过原数组的部分,就是数组类型的默认值

新增元素,默认在数组最后新增

在解决数组满了这种情况之后,新增元素就很简单了.
一共分为两步:首先先判断数组是否满了,数组满了,就进行扩容.然后进行新增元素.如果没满,直接增加元素即可

    /** 新增元素,默认在数组最后新增* 判断顺序表是否满了* 满了->扩容* @param data*/public void add(int data) {if (isFull()) {//扩容this.elem = Arrays.copyOf(this.elem,2*this.elem.length);}this.elem[usedSize] = data;usedSize++;}

在指定pos位置新增元素

在指定位置新增元素,首先要判断数组是否满了,如果满了要进行扩容.其次,pos位置是否合法,合法位置才能新增元素.
因为是从指定位置新增元素,如果这个位置不是在最后面,那么在新增元素时,首先要把pos及其以后位置的元素都往后移动一位,将pos位置空出来,这样才能将元素放进去

    public void add(int pos, int data) {if(isFull()){this.elem = Arrays.copyOf(this.elem,2*this.elem.length);}if(checkPos(pos)){for (int i = usedSize; i >= pos; i--) {this.elem[i] = this.elem[i-1];}this.elem[pos] = data;}this.usedSize++;}// 检查pos位置是否合法private boolean checkPos(int pos) {if (pos < 0 || pos > size()) {System.out.println("pos位置不合法");return false;}return true;//合法}

判定是否包含某个元素

直接对数组进行遍历然后比较即可,如果相等,直接返回true 如果遍历完没有与它相等的,就返回false

    // 判定是否包含某个元素public boolean contains(int toFind) {for (int i = 0; i < this.usedSize; i++) {if (toFind == this.elem[i]) {return true;}}return false;}

查找某个元素对应的位置

与上面判断是否包含某个元素相同,遍历就行.
如果相等,返回当前的i值,如果不相等,就继续遍历.如果遍历完还没找到,就返回-1

    // 查找某个元素对应的位置public int indexOf(int toFind) {for (int i = 0; i < this.usedSize; i++) {if (toFind == this.elem[i]) {return i;}}return -1;}

获取指定pos位置的元素

先检查顺序表是否为空,如果是空的.直接返回-1.如果不为空,再检查pos位置是否合法.
用自定义异常解决了顺序表为空这种情况,处理方法不一,合理即可

    // 获取 pos 位置的元素public int get(int pos) {if(isEmpty()){throw new EmptyException("顺序表为空!");}if(checkPos(pos)){return this.elem[pos];}return -1;}

将指定pos位置的元素替换成value

先判断顺序表是否为空,在判断pos位置是否合法.满足即可将pos位置的值更新为value

    // 给 pos 位置的元素设为【更新为】 valuepublic void set(int pos, int value) {if(isEmpty()){throw new EmptyException("顺序表为空!");}if(pos < 0 || pos > size()){System.out.println("pos位置不合法");return;}this.elem[pos] = value;}

删除第一次出现的关键字key

先判断顺序表是否为空,是空直接返回
然后判断顺序表中是否存在key,如果存在key,直接让key所在的位置的后面元素,一个一个往前覆盖,如果不存在,直接返回即可

    public void remove(int key) {if(isEmpty()){throw new EmptyException("顺序表为空!");}if(contains(key)) {int ret = indexOf(key);for (int i = ret; i < usedSize; i++) {this.elem[i] = this.elem[i+1];}}this.usedSize--;}

清空顺序表

public void clear() {this.usedSize = 0;}

这里的清空并不是真的清空,而是下次增加元素时,会把之前有的元素覆盖掉.如果不覆盖,那么原来的数据还是存在数组中的
如果想要彻底清空顺序表,就需要使用循环,将数组一个一个置为0

完整代码

主要部分:

import java.util.Arrays;public class MyArrayList {public int[] elem;public int usedSize;//0//默认容量private static final int DEFAULT_SIZE = 10;public MyArrayList() {this.elem = new int[DEFAULT_SIZE];}/*** 打印顺序表:* 根据usedSize判断即可*/public void display() {for (int i = 0; i < this.usedSize; i++) {System.out.print(this.elem[i] + " ");}System.out.println();}/** 新增元素,默认在数组最后新增* 判断顺序表是否满了* 满了->扩容* @param data*/public void add(int data) {if (isFull()) {//扩容this.elem = Arrays.copyOf(this.elem,2*this.elem.length);}this.elem[usedSize] = data;usedSize++;}/*** 判断当前的顺序表是不是满的！* @return true:满   false代表空*/public boolean isFull() {
//        if (size() >= this.elem.length) {
//            return true;
//        }
//        return false;return size() >= this.elem.length;}private boolean checkPos(int pos) {if (pos < 0 || pos > size()) {System.out.println("pos位置不合法");return false;}return true;//合法}/** 在 pos 位置新增元素* 方法：将pos位置的元素向后移动* 情况：*  pos位置不合法*  不能间隔* @param pos* @param data**/public void add(int pos, int data) {if(isFull()){this.elem = Arrays.copyOf(this.elem,2*this.elem.length);}if(checkPos(pos)){for (int i = usedSize; i >= pos; i--) {this.elem[i] = this.elem[i-1];}this.elem[pos] = data;}this.usedSize++;}// 判定是否包含某个元素public boolean contains(int toFind) {for (int i = 0; i < this.usedSize; i++) {if (toFind == this.elem[i]) {return true;} else {continue;}}return false;}// 查找某个元素对应的位置public int indexOf(int toFind) {for (int i = 0; i < this.usedSize; i++) {if (toFind == this.elem[i]) {return i;}}return -1;}// 获取 pos 位置的元素public int get(int pos) {if(isEmpty()){throw new EmptyException("顺序表为空!");}if(checkPos(pos)){return this.elem[pos];}return -1;}//判断顺序表是否为空private boolean isEmpty() {return size()==0;}// 给 pos 位置的元素设为【更新为】 valuepublic void set(int pos, int value) {if(isEmpty()){throw new EmptyException("顺序表为空!");}if(pos < 0 || pos > size()){System.out.println("pos位置不合法");return;}this.elem[pos] = value;}/*** 删除第一次出现的关键字key* @param key*/public void remove(int key) {if(isEmpty()){throw new EmptyException("顺序表为空!");}if(contains(key)) {int ret = indexOf(key);for (int i = ret; i < usedSize; i++) {this.elem[i] = this.elem[i+1];}}this.usedSize--;}// 获取顺序表长度public int size() {return this.usedSize;}// 清空顺序表public void clear() {this.usedSize = 0;}
}

自定义异常部分

public class EmptyException extends RuntimeException{public EmptyException() {}public EmptyException(String message) {super(message);}
}