ArrayList

• ArrayList
• 相关接口
• 代码
• 最后：自己的一些感想

大家好，我是青菜不青。

今天来分享一下手写一个小小ArrayList，希望对再看的小伙伴有所帮助！

希望大家一起不断成长。

ArrayList

数组是一种顺序存储的线性表，存储的地址是连续的。数组的一大缺点就是无法动态修改容量。

Java提供的包下的ArrayList，是为了弥补数组这一缺陷，我们也将ArrayList称为动态数组

相关接口

本文中，我实现了部分常用接口，ArrayList源码设计的比较庞大，继承了父类以及实现了很多接口。我们就不用这么麻烦了，手写一部分常用的方法逻辑以作学习。

• int size(); // 元素的数量
• boolean isEmpty(); // 是否为空
• boolean contains(E element); // 是否包含某个元素
• void add(E element); // 添加元素到最后面
• E get(int index); // 返回index位置对应的元素
• E set(int index, E element); // 设置index位置的元素
• void add(int index, E element); // 往index位置添加元素
• E remove(int index); // 删除index位置对应的元素
• int indexOf(E element); // 查看元素的位置
• void clear(); // 清除所有元素

实现之前，我们来说一说作为一个类来说，ArrayList内部需要的一些属性。

首先我们需要一个内部的数组，来存储数据。为了满足容量，以及遍历的操作，我们提供一个叫size的属性来描述，数组中有多少数据。

我们使用了泛型

public class ArrayList<E> {    private E[] element;    private int size;    //...接口}

对于一个类来说，构造函数是必不可少的。我们也提供两个构造函数。当数量小于10的时候，默认设置数组大小为10，如果大于10就按照传入值设置大小

这里我们要注意，使用泛型的时候写成element = new E[capacity]；这样是不可取的，编译的时候不会通过，因为编译器无法获取到E的确定类型。

已知所有数据类型都可以放置在Object类型的数组中，这里发生是向上转型。基本数据类型的包装类是继承了Object的，而我们自己定义的一些类，默认也是继承Object的

public class ArrayList {    private int[] element;    private int size;    private static final int Default_Capacity = 10;public ArrayList(int capacity){ capacity = (capacity > Default_Capacity ? capacity : Default_Capacity); element = (E[]) new Object[capacity];    }    public ArrayList(){ this(Default_Capacity);    }    //...接口}    

那接下来，我们开始实现接口吧！

int size() 获取元素数量

public int size(){ return size;}

boolean isEmpty(); // 是否为空

public boolean isEmpty(){ return size==0;    }

boolean contains(E element); // 是否包含某个元素

public boolean contains(E value){    return indexOf(value) != -1;}

void add(E element); // 添加元素到最后面

• 这里我们实现了复用接口

public void add(E value){    /*element[size] = value;    size++;*/    add(size, value);}

void add(int index, E element); // 往index位置添加元素

• 对于下标不合法的情况，我们要抛出错误

• add操作本质就是移位

  

• 在添加元素之前，我们需要判定数组element空间是否足够，不够就需要扩容。创建一个新数组，将element的数据拷贝过去，然后就将element指向到这份新数组上

//保证容量    public void addCapcity(int capacity){ if(element.length >= capacity){     return; }else{     int newCapcity = element.length * 2;     E[] newElement = (E[]) new Object[newCapcity];     for(int i = 0; i < size; i++){  newElement[i] = element[i];     }     element = newElement; }    }public void add(int index, E value){    if(index < 0 || index > size){ throw new IndexOutOfBoundsException("Index:"+index + ",Size:"+size+",下标越界");    }    addCapcity(size + 1);    for(int i = size - 1; i >=index; i--){ element[i+1] = element[i];    }    element[index] = value;    size++;}

E remove(int index); // 删除index位置对应的元素

• 删除元素同样需要判断下标是否合理，删除的逻辑与添加的逻辑相似，也需要挪动数据

  

public E remove(int index){    if(index < 0 || index >= size){ throw new IndexOutOfBoundsException("Index:"+index + ",Size:"+size+",下标越界");    }    E tmp = element[index];    for(int i = index + 1; i < size; i++){ element[i - 1] = element[i];    }    size--;    element[size] = null;    return tmp;}

int indexOf(E element); // 查看元素的位置

• 注意我们这里使用equals，不使用==，使用==的时候，对于引用类型，判断的是地址是否相同，这样太狭隘了。我们一般会重写对象的equals。

  这里是我自定义类Person中的重写

  

• 另外，这里我们少做了一些判断，当element中有null的时候，调用equals会判错。

