【数据结构】ArrayList的模拟实现--Java
目录
一、🍩简单了解ArrayList
二、🍩ArrayList的简单模拟实现
1.🍔IList接口
1.🍕IList接口
2. 🍕 MyArrayList 重写接口方法
2.🍔ArrayList方法
1.🥪增
1.add(添加元素):添加在末尾
2.add(插入元素):插入元素在任意位置
2.🥪 查
1.contains(是否包含该元素)
2.get(获取下标元素)
3.indexOf (获取元素下标)
3.🥪删
1.remove(删除元素)
2.clear(清空所有元素)
4.🥪改
1.set(更改元素):将元素进行替换
一、🍩简单了解ArrayList
什么是ArrayList?
在集合框架中,ArrayList是一个普通的类,其内部基于数组实现,数据存储有序,实现的List接口。List是一个接口不能进行实例化,而ArrayList实现了这个接口。
- List就是一个线性表,即具有n个相同类型元素的有限序列,在该序列上可以执行增删查改的功能以及变量等操作。
二、🍩ArrayList的简单模拟实现
1.🍔IList接口
首先,我们知道ArrayList实现了List的接口,所以我们要知道List接口中有哪些方法,并且ArrayLiat要重写List接口中的方法这里我们对其是简单模拟ArrayList,我们实现其一些常见的功能就好。
ArrayList常见方法:
增: | |
void add(int data) | 在数组最后添加元素 |
void add(int pos,int data) | 在数组某下标插入元素 |
删: | |
void remove(int toRemove) | 删除第一次出现的元素 |
void clear(); | 清空所有元素 |
查: | |
boolean contains(int toFind) | 查看是否包含该元素 |
int get(int pos) | 获取该下标元素 |
int indexOf(int toFind ) | 获取该元素下标 |
改: | |
void set(int pos,int value) | 将下标元素进行更改 |
这些常见方法就是增删查改的功能。
1.🍕IList接口
public interface IList {
public void add(int data);
public void add(int pos,int data);
public void remove(int toRemove);
public void clear();
public boolean contains(int toFind);
public int get(int pos);
public int indexOf(int toFind);
public void set(int pos,int value);
}
2. 🍕 MyArrayList 重写接口方法
public class MyArrayList implements IList{
@Override
public void add(int data) {
}
@Override
public void add(int pos, int data) {
}
@Override
public void remove(int toRemove) {
}
@Override
public void clear() {
}
@Override
public boolean contains(int toFind) {
return false;
}
@Override
public int get(int pos) {
return 0;
}
@Override
public int indexOf(int toFind) {
return 0;
}
@Override
public void set(int pos, int value) {
}
}
我们知道,ArrayList内部是基于数组内部实现, 并且他是一个有限序列,所以我们需要在MyArrayList中加几个定义的变量
public class MyArrayList implements IList{
public int[] array;
//默认容量大小
//这个为常量,所以可以使用static final
public static final int DEFULATE_CAPACITY=10;
//以占用的数组空间大小
public int usedsize;
//构造方法
public MyArrayList() {
this.array = new int[DEFULATE_CAPACITY];
}
}
2.🍔ArrayList方法
1.🥪增
1.add(添加元素):添加在末尾
注意事项:
- 是否空间已满,如果满了进行扩容;
- 添加了代码之后,使用空间增加。
public void add(int data) {
//如果满了,进行扩容
if(isFull()){
grows();
}
//数组下标由0开始,在增加一个元素的时候,其下标在第usedsize的位置上
array[usedsize]=data;
usedsize++;
}
判断空间是否已满(isFull):使用空间==空间大小
public boolean isFull(){
return this.usedsize==array.length;
}
扩容(grows):使用Arrays.copyOf进行扩容
public void grows(){
this.array= Arrays.copyOf(this.array,
2*this.array.length);
}
为了更好的查看结果,我们需要加上一个打印方法
展示:注意这里的i是小于数组以使用的长度usedsize,而不是数组的全部长度
public void display(){
for (int i = 0; i < usedsize; i++) {
System.out.print(array[i]+" ");
}
测试:
public class Test {
public static void main(String[] args) {
MyArrayList myArrayList=new MyArrayList();
myArrayList.add(1);
myArrayList.add(2);
myArrayList.add(3);
myArrayList.add(1);
myArrayList.add(2);
myArrayList.add(3);
myArrayList.add(1);
myArrayList.add(2);
myArrayList.add(3);
myArrayList.add(1);
myArrayList.add(2);
myArrayList.add(3);
myArrayList.display();
}
}
结果:
2.add(插入元素):插入元素在任意位置
注意事项:
1.插入元素的下标不能小于0以及不能大于usedsize,否则·报错;
2.插入空间是否已满,满了扩容;
3.已使用数组长度增加;
我们需要检查添加的下标位置是否合法,由于可能会出现位置不合法的情况,如果出现这种情况,要报错,所以我们需要自定义一个位置不合法异常。
PosIlleagal类:继承运行时异常
public class PosIllegal extends RuntimeException{
public PosIllegal() {
super();
}
public PosIllegal(String message) {
super(message);
}
}
出现异常条件:插入元素的下标不能小于0以及不能大于usedsize
checkPos:检查插入元素的下标是否合法
//throws:其提醒作用,可能存在的异常
public void checkPos(int pos) throws PosIllegal{
//如果下标位置不合法,报错
if(pos < 0 || pos >= usedsize){
throw new PosIllegal("位置不合法!!!");
}
}
既然可能会出现异常,我们需要对其进行try-catch捕获处理:
public void add(int pos, int data) {
try{
checkPos(pos);
if(isFull()){
grows();
}
}catch (PosIllegal e){
System.out.println("下标插入位置不合法");
e.printStackTrace();
}catch(Exception e){
e.printStackTrace();
}
}
add(插入元素):我们可以从后往前,将前面的元素向后移动,直到移动到所需插入元素的下标为止,随即插入元素
public void add(int pos, int data) {
try{
checkPos(pos);
if(isFull()){
grows();
}
for (int i = usedsize-1; i >=pos ; i--) {
array[i+1]=array[i];
}
array[pos]=data;
usedsize++;
}catch (PosIllegal e){
System.out.println("下标插入位置不合法");
e.printStackTrace();
}catch(Exception e){
e.printStackTrace();
}
}
测试:
public static void main(String[] args) {
MyArrayList myArrayList=new MyArrayList();
myArrayList.add(1);
myArrayList.add(2);
myArrayList.add(3);
myArrayList.add(3,11);
myArrayList.add(6,5);
myArrayList.display();
}
结果:
2.🥪 查
1.contains(是否包含该元素)
contains:遍历所使用的数组大小,查找是否有该元素
@Override
public boolean contains(int toFind) {
for (int i = 0; i < usedsize; i++) {
if(array[i]==toFind){
return true;
}
}
return false;
}
2.get(获取下标元素)
注意事项:
1.该数组是否为空,如果为空,报错
1.该下标是否合法,如果下标小于0或者下标大于等于usedsize,那么位置不合法;
注意:这里的是大于等于,而插入元素的不合法是大于。
既然我们在使用get方法的时候会出现顺序表为空的情况下,那么我们需要一个顺序表为空时候的异常
EmptyException(顺序表为空异常):
public class EmptyException extends RuntimeException{
public EmptyException() {
}
public EmptyException(String message) {
super(message);
}
}
checkEmpty(顺序表报错条件):
public void checkEmpty() throws EmptyException{
if(usedsize==0){
throw new EmptyException("顺序表为空");
}
}
由于这样的位置不合法条件与插入元素的位置不合法条件不同,所以我们需要再写一个检查位置是否合法的方法
checkPos2(检查pos位置是否合法):
public void checkPos2(int pos) throws PosIllegal{
if(pos < 0 || pos >= usedsize){
throw new PosIllegal("位置不合法!!!");
}
}
get:如果没有出现异常,直接返回下标元素
public int get(int pos) {
try {
checkEmpty();
checkPos2(pos);
return array[pos];
}catch (PosIllegal e){
System.out.println("Pos位置不合法");
e.printStackTrace();
}catch (EmptyException e){
System.out.println("顺序表为空");
e.printStackTrace();
}catch (Exception e){
e.printStackTrace();
}
return -1;
}
3.indexOf (获取元素下标)
注意事项:
1.是否包含该元素,如果没有返回-1;
indexOf:遍历数组元素,查找是否有该元素,有则返回元素下标,没有返回-1
public int indexOf(int toFind) {
if(contains(toFind)){
for (int i = 0; i < usedsize; i++) {
if(array[i]==toFind){
return i;
}
}
}
return -1;
}
测试:
public static void main(String[] args) {
MyArrayList myArrayList=new MyArrayList();
myArrayList.add(1);
myArrayList.add(2);
myArrayList.add(3);
//是否包含
boolean b=myArrayList.contains(5);
System.out.println(b);//false
//获取下标元素
int a=myArrayList.get(2);
System.out.println(a);//3
//获取元素下标
int c=myArrayList.indexOf(0);
System.out.println(c);//-1
int d=myArrayList.indexOf(3);
System.out.println(d);//2
}
结果:
3.🥪删
1.remove(删除元素)
注意事项:
1.顺序表是否为空;
2.是否有该元素;
3.如果删除完该元素,数组使用长度减小。
remove:获取下标,如果下标不存在,返回;如果下标存在,将下标从前往后遍历,将后面的元素向前移动
public void remove(int toRemove) {
try{
checkEmpty();
//获取下标
int pos=indexOf(toRemove);
if(pos==-1){
System.out.println("没有该元素,移除失败");
return;
}
//从前往后,将后面的元素向前移动
//i是小于usedsize-1就好,因为当i=usedsize-2
//将usedsize-1中的元素移到了usedsize-2中
for (int i = pos; i < usedsize-1; i++) {
array[i]=array[i+1];
}
usedsize--;
}catch (EmptyException e){
System.out.println("顺序表为空");
e.printStackTrace();
}catch(Exception e){
e.printStackTrace();
}
}
2.clear(清空所有元素)
clear:直接将使用空间置0;
public void clear() {
this.usedsize=0;
}
测试:
public static void main(String[] args) {
MyArrayList myArrayList=new MyArrayList();
myArrayList.add(1);
myArrayList.add(2);
myArrayList.add(3);
myArrayList.display();
System.out.println();//1 2 3
//移除:
myArrayList.remove(2);
myArrayList.display();
System.out.println();//1 3
myArrayList.remove(5);//没有该元素,移除失败
System.out.println();
//清空:
myArrayList.clear();
myArrayList.display();
myArrayList.add(1);
myArrayList.display();//1
}
4.🥪改
1.set(更改元素):将元素进行替换
注意事项:
1.顺序表是否为空;
2.进行更改的元素下标是否合法
set:直接将下标所对于的元素进行更改
public void set(int pos, int value) {
try{
checkEmpty();
checkPos2(pos);
array[pos]=value;
}catch (EmptyException e){
System.out.println("顺序表为空");
e.printStackTrace();
}catch (PosIllegal e){
System.out.println("下标位置不合法");
e.printStackTrace();
}catch(Exception e){
e.printStackTrace();
}
}
测试:
public static void main(String[] args) {
MyArrayList myArrayList=new MyArrayList();
myArrayList.add(1);
myArrayList.add(2);
myArrayList.add(3);
myArrayList.display();//1 2 3
System.out.println();
myArrayList.set(2,11);//1 2 11
myArrayList.display();
System.out.println();
myArrayList.set(5,11);//报错
myArrayList.display();
}
结果: