最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

【环球时快讯】Java实现动态数组(数据结构与算法)

来源：博客园

前言:为什么需要动态数组？

1，我们之前用的数组最大的问题就在于数组长度定长，一旦一个数组在定义时确定长度之后，使用过程中无法修改这个长度。

2，Java中提供的数组都是静态数组int[] char[] long[](定义之后没法改变长度) 所以需要我们自己定义一个类，拓展基础数组的功能。


(资料图片仅供参考)

一、什么是动态数组

Java中提供的数组都是静态数组，即在一个数组定义时确定长度后，使用过程中无法修改此长度。 动态数组就是在普通数组上，增加了一个可以根据元素的个数动态调整数组大小的功能。

二、动态数组的实现

创建一个MyArrayList类 为可变类型Object参数 size为元素的数量 elements为所有的元素 DEFAULT_CAPACITY为默认组的数量 并且初始化构造方法

package com.szx;@SuppressWarnings("unchecked")public class MyArrayList {    /**     * 元素的数量     */    private int size;    /**     *  所有的元素     */    private E[] elements;    /**     * 默认数组数量     */    private static final int DEFAULT_CAPACITY=2;    /**     * 返回-1索引不存在     */    private static final int ELEMENT_NOT_FOUND=-1;                public MyArrayList(int capaticy){        //如果新的数组数量小于默认的数组 那么就用新的 ,默认为2         capaticy = (capaticy
接口的设计
◼ 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(); // 清除所有元素
1添加元素-add(E element)
0　　 1　2  3  4  5  6
当size等于0时
element
0     1    2    3    4      5      6
1020304050element
当size=5时
核心代码:elements[size] = elemenet;
size++;
package com.szx;@SuppressWarnings("unchecked")public class MyArrayList {    /**     * 元素的数量     */    private int size;    /**     *  所有的元素     */    private E[] elements;    /**     * 默认数组数量     */    private static final int DEFAULT_CAPACITY=2;    /**     * 返回-1索引不存在     */    private static final int ELEMENT_NOT_FOUND=-1;                public MyArrayList(int capaticy){        //如果新的数组数量小于默认的数组 那么就用新的 ,默认为2         capaticy = (capaticysize){            throw new IndexOutOfBoundsException("Index:"+index+",Size:"+size);        }        //ensureCapacity(size+1);        for (int i = size-1; i >=index; i--) {            elements[i+1] = elements[i];        }        //原来的位置存放新添加的元素        elements[index] = element;        size++;    }    @Override    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(elements[i]);                                }                string.append("]");        return string.toString();    }
测试结果:
2:数组动态扩容 经过上面测试.我们会发现数组可以正常添加但默认数量是2 超过两个就会出事:
实现动态扩容:ensureCapacity方法,在添加元素前进行调用
/**     * 往index位置添加元素     * @param index     * @param element     */    public void add(int index,E element){        if(index <0||index>size){            throw new IndexOutOfBoundsException("Index:"+index+",Size:"+size);        }        ensureCapacity(size+1);        for (int i = size-1; i >=index; i--) {            elements[i+1] = elements[i];        }        //原来的位置存放新添加的元素        elements[index] = element;        size++;    }/**     * 保证要有capacity的容量     * @param capacity     */    private void ensureCapacity(int capacity){        int oldCpacity = elements.length;        if(oldCpacity >=capacity){            return;        }        //int newCapacity = oldCpacity +oldCpacity*1.5;        //新的容量为旧容量的1.5倍,当然也可以自己调整,        //使用位运算提高效率        int newCapacity = oldCpacity +(oldCpacity>>1);        E[] newElements = (E[]) new Object[newCapacity];        for (int i = 0; i < size; i++) {            newElements[i] = elements[i];        }        //替换之前的数组        elements = newElements;        System.out.println(oldCpacity + "扩容为:"+newCapacity);                    }
测试结果:
3:删除元素-remove(int index)
/**     * 删除index位置对应的元素     * @param index     * @return     */    public E remove(int index){        if(index <0||index>=size){            throw new IndexOutOfBoundsException("Index:"+index+",Size:"+size);        }        E old = elements[index];        for (int i = index+1; i <=size-1; i++) {            elements[i-1] = elements[i];        }        size--;        elements[size] = null;        return old;    }
4:根据idex查询对应的元素
/**     * 返回index位置对应的元素     * @param index     * @return     */    public E get(int index){        if(index <0||index>=size){            System.out.println("下标越界,该数组中不存在");            throw new IndexOutOfBoundsException("Index:"+index+",Size:"+size);        }        return elements[index];    }
5:设置index的元素(元素的修改)
/**     * 设置index位置的元素     * @param index     * @param element     * @return     */    public E set(int index,E element){        if(index <0||index>=size){            throw new IndexOutOfBoundsException("Index:"+index+",Size:"+size);        }        E old = elements[index];        elements[index] = element;        return old;    }
进行测试:
完整代码:
package com.szx;@SuppressWarnings("unchecked")public class MyArrayList {    /**     * 元素的数量     */    private int size;    /**     *  所有的元素     */    private E[] elements;    /**     * 默认数组数量     */    private static final int DEFAULT_CAPACITY=2;    /**     * 返回-1索引不存在     */    private static final int ELEMENT_NOT_FOUND=-1;                public MyArrayList(int capaticy){        //如果新的数组数量小于默认的数组 那么就用新的 ,默认为2         capaticy = (capaticysize){            throw new IndexOutOfBoundsException("Index:"+index+",Size:"+size);        }        ensureCapacity(size+1);        for (int i = size-1; i >=index; i--) {            elements[i+1] = elements[i];        }        //原来的位置存放新添加的元素        elements[index] = element;        size++;    }        /**     * 清除所有元素     */    public void clear(){//        if(size<=100){//            size = 0;//        }else{//            //            elements =null;//        }        for (int i = 0; i < size; i++) {            elements[i] = null;        }        size = 0;    }        /**     * 是否为空     * @return     */    public boolean isEmpty(){//        if(size==0){//            return true;//        }else{//            return false;//        }//                return size==0;    }    /**     * 是否包含某个元素     * @param element     * @return     */    public boolean contains(E element){                return  indexOf(element)!=ELEMENT_NOT_FOUND;    }    /**     * 返回index位置对应的元素     * @param index     * @return     */    public E get(int index){        if(index <0||index>=size){            System.out.println("下标越界,该数组中不存在");            throw new IndexOutOfBoundsException("Index:"+index+",Size:"+size);        }        return elements[index];    }    /**     * 设置index位置的元素     * @param index     * @param element     * @return     */    public E set(int index,E element){        if(index <0||index>=size){            throw new IndexOutOfBoundsException("Index:"+index+",Size:"+size);        }        E old = elements[index];        elements[index] = element;        return old;    }    /**     * 删除index位置对应的元素     * @param index     * @return     */    public E remove(int index){        if(index <0||index>=size){            throw new IndexOutOfBoundsException("Index:"+index+",Size:"+size);        }        E old = elements[index];        for (int i = index+1; i <=size-1; i++) {            elements[i-1] = elements[i];        }        size--;        elements[size] = null;        return old;    }    /**     * 查看元素的位置     * @param element     * @return     */    public int indexOf(E element){        if(element ==null){            for (int i = 0; i < size; i++) {                if(elements[i]== null){                    return i;                }            }        }else{            for (int i = 0; i < size; i++) {                if(element.equals(elements[i])){                    return i;                }            }                    }                    return -1;    }    @Override    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(elements[i]);                                }                string.append("]");        return string.toString();    }    /**     * 保证要有capacity的容量     * @param capacity     */    private void ensureCapacity(int capacity){        int oldCpacity = elements.length;        if(oldCpacity >=capacity){            return;        }        //int newCapacity = oldCpacity +oldCpacity*1.5;        //新的容量为旧容量的1.5倍,当然也可以自己调整,        //使用位运算提高效率        int newCapacity = oldCpacity +(oldCpacity>>1);        E[] newElements = (E[]) new Object[newCapacity];        for (int i = 0; i < size; i++) {            newElements[i] = elements[i];        }        //替换之前的数组        elements = newElements;        System.out.println(oldCpacity + "扩容为:"+newCapacity);                    }}
测试代码:
package com.szx;public class Main {        public static void main(String[] args) {                    MyArrayList list1 = new MyArrayList();            list1.add(11);            list1.add(22);            list1.add(33);                list1.add(44);                System.out.println(list1.toString());                            list1.remove(2);            System.out.println("删除后");            System.out.println(list1.toString());            System.out.println("修改:");            list1.set(0,66);            System.out.println(list1.toString());        }}
                 

关键词：         
       添加元素 
              
       动态数组 
              
       是否为空