Java如何自定义一个变长数组

这篇文章主要介绍“Java如何自定义一个变长数组”的相关知识,小编通过实际案例向大家展示操作过程,操作方法简单快捷,实用性强,希望这篇“Java如何自定义一个变长数组”文章能帮助大家解决问题。

思路分析

主要功能点:

  1. 新建时可以指定容量大小,不指定时使用默认容量大小。

  2. 向数组中追加新元素,当超过容量时应该自动扩容。

  3. 向数组中指定位置添加新元素,需要考虑指定的下标是否越界,同样也需要考虑扩容操作。

  4. 删除末尾的元素,需要考虑缩小容量。

  5. 删除指定位置元素,需要考虑指定的下标是否越界,同样也需要考虑缩小容量。

  6. 修改特定位置的元素,需要考虑指定的下标是否越界。

  7. 以时间复杂度为O ( 1 ) O(1)O(1)获取任意位置的元素,需要考虑指定的下标是否越界。

主要注意点:

  1. 扩容: 这里扩容2倍(ArrayList 是扩容 1.5 倍),扩容时新建一个2倍容量的新数组,然后将旧数组中的元素按顺序拷贝到新数组。

  2. 缩容: 当数组中的元素个数 <= 0.25 * 容量时,自动缩小容量为原来的一半,新建一个容量是原来容量一半的数组,然后将旧数组中的元素按顺序拷贝到新数组。(ArrayList缩小为和当前元素个数一样大)。

  3. 指定位置添加: 需要先将指定位置及后面所有的元素都向后移动一位,将指定位置空出来然后再插入。

  4. 指定位置删除: 先将制定位置删除,然后将后面的所有元素都向前移动一位。

  5. 容量大小: 需要指定容量的最大值,避免OOM的发生。最小值可以指定也可以不指定。

实现代码

/**
 * 变长数组
 * */
public class ResizeableArray<E> {

    private static final int MIN_CAPACITY = 10;

    private static final int MAX_CAPACITY = Integer.MAX_VALUE - 8;

    // 当前实际数据大小
    private int size = 0;

    // 实际存放元素的数组,容量为 elements.length
    private Object[] elements;

    public ResizeableArray(){
        this(MIN_CAPACITY);
    }

    public ResizeableArray(int initCapacity){
        if(initCapacity < MIN_CAPACITY){
            initCapacity = MIN_CAPACITY;
        }else if(initCapacity > MAX_CAPACITY){
            initCapacity = MAX_CAPACITY;
        }
        this.elements = new Object[initCapacity];
    }

    // 数组的特性,根据下标获取元素
    public E get(int index){
        this.checkIndex(index);
        return (E)elements[index];
    }

    // 添加一个元素到最后
    public void add(E element){
        if(size == elements.length){
            // 需要扩容
            this.expandCapacity();
        }
        elements[size++] = element;
    }

    // 添加一个元素到指定位置
    public void add(int index, E element){

        if(index == size){
            this.add(element);
            return;
        }
        this.checkIndex(index);
        if(size == elements.length){
            // 需要扩容
            this.expandCapacity();
        }
        // 需要先将index和之后的所有元素向后移动一位
        for(int i = size - 1; i >= index; i--){
            elements[i + 1] = elements[i];
        }
        elements[index] = element;
        size++;

    }

    // 设置下标为index的元素
    private void set(int index, E element){
        this.checkIndex(index);
        elements[index] = element;
    }

    /**
     * 删除下标为index的元素
     * 当 size <= 0.25 * capacity 的时候缩小容量
     */

    private void delete(int index){
        this.checkIndex(index);
        elements[index] = null;
        // 如果删除的不是最后一个元素,需要将后续元素往前移动一位
        if(index < size - 1){
            for(int i = index + 1; i < size; i++){
                elements[i - 1] = elements[i];
            }
        }
        size--;
        if(size <= 0.25 * elements.length){
            this.reduceCapacity();
        }
    }

