顺序表——模拟ArrayList的实现(java)
先定义接口List,列出需要实现的方法:
package com.qianyu.dataStructure.lineTable;
/**
* @author lijing
* @date 2019-03-19-19:38
* @discroption 模拟List接口
*/
public interface List {
//返回线性表的大小
public int size();
//返回线性表中序号为i的数据元素
public Object get(int i);
//如果线性表为空则返回true,否则返回false
public boolean isEmpty();
//判断线性表是否包含元素e
public boolean contains(Object e);
//返回数据元素e在线性表中的序号
public int indexOf(Object e);
//建数据元素e插入到线性表中第i个位置
public void add(int i,Object e);
//将数据元素e插入到线性表的末尾
public void add(Object e);
//删除集合中序号为i的元素,并返回之
public Object remove(int i);
//删除集合中第一个与e相同的元素
public boolean remove(Object e);
//替换集合中序号为i的数据元素为e,返回数据元素
public Object replace(int i,Object e);
}
自定义异常:MyIndexOutOfBoundsException
package com.qianyu.dataStructure.lineTable;
/**
* @author lijing
* @date 2019-03-19-20:34
* @discroption 自定义异常
*/
public class MyIndexOutOfBoundsException extends RuntimeException{
public MyIndexOutOfBoundsException() {
super();
}
public MyIndexOutOfBoundsException(String message) {
super(message);
}
}
实现List接口:
package com.qianyu.dataStructure.lineTable;
import java.util.Arrays;
/**
* @author lijing
* @date 2019-03-19-20:00
* @discroption 用线性表来模拟实现ArrayList
*/
public class ArrayList implements List {
/**
* 储存元素的数组
*/
private Object[] elementData;
/**
* 这个size并表示给数组分配的内存,而表示ArrayList中元素的个数
*/
private int size;
/**
* 有参构造函数
*
* @param initialCapacity 表示初始数组的大小
*/
public ArrayList(int initialCapacity) {
//给数组分配内存
elementData = new Object[initialCapacity];
//初始化size为0
this.size = 0;
}
/**
* 无参构造函数
*/
public ArrayList() {
//调用有参构造函数,将初始长度设为10
this(10);
}
/**
* @return 返回ArrayList中元素的个数
*/
@Override
public int size() {
return size;
}
/**
* @param i 索引(从0开始)
* @return 找到索引对应元素
*/
@Override
public Object get(int i) {
//判断如果索引不和规范就抛出异常
if (i < 0 || i >= this.size) {
throw new MyIndexOutOfBoundsException("无效的索引值:" + i);
}
return this.elementData[i];
}
/**
* 如果ArrayList中没有元素就返回true
*
* @return
*/
@Override
public boolean isEmpty() {
return size == 0;
}
/**
* 直接调用indexOf()函数,如果找到就返回true,找不到就返回false
*
* @param e
* @return
*/
@Override
public boolean contains(Object e) {
return indexOf(e) >= 0;
}
/**
* 返回ArrayList中元素e的下标
*
* @param e
* @return
*/
@Override
public int indexOf(Object e) {
//分两种情况,e为null和e不为null两种情况
if (e == null) {
for (int i = 0; i < this.size; i++) {
if (this.elementData[i] == null) {
return i;
}
}
} else {
for (int i = 0; i < this.size; i++) {
if (this.elementData[i].equals(e)) {
return i;
}
}
}
return -1;
}
/**
* 这指定位置插入元素
*
* @param i 指定索引
* @param e 插入的元素
*/
@Override
public void add(int i, Object e) {
//判断索引是否合法
if (i < 0 || i > this.size) {
throw new MyIndexOutOfBoundsException("非法的索引:" + i);
}
//先判断数组的元素是否够用,不够用就扩容数组
if (size == this.elementData.length) {
//调用扩容数组的方法
grow();
}
//从最后一个元素开始后移,将位置空出来
for (int j = this.size; j > i; j--) {
this.elementData[j] = this.elementData[j - 1];
}
//将元素插入到空出来的位置中
//这里注意数组中的i和size(数组的长度相差1)
this.elementData[i] = e;
//将长度加一
this.size++;
}
/**
* 向ArrayList中增加元素
*
* @param e
*/
@Override
public void add(Object e) {
//相当于加末尾追加元素
this.add(size, e);
}
/**
* 扩容数组的方法
*/
private void grow() {
Object[] newArr = new Object[this.elementData.length * 2];
for (int i = 0; i < this.elementData.length; i++) {
newArr[i] = this.elementData[i];
}
this.elementData = newArr;
/**
* 以上代码可以简写为如下代码
* this.elementData = Arrays.copyOf(elementData, elementData.length * 2);
*/
}
@Override
public Object remove(int i) {
//判断索引是否合法
if (i < 0 || i > this.size - 1) {
throw new MyIndexOutOfBoundsException("非法的索引:" + i);
}
Object e = this.elementData[i];
/*
System.arraycopy()函数参数的意义
Object src : 原数组
int srcPos : 从元数据的起始位置开始
Object dest : 目标数组
int destPos : 目标数组的开始起始位置
int length : 要copy的数组的长度
*/
System.arraycopy(this.elementData, i + 1, this.elementData, i, this.size - i - 1);
//将最后一个元素置空,注意size(数组的长度)减一之后才是最后一个元素的位置
this.elementData[--size] = null;
return e;
}
/**
* 删除ArrayList中第一个为e的元素
*
* @param e
* @return
*/
@Override
public boolean remove(Object e) {
//先判断e知否为null
//注意遍历数组的时候用this.size,不可用this.elementData.length,否则就会产生空指针异常
if (e == null) {
for (int i = 0; i < this.size; i++) {
if (this.elementData[i] == null) {
this.remove(i);
return true;
}
}
} else {
for (int i = 0; i < this.size; i++) {
if (this.elementData[i].equals(e)) {
this.remove(i);
return true;
}
}
}
return false;
}
/**
* 替换元素
*
* @param i
* @param e
* @return
*/
@Override
public Object replace(int i, Object e) {
//判断索引是否合法
if (i < 0 || i > this.size - 1) {
throw new MyIndexOutOfBoundsException("非法的索引:" + i);
}
Object oldObj = this.elementData[i];
this.elementData[i] = e;
return oldObj;
}
@Override
public String toString() {
return "ArrayList{" +
"elementData=" + Arrays.toString(elementData) +
", length=" + elementData.length +
", size=" + size +
'}';
}
}
测试类:
package com.qianyu.test;
import com.qianyu.dataStructure.lineTable.ArrayList;
/**
* @author lijing
* @date 2019-03-19-20:01
* @discroption
*/
public class TestArrayListA {
public static void main(String[] args) {
ArrayList arrayList = new ArrayList();
System.out.println("是否为空:" + arrayList.isEmpty());
arrayList.add(111);
arrayList.add(222);
arrayList.add(333);
System.out.println("ArrayList的长度:" + arrayList.size());
System.out.println("索引为2个元素:" + arrayList.get(2));
System.out.println("是否为空:" + arrayList.isEmpty());
System.out.println("是否包含222:" + arrayList.contains(222));
System.out.println("是否包含778:" + arrayList.contains(778));
System.out.println("222所在的位置:" + arrayList.indexOf(222));
arrayList.add(2, "hello");
System.out.println(arrayList);
System.out.println(arrayList.remove(0));
System.out.println("删除索引为0的元素:" + arrayList);
arrayList.remove(new Integer(333));
System.out.println("删除333:"+arrayList);
arrayList.replace(0, "qianyu");
System.out.println("替换索引为0的元素:"+arrayList);
try {
System.out.println(arrayList.get(4));
} catch (Exception e) {
e.printStackTrace();
}
//测试数组扩容
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
arrayList.add(4);
arrayList.add(5);
arrayList.add(6);
arrayList.add(7);
arrayList.add(8);
arrayList.add(9);
arrayList.add(10);
System.out.println(arrayList);
}
}
运行结果: