数据结构-数组实现

╰半夏微凉° 2022-03-28 12:08 228阅读 0赞

public class Array<E> {
    
        private E[] data;
    
        private  int size; //数组元素个数
    
        private static  final  int DEFAULT_CAPACITY=10;//默认容量
    
        /**
         * 自定义数组长度
         * @param Capacity
         */
        public  Array(int Capacity){
           setInitCapacity(Capacity);
        }
    
        /**
         * 给数组提供一个默认大小
         */
        public Array(){
            setInitCapacity(DEFAULT_CAPACITY);
        }
    
        /**
         * 获取数组元素个数
         * @return
         */
        public int getSize(){
            return size;
        }
    
        /**
         * 设置初始大小
         * @param capacity
         */
        private void  setInitCapacity(int capacity){
            data= (E[]) new Object[capacity];
        }
    
        /**
         * 获取数组容量
         * @return
         */
        public int getCapacity(){
            return data.length;
        }
    
        /**
         * 监测数组是否为空
         * @return
         */
        public boolean isEmpty(){
            return size==0;
        }
    
        /**
         * 在指定index添加元素
         * @param index
         * @param e
         */
        public  void add(int index,E e){
             rangeCheck(index);//检查index是否越界
             ensureCapacity(size+1);
            //方式一
            for (int i=size-1;i>=index;i--){
                 data[i+1]=data[i];
            }
            //System.arraycopy(data,index,data,index+1,size-index); 方式二
            data[index]=e;
            size++;
        }
    
         /**
         * 检查index是否越界
         * @param index
         */
        public void  rangeCheck(int index){
            if(index<0 || index>size){
                throw new IndexOutOfBoundsException("index:"+index);
            }
        }
    
    
    
        /**
         * 添加元素
         * @param e
         */
        public void add(E e){
            add(size,e);
        }
    
        /**
         * 在数组头部添加元素
         * @param e
         */
        public void addFrist(E e){
            add(0,e);
        }
    
        /**
         * 删除指定下标元素
         * @param index
         * @return
         */
        public E remove(int index){//1
            rangeCheck(index);
            //记录删除的元素
            E result=data[index];
            //方式一
            for(int i=index+1;i<size;i++){
                data[i-1]=data[i];
            }
            //方式二
            //System.arraycopy(data,index+1,data,index,size-index-1);
             size--;
             if(size==data.length>>1){
                 resize(data.length>>1);
             }
           
            return result;
        }
    
        public void removeFrist(){
            remove(0);
        }
    
        public void removeLast(){
            remove(size-1);
        }
    
        public void removeElement(E e){
            int index = find(e);//查找指定元素
            remove(index);//删除元素
        }
    
        /**
         * 修改元素
         * @param index
         * @param e
         * @return
         */
        public E set(int index,E e){
            rangeCheck(index);
            E oldValue=data[index];
            data[index]=e;
            return oldValue;
        }
    
        /**
         * 根据下标得到对应元素
         * @param index
         * @return
         */
        public  E get(int index){
            rangeCheck(index);
            return data[index];
        }
    
        /**
         * 获取第一个元素
         *
         *
         */
        public E getFrist(){
            return get(0);
        }
    
        /**
         * 获取最后一个元素
         *
         *
         */
        public E getLast(){
            return get(size-1);
        }
    
        /**
         * 是否包含
         * @param e
         * @return
         */
        public boolean contains(E e){
            return find(e)>=0;
        }
        /**
         * 得到指定元素的下标
         */
        public int find(E index){
            for (int i = 0; i < size; i++) {
                if(data[i].equals(index)){
                    return i;
                }
            }
            return -1;
        }
    
        /**
         *
         * @return
         */
        @Override
        public String toString() {
            StringBuilder sb=new StringBuilder();
            sb.append("Array:size="+size+",capacity="+data.length+"\n");
            sb.append("[");
            for (int i = 0; i < size; i++) {
                sb.append(data[i]);
                if(i!=size-1){
                    sb.append(",");
                }
            }
            sb.append("]");
            return sb.toString();
        }
    
        /**
         * 数组扩容操作
         * @param minCapacity
         */
        private  void  resize(int minCapacity){
            E [] newData=(E[]) new Object[minCapacity];
            for (int i = 0; i < size; i++) {
                newData[i]=data[i];
            }
            data=newData;
        }
    
        /**
         * 合并数组
         * @param array
         * @return
         */
        public boolean addAll(Array<E> array){
            E[] objects = (E[]) array.toArray();
            int numNew = objects.length;
    
            ensureCapacity(numNew+size);
            //第一种方式
            for (int i=0;i<numNew;i++){
                data[size++]=objects[i];
            }
            //第二种方式
            //System.arraycopy(objects, 0, data, size, numNew);
            return numNew!=0;
        }
    
        /**
         * 删除全部
         * @param array
         * @return
         */
        public  boolean removeAll(Array<E> array){
            int count=size;
            if(array!=null){
                for (int i =0; i <size; i++) {
                    data[i]=null;
                    count--;
                }
                size=count;
                //把数组设置为默认长度
                setInitCapacity(DEFAULT_CAPACITY);
                return true;
            }
            return false;
        }
    
        /**
         * 监测是否满足扩容操作
         * @param minCapacity
         */
        private  void ensureCapacity(int minCapacity){
            if(minCapacity-data.length>0){
                addresize(minCapacity);
            }
    
        }
    
        /**
         * 添加操作时扩容
         * @param minCapacity
         */
        private  void addresize(int minCapacity){
            int oldCapacity=data.length;
            int newCapatity= oldCapacity << 1;
            if(newCapatity-minCapacity<0){
                newCapatity=minCapacity;
            }
            resize(newCapatity);//数组扩容
        }
    
        /**
         * 集合转数组
         * @return
         */
        public Object[] toArray(){
            return Arrays.copyOf(data,size);
        }