  看看源码的写法：库中是对null进行了专门处理的。只能说太面面俱到了

  

public int indexOf(E value){    for(int i = 0; i < size; i++){ if(element[i].equals(value)) return i;    }    return -1;}

E get(int index); // 返回index位置对应的元素

public E get(int index){    if(index < 0 || index >= size){ throw new IndexOutOfBoundsException("Index:"+index + ",Size:"+size+",下标越界");    }    return element[index];}

E set(int index, E element); // 设置index位置的元素

public E set(int index, E value){    if(index < 0 || index >= size){ throw new IndexOutOfBoundsException("Index:"+index + ",Size:"+size+",下标越界");    }    E tmp = element[index];    element[index] = value;    return tmp;}

void clear(); // 清除所有元素

• 对于基本数据类型，我们当然可以直接size=0，但是ArrayList不仅仅需要存储基本数据类型，还需要存储引用数据类型，当存储引用数据类型的时候，数组中存储的实际是一个个地址值，然后指向堆空间的数据，我们要手动释放这些对象的空间，否则最终释放他们的时候，会是在程序结束以后。

  我们可以通过对象的finalize()方法确定这些堆空间内存确实被释放了

  

  如果我们采用size=0,就可以看到，不会打印Person销毁，也就是内存并不是我们手动释放的

• 为什么不使用element = null呢？element=null是将ArrayList置空，那么我们再次使用一个ArrayList的时候就需要重新调用构造函数，申请空间。能重复利用为什么不用呢？

  当element=null的时候，我们将红线断开了，红线都断开了，更别说是黑线了，那么element和堆空间都不会通过arr找到，但是我们在程序后续还要使用arr的时候，就需要重新为element开辟空间。这样性能就不好了，所以我们采用将element中的每一个元素置空。当再次使用arr的时候，直接将element[i]指向对应地址即可

  

public void clear(){    //销毁指向的引用数据变量    for(int i = 0; i < element.length; i++){ element[i] = null;    }    size = 0;}

最后，为了实现打印，我们实现一个toString方法

public String toString(){ StringBuffer string = new StringBuffer(); string.append("size=").append(size).append(",["); for(int i = 0; i < size; i++){     if(i != 0){  string.append(",");     }     string.append(element[i]); } string.append("]"); return string.toString();    }

源码中的toString写在了继承的父类中

代码

public class ArrayList<E> {    private E[] element;    private int size;    private static final int Default_Capacity = 10;    public ArrayList(int capacity){ capacity = (capacity > Default_Capacity ? capacity : Default_Capacity); element = (E[]) new Object[capacity];    }    public ArrayList(){ this(Default_Capacity);    }    public int indexOf(E value){ for(int i = 0; i < size; i++){     if(element[i].equals(value)) return i; } return -1;    }    public boolean isEmpty(){ return size==0;    }    public boolean contains(E value){ return indexOf(value) != -1;    }    public int size(){ return size;    }    public void add(E value){ /*element[size] = value; size++;*/ add(size, value);    }    public void addCapcity(int capacity){ if(element.length >= capacity){     return; }else{     int newCapcity = element.length * 2;     E[] newElement = (E[]) new Object[newCapcity];     for(int i = 0; i < size; i++){  newElement[i] = element[i];     }     element = newElement; }    }    public void add(int index, E value){ if(index < 0 || index > size){     throw new IndexOutOfBoundsException("Index:"+index + ",Size:"+size+",下标越界"); } addCapcity(size + 1); for(int i = size - 1; i >=index; i--){     element[i+1] = element[i]; } element[index] = value; size++;    }    public void clear(){ //销毁指向的引用数据变量 //不压迫element = null--->循环利用 for(int i = 0; i < element.length; i++){     element[i] = null; } size = 0;    }    public E set(int index, E value){ if(index < 0 || index >= size){     throw new IndexOutOfBoundsException("Index:"+index + ",Size:"+size+",下标越界"); } E tmp = element[index]; element[index] = value; return tmp;    }    public E get(int index){ if(index < 0 || index >= size){     throw new IndexOutOfBoundsException("Index:"+index + ",Size:"+size+",下标越界"); } return element[index];    }    public E remove(int index){ if(index < 0 || index >= size){     throw new IndexOutOfBoundsException("Index:"+index + ",Size:"+size+",下标越界"); } E tmp = element[index]; for(int i = index + 1; i < size; i++){     element[i - 1] = element[i]; } size--; element[size] = null; return tmp;    }    public String toString(){ StringBuffer string = new StringBuffer(); string.append("size=").append(size).append(",["); for(int i = 0; i < size; i++){     if(i != 0){  string.append(",");     }     string.append(element[i]); } string.append("]");// System.out.println(string.toString()); return string.toString();    }}

然后是我定义的Person，用来做测试泛型的

public class Person {    public int age;    private String name;    public Person(int age, String name){ this.age = age; this.name = name;    }    public void finalize() throws Throwable{ super.finalize(); System.out.println("Person销毁了");    }    @Override    public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Person person = (Person) o; return age == person.age && Objects.equals(name, person.name);    }}

最后：自己的一些感想

看了一些源码，觉得设计这些的人真是太强了，实现每一个接口，或者继承父类，达到复用的效果。

文章如果有错误，还请小伙伴们多多指正！