从零手工实现java中的ArrayList容器（三个版本的迭代）
注：为方便理解，分为三个版本，每个版本在上一个的基础上扩展，如果你有足够的基础，可以直接翻到最下面看最终版本代码，我会详细注释
内部方法与变量
add(),set(),get(),remove(),empty(),size(),checkRank(),toString()
size,elementData [],DEFAULT_CAPACITY
核心问题
| 问题 | 方法 |
|---|---|
| 列表的存储结构是什么？ | object型数组 |
| 如果扩展列表？ | 新建一个更大的数组取代原数组 |
| 如何适用所有类型元素 | 设置泛型 |
| 如何删除元素 | 让目标元素后面的元素依次往前挪，最后一个设为null |
以上都是实现ArrayList的指导思想，接下来我们直接上代码
第一版
package collection;
/**
* 自定义实现一个ArrayList
*/
public class MyArrayList {
//存储元素的数组
private Object [] elementData;
//当前元素的个数
private int size;
//数组默认大小
private final static int DEFAULT_CAPACITY=10;
public MyArrayList(int capacity){
elementData=new Object[capacity];
}
//当没有设置列表大小时，默认为10
public MyArrayList(){
elementData=new Object[DEFAULT_CAPACITY];
}
//每加一个元素，先把元素放在size位置处（因为此时数组中最后一个元素位于size-1处）,然后size++
public void add(Object object){
elementData[size++]=object;
}
//将数组转换为列表的样式输出，
@Override
public String toString() {
StringBuilder stringBuilder=new StringBuilder("[");
for(int i=0;i<size;i++) {
stringBuilder.append(elementData[i]);
stringBuilder.append(",");
}
//现在stringBuilder中最后一个字符时逗号，我们将它转换为]号
stringBuilder.setCharAt(stringBuilder.length()-1,']');
return stringBuilder.toString();
}
public static void main(String[] args){
MyArrayList myArrayList =new MyArrayList();
myArrayList.add("a");
System.out.println(myArrayList);
for(int i=0;i<5;i++){
myArrayList.add("a"+i);
}
System.out.println(myArrayList);
}
}
效果如图
但是明显有很多问题，除了方法少之外，还有数组越界没有检查，而且不能设置泛型
第二版
package collection;
/**
* arraylist数组扩容add()，泛型,size,empty
*/
//设置泛型比较简单，直接在类名后加，并且修改传入元素的类型名(add())
public class MyArrayList02<E> {
private Object [] elementData;
private int size;
private final static int DEFAULT_CAPACITY=10;
public MyArrayList02(int capacity){
elementData=new Object[capacity];
}
public MyArrayList02(){
elementData=new Object[DEFAULT_CAPACITY];
}
//边界检查，当实际容量(size)达到了数组最大容量之后
//我们将新建一个比原来大1/2的数组，然后再赋给原来的数组
public void add(E object){
if(size==elementData.length){
Object [] newArray=new Object[elementData.length+elementData.length<<1];
System.arraycopy(elementData,0,newArray,0,elementData.length);
elementData=newArray;
}
elementData[size++]=object;
}
//获得列表长度
public int size(){
return size;
}
//判定是否为空
public boolean empty(){
if(size==0){
return true;
}
return false;
}
@Override
public String toString() {
StringBuilder stringBuilder=new StringBuilder("[");
for(int i=0;i<size;i++) {
stringBuilder.append(elementData[i]);
stringBuilder.append(",");
}
stringBuilder.setCharAt(stringBuilder.length()-1,']');
return stringBuilder.toString();
}
public static void main(String[] args){
MyArrayList03<String> myArrayList02 =new MyArrayList03<>();
for(int i=0;i<20;i++) {
myArrayList02.add("a"+i);
}
System.out.println(myArrayList02);
System.out.println("数组长度："+myArrayList02.size());
System.out.println("数组是空吗？"+myArrayList02.empty());
}
}
原数组默认只有10，自动将数组扩容，新增大小为原来的1/2，用移位的方法获得，这也是ArrayList源码中使用的方法，并且新增了size(),empty()方法
但是，依旧有问题，比如新建一个空列表~
第三版
package collection;
/**
* set,get,checkRank边界检查,remove
*/
public class MyArrayList03<E> {
private Object [] elementData;
private int size;
private final static int DEFAULT_CAPACITY=10;
//这里表示传入有容量的列表
public MyArrayList03(int capacity){
if(capacity<0){
throw new RuntimeException("容量不能为负");
}
elementData=new Object[capacity];
}
//这里是没有传参的列表，默认容量是10
public MyArrayList03(){
elementData=new Object[DEFAULT_CAPACITY];
}
//添加元素，先判定是否到了数组边界，如果到了就扩容，然后添加一个位置
public void add(E object){
if(size==elementData.length){
Object [] newArray=new Object[elementData.length+elementData.length<<1];
System.arraycopy(elementData,0,newArray,0,elementData.length);
elementData=newArray;
}
elementData[size++]=object;
}
//移除元素，将目标元素后面的元素挨个赋给前一位，这样会导致最后一位和倒数第二位相同，size--不输出最后一位
//为了避免意外错误，我们把最后一位手动设为空
public void remove(int index){
//a,b,c,d,e,f
//a,b,c,e,f
checkRank(index);
int moveElement=size-index-1;
if(moveElement>0) {
elementData[size] = null;
System.arraycopy(elementData, index + 1, elementData, index, moveElement);
}
size--;
}
@Override
public String toString() {
StringBuilder stringBuilder=new StringBuilder("[");
if(size==0)stringBuilder.append("]");
//这里以size为输出大小，所以以后的add或者remove等只需要修改size就可以获得位置或者删除位置
for(int i=0;i<size;i++) {
stringBuilder.append(elementData[i]);
stringBuilder.append(",");
}
//将最后一个逗号改为"]"
stringBuilder.setCharAt(stringBuilder.length()-1,']');
return stringBuilder.toString();
}
public E get(int index){
checkRank(index);
return (E)elementData[index];
}
public void set(E e,int index){
checkRank(index);
elementData[index]=e;
}
//检查数组是否越界
public void checkRank(int index){
if(index<0||index>size-1){
throw new ArrayIndexOutOfBoundsException("索引不合法");
}
}
//获得列表长度
public int size(){
return size;
}
//判定是否为空
public boolean empty(){
if(size==0){
return true;
}
return false;
}
public static void main(String[] args){
MyArrayList03<String> myArrayList03 =new MyArrayList03<>();
System.out.println(myArrayList03);
for(int i=0;i<1;i++)
myArrayList03.add("a"+i);
System.out.println("添加1个元素后列表长度为"+myArrayList03.size());
System.out.println("列表元素 "+myArrayList03);
myArrayList03.remove(0);
System.out.println("删除第一个元素后 "+myArrayList03);
}
}
进行了更多的边界检查，同时新增了remove(),get,set等使用方法，也改进了toString方法
