Array的实现——java语言

1.只能存放int的自定义数组类

public class Array {

   private int[] data;

   private int size;//data[size]指向数组中第一个没有数据的位置

   //传入数组的容量capacity构造Array

   public Array(int capacity){

       data=new int[capacity];

       size=0;

   }

   //无参构造，默认数组capacity为10

   public Array(){

       data=new int[10];

   //获取数组已有长度

   public int getSize(){

       return size;

   //获取数组容量

   public int getCapacity(){

       return data.length;

   //判断数组是否为空

   public boolean isEmpty(){

       return size==0;

   //向数组尾部添加数据

   public void addLast(int e){

       add(size,e);

   //向数组头添加数据

   public void addFirst(int e){

       add(0,e);

   //向数组中任意一个位置添加数据

   public void add(int index,int e){

       if(data.length==size)

           throw new IllegalArgumentException("array is full");

       if(index<0||index>size)

       for(int i=size-1;i>=index;i--){

           data[i+1]=data[i];

       }

       data[index]=e;

       size++;

   //获取某个索引元素

   public int get(int index,int e){

       if(index<0||index>=size)

           throw new IllegalArgumentException("index error");

       return data[index];

   //设置某个索引位置元素

   public void set(int index,int e){

   //判断数组是否包含某个元素

   public boolean contains(int e){

       for(int i=0;i<size;i++){

           if(data[i]==e)

               return true;

       return false;

   //查找某个元素并返回索引，不存在则返回-1

   public int find(int e){

               return i;

       return -1;

   //删除索引位置元素并返回被删元素值

   public int remove(int index){

       int tem=data[index];

       for(int i=index+1;i<size;i++)

           data[i-1]=data[i];

       size--;

       return tem;

   //删除指定数值的元素

   public void removeElement(int e){

       int index = find(e);

       if(index!=-1)

           remove(index);

   @Override

   public String toString(){

       StringBuilder sb = new StringBuilder();

       sb.append(String.format("Array: size=%d capacity=%d\n", size,data.length));

       sb.append("[");

           sb.append(data[i]);

           if(i!=size-1)

               sb.append(", ");

       sb.append("]");

       return sb.toString();

}

2.泛型化数组

public class Array<E> {

   private E[] data;

       //data=new E[capacity];这样子new不对

       data=(E[]) new Object[capacity];

       //data=new E[10];

       data= (E[]) new Object[10];

   public void addLast(E e){

   public void addFirst(E e){

   public void add(int index,E e){

   public E get(int index,E e){

   public void set(int index,E e){

   public boolean contains(E e){

           //if(data[i]==e)

           //==为引用比较

           //equals为值比较，对于对象来说，进行值比较

           if (data[i].equals(e))

   public int find(E e){

   public E remove(int index){

       E tem=data[index];

   public void removeElement(E e){

3.动态数组

  //当数组满时进行扩容

   private void resize(int newCapacity){

       E[] newData=(E[])new Object[newCapacity];

       for (int i=0;i<size;i++)

           newData[i]=data[i];

       data=newData;

        //当元素减少到一半时，进行缩容

       if (size== data.length/2)

           resize(data.length/2);

        //当数组满了，进行扩容

           resize(2*data.length);

           throw new IllegalArgumentException("error");

       //当数组满了，进行扩容

       //当元素减少到一半时，进行缩容

  //当数组满时进行扩容

均摊复杂度

resize()并不是每次add都会触发，可以将其均摊到add步骤上

复杂度震荡

当数组中的数据一直在data.length/2附近波动，会产生复杂度震荡，操作过于激进，可以使用相对lazy的策略

        //当元素减少到1/4时，进行缩容

       if (size== data.length/4 && data.length/2!=0)