正文
造轮子ArrayList
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
这篇博客实现一个简单的ArrayList集合.博客里的代码首先根据自己的想法实现,在走不动的情况下会去参考JDK源代码.所以阅读本文,不要抱着跟JDK源码对比的心态.于我个人而言,国庆期间,纯属娱乐.写完打游戏去.
首先写搭建一个架子
public class MyArrayList<E> {
/*
* 注意ArrayList的大小是可变的,此处设定的数组大小为默认大小,和每次扩建的大小
* */ //默认的数组大小
private int DEFAULT_CAPACITY = 1;
//存储元素的数组
private Object[] elements; //当前下标默认值
private int index = 0; //构造一个默认长度的集合
public MyArrayList() {
this.elements = new Object[DEFAULT_CAPACITY];
} //构造一个指定长度的集合.
public MyArrayList(int capacity) {
this.DEFAULT_CAPACITY = capacity;
this.elements = new Object[DEFAULT_CAPACITY];
} //添加元素
public boolean add(E e) {
//设置元素到指定下标位置
elements[index] = e;
//下标自增
index++;
return true;
} //返回当前集合长度
public int size(){
return index;
}
}
public class Main {
public static void main(String[] args) {
MyArrayList<Integer> myArrayList = new MyArrayList();
myArrayList.add(1);
System.out.println(myArrayList.size());//
}
}
我们再来尝试创建一个指定大小的集合.
public class Main {
public static void main(String[] args) {
MyArrayList<Integer> myArrayList = new MyArrayList(0);
myArrayList.add(1);
System.out.println(myArrayList.size());
}
}
这时是会报错的,如果你指定了一个大小为0的集合,那么会造成下标越界.所以我们要对集合进行修改
//构造一个指定长度的集合.
public MyArrayList(int capacity) {
if(capacity>0){
DEFAULT_CAPACITY = capacity;
}this.elements = new Object[DEFAULT_CAPACITY ];
}
如果我们添加元素时,已经超过了数组的下标,也是会报错的.接下来我们要做对数组的扩建.
我们引入另一个临时的数组
//临时存储元素的数组
private Object[] tempElements;
并且修改add()方法
//添加元素
public boolean add(E e) {
//现在数组已经满了
if (index==elements.length){
tempElements = new Object[elements.length+DEFAULT_CAPACITY]; //接着我们需要将已经有的元素copy到新数组内
for(int x=0;x<elements.length;x++){
tempElements[x] = elements[x];
} //然后我们将老的数组重新创建
elements = new Object[elements.length+DEFAULT_CAPACITY];
//最后我们将临时数组的元素,重新放置到新数组中
for(int x=0;x<tempElements.length;x++){
elements[x] = tempElements[x];
} }
//设置元素到指定下标位置
elements[index] = e;
//下标自增
index++;
return true;
}
public class Main {
public static void main(String[] args) {
MyArrayList<Integer> myArrayList = new MyArrayList(0);
myArrayList.add(1);
myArrayList.add(2);
myArrayList.add(3);
myArrayList.add(4);
System.out.println(myArrayList.size());//
}
}
此时我们的集合,则有了自动扩建大小的功能.
接下来我们来实现一个get()
//获取指定下标的元素
public E get(int index){
return (E)elements[index];
}
public class Main {
public static void main(String[] args) {
MyArrayList<Integer> myArrayList = new MyArrayList(3);
myArrayList.add(1);
System.out.println(myArrayList.get(0));//
System.out.println(myArrayList.get(1));//null
System.out.println(myArrayList.get(2));//null
System.out.println(myArrayList.get(3));// java.lang.ArrayIndexOutOfBoundsException: 3
}
}
这个结果显然不是我们想要的,我们初始化一个大小为3的集合,并且设置1个元素,此时我们只添加一个元素.其他两个为null,原因是我们创建的Object数组,数组中没有元素默认值它就是null,至于下标越界则是正常情况.此时我们应该加一个限制.
//获取指定下标的元素
public E get(int index) {
if (index >= this.index) {
throw new RuntimeException("您访问了不存在的元素,当前元素个数最大为" + this.index + "");
}
return (E) elements[index];
}
此处抛出一个RuntimeException,运行时异常模仿JDK中,不让用户try,catch异常.
public class Main {
public static void main(String[] args) {
MyArrayList<Integer> myArrayList = new MyArrayList(3);
myArrayList.add(1);
System.out.println(myArrayList.get(0));//
System.out.println(myArrayList.get(1));//您访问了不存在的元素,当前元素个数最大为1
}
}
同样我们的set()方法也应该具备检验的能力,所以我们将检验的代码抽离出来.
//获取指定下标的元素
public E get(int index) {
check(index);
return (E) elements[index];
} //替换指定位置的元素
public E set(int index, E e) {
check(index);
E old = (E) elements[index];
elements[index] = e;
return old;
} //检验下标是否越界
private void check(int index) {
if (index >= this.index) {
throw new RuntimeException("您访问了不存在的元素,当前元素个数最大为" + this.index + "");
}
}
public class Main {
public static void main(String[] args) {
MyArrayList<Integer> myArrayList = new MyArrayList(3);
myArrayList.add(1);
System.out.println(myArrayList.set(0, 2));//
System.out.println(myArrayList.set(1, 2));//您访问了不存在的元素,当前元素个数最大为1
}
}
实现根据下标删除元素
//删除指定位置的元素
public E remove(int index) {
check(index);
/*
* 删除指定下标的元素
* 1 创建一个新的数组,大小为删除元素后的数组大小.
* 2 将下标前的数组元素取出
* 3 将下标后的数组元素取出
* */
E removeObj = (E) elements[index];
Object[] newObj = new Object[this.index];
for (int i = 0; i < index; i++) {
newObj[i] = elements[i];
}
for (int i = index + 1; i < this.index; i++) {
newObj[i - 1] = elements[i];
}
elements = newObj; return removeObj;
}
public class Main {
public static void main(String[] args) {
MyArrayList<Integer> myArrayList = new MyArrayList(3);
myArrayList.add(1);
myArrayList.add(2);
myArrayList.add(3);
myArrayList.add(4);
myArrayList.add(5);
Integer remove = myArrayList.remove(3);
System.out.println(remove);//
System.out.println(myArrayList.get(0));//
System.out.println(myArrayList.get(1));//
System.out.println(myArrayList.get(2));//
System.out.println(myArrayList.get(3));// }
}
至此我们还差最后一个东西,迭代.我们要遍历集合
public class Main {
public static void main(String[] args) {
MyArrayList<Integer> myArrayList = new MyArrayList(3);
myArrayList.add(1);
myArrayList.add(2);
myArrayList.add(3);
myArrayList.add(4);
myArrayList.add(5);
for (Object i:myArrayList){
System.out.println(i);
}
}
}
我们要用增强for,但是呢,这个增强for需要集合实现一个接口
public class MyArrayList<E> implements Iterable
这个接口需要实现一个方法,这个方法需要返回一个Iterator
@Override
public Iterator iterator() {
return new MyIterator();
}
class MyIterator implements Iterator{
@Override
public boolean hasNext() {
return false;
} @Override
public Object next() {
return null;
}
}
这里我们使用一个内部类,这个内部类实现Iterator.下边我们要把这两个方法给实现了.
class MyIterator implements Iterator{
int i = 0;
@Override
public boolean hasNext() {
if(index>i){
return true;
}
return false;
} @Override
public Object next() {
return elements[i++];
}
}
其实呢,这个所谓的迭代器,维护的就是一个指针,hasNext()就是判断有没有下一个元素,那就是判断elements的index下标.每次next()执行就把指针自增1.
到此一个简单的ArrayList就完成了.
最后附录一个完整的代码
import java.util.Iterator; public class MyArrayList<E> implements Iterable {
/*
* 注意ArrayList的大小是可变的,此处设定的数组大小为默认大小,和每次扩建的大小
* */ //默认的数组大小
private int DEFAULT_CAPACITY = 1; //存储元素的数组
private Object[] elements; //临时存储元素的数组
private Object[] tempElements; //当前下标默认值
private int index = 0; //构造一个默认长度的集合
public MyArrayList() {
this.elements = new Object[DEFAULT_CAPACITY];
} //构造一个指定长度的集合.
public MyArrayList(int capacity) {
if (capacity > 0) {
DEFAULT_CAPACITY = capacity;
}
this.elements = new Object[DEFAULT_CAPACITY];
} //添加元素
public boolean add(E e) {
//现在数组已经满了
if (index == elements.length) {
tempElements = new Object[elements.length + DEFAULT_CAPACITY]; //接着我们需要将已经有的元素copy到新数组内
for (int x = 0; x < elements.length; x++) {
tempElements[x] = elements[x];
} //然后我们将老的数组重新创建
elements = new Object[elements.length + DEFAULT_CAPACITY];
//最后我们将临时数组的元素,重新放置到新数组中
for (int x = 0; x < tempElements.length; x++) {
elements[x] = tempElements[x];
} }
//设置元素到数组
elements[index] = e;
//将下标自增
index++;
return true;
} //返回当前集合长度
public int size() {
return index;
} //获取指定下标的元素
public E get(int index) {
check(index);
return (E) elements[index];
} //替换指定位置的元素
public E set(int index, E e) {
check(index);
E old = (E) elements[index];
elements[index] = e;
return old;
} //检验下标是否越界
private void check(int index) {
if (index >= this.index) {
throw new RuntimeException("您访问了不存在的元素,当前元素个数最大为" + this.index + "");
}
} //删除指定位置的元素
public E remove(int index) {
check(index);
/*
* 删除指定下标的元素
* 1 创建一个新的数组,大小为删除元素后的数组大小.
* 2 将下标前的数组元素取出
* 3 将下标后的数组元素取出
* */
E removeObj = (E) elements[index];
Object[] newObj = new Object[this.index];
for (int i = 0; i < index; i++) {
newObj[i] = elements[i];
}
for (int i = index + 1; i < this.index; i++) {
newObj[i - 1] = elements[i];
}
elements = newObj; return removeObj;
} @Override
public Iterator iterator() {
return new MyIterator();
} class MyIterator implements Iterator{
int i = 0;
@Override
public boolean hasNext() {
if(index>i){
return true;
}
return false;
} @Override
public Object next() {
return elements[i++];
}
}
}