    private void deleteLast(){
        this.delete(size - 1);
    }

    private void checkIndex(int index){
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException(String.format("Out of bounds at: %s, size is: %d", index, size));
        }
    }

    private void expandCapacity(){
        if(MAX_CAPACITY == elements.length){
            // 容量达到最大限制,无法扩容。
            throw new RuntimeException("The capacity has reached its maximum limit and cannot be expanded.");
        }
        int newCapacity = Math.min(elements.length << 1, MAX_CAPACITY);
        Object[] newElements = new Object[newCapacity];
        System.arraycopy(elements, 0, newElements, 0, size);
        elements = newElements;
    }

    private void reduceCapacity(){
        if(elements.length == MIN_CAPACITY){
            return;
        }
        int newCapacity = Math.max(elements.length >> 1, MIN_CAPACITY);
        Object[] newElements = new Object[newCapacity];
        System.arraycopy(elements, 0, newElements, 0, size);
        elements = newElements;
    }



    public static void main(String[] args){
        ResizeableArray<Integer> resizeableArray = new ResizeableArray<>();
        System.out.printf("初始化后,size为: %d \n", resizeableArray.size);
        System.out.printf("初始化后,capacity为: %d \n", resizeableArray.elements.length);
        System.out.println();

        for(int i = 0; i < 20; i++){
            resizeableArray.add(i);
        }

        System.out.printf("添加20个元素后,size为: %d \n", resizeableArray.size);
        System.out.printf("添加20个元素后,capacity为: %d \n", resizeableArray.elements.length);
        System.out.printf("添加20个元素后,第5个元素是: %d \n", resizeableArray.get(4));
        System.out.println();

        resizeableArray.delete(4);

        System.out.printf("删除第五个元素后,size为: %d \n", resizeableArray.size);
        System.out.printf("删除第五个元素后,capacity为: %d \n", resizeableArray.elements.length);
        System.out.printf("删除第五个元素后,第5个元素是: %d\n", resizeableArray.get(4));
        System.out.println();

        resizeableArray.add(4, 100);
        System.out.printf("在第五个位置插入元素后,size为: %d \n", resizeableArray.size);
        System.out.printf("在第五个位置插入元素后,capacity为: %d \n", resizeableArray.elements.length);
        System.out.printf("在第五个位置插入元素后,第5个元素是: %d\n", resizeableArray.get(4));
        System.out.println();

        for(int i = 0; i < 15; i++){
            resizeableArray.deleteLast();
        }
        System.out.printf("删除后面15个元素后,size为: %d \n", resizeableArray.size);
        System.out.printf("删除后面15个元素后,capacity为: %d \n", resizeableArray.elements.length);
        System.out.printf("删除后面15个元素后,第5个元素是: %d\n", resizeableArray.get(4));
        System.out.println();

        resizeableArray.set(4, 200);
        System.out.printf("修改第五个元素后,当前size为: %d \n", resizeableArray.size);
        System.out.printf("修改第五个元素后,capacity为: %d \n", resizeableArray.elements.length);
        System.out.printf("修改第五个元素后,第5个元素是: %d\n", resizeableArray.get(4));

    }
}

测试结果

由执行结果可知:

  • 初始化后默认容量为10

  • 添加元素超过10个后会自动扩容。

  • 删除一个元素后,size会减1,后面元素会自动向前移动一位。

  • 插入一个新元素后,size会加1,后续元素后移一位。

  • 删除到只有0.25 * 容量个元素后,会自动缩小容量。

Java如何自定义一个变长数组  java 第1张

关于“Java如何自定义一个变长数组”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识,可以关注蜗牛博客行业资讯频道,小编每天都会为大家更新不同的知识点。

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:niceseo99@gmail.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

评论

有免费节点资源,我们会通知你!加入纸飞机订阅群

×
天气预报查看日历分享网页手机扫码留言评论电报频道链接