dynamic-array

Posted on 2020-04-26 Edited on 2025-02-24 Views:

动态数组

数组是一种顺序储存的线性表,所有元素的内存地址是连续.

1 2	int[] array = new int[]{20, 30, 40} //向内存申请了12个字节地址

在这里插入图片描述

在很多编程语言中，数组有个致命的缺点， 无法动态修改容量。
实际开发中我们希望数组的容量是动态变化的。

动态数组

创建ArrayList类,创建size属性来管理数组中元素的个数,创建element属性来管理存取的数据.

可以对动态数组进行增删改查操作.

public class ArrayList<E> {
    private int size;
    private E[] elements;

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

动态数组的实现

构造方法

如果构建的数组空间小于默认空间,则会以默认空间创建数组.

public class ArrayList<E> {
    /**
     * 元素的数量
     */
    private int size;

    /**
     * 所有元素
     */
    private E[] elements;

    /**
     * 数组的默认容量
     */
    private static final int DEFAULT_CAPACITY = 10;

	/**
     * 找不到元素返回-1
     */
    private static final int ELEMENT_NOT_FOUNT = -1;

    public ArrayList() {
        // 默认容量
        //elements = new int[DEFAULT_CAPACITY];
        this(DEFAULT_CAPACITY); // 调用下面的构造器
    }

    public ArrayList(int capacity) {
        // 设置默认容量为 10
        capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;

        // 因为泛型(所以传一个Object数组,然后通过强转)
        elements = (E[]) new Object[capacity];
    }
}

添加元素

数组添加元素分为在最后一个元素的后面添加新元素和将元素插入到某个位置（非最后面）两种情况。
第一种情况，这个新元素需要添加到的索引等于当前数组元素的个数，在ArrayList中size属性就是当前数组元素的个数，所以就是将新元素添加到数组的size位置上，然后size加1。

public void add(int index, E element) {
    elements[index] = element;
    size++;
}

如果是第二种情况，只需要将插入位置后面的元素向后移动即可。
注意：需要从后向前移动元素，如果从前向后移动元素，那么会进行元素覆盖, 最后出错。

数组越界

添加元素,还要注意传入的索引不能越界,即不能小于0,也不能大于size.

/**
 * 根据index插入元素时,判断index是否有效
 *
 * @param index
 */
private void rangeCheckForAdd(int index) {
    if (index < 0 || index > size) {
        indexOutOfBounds(index);
    }
}

/**
 * 封装数组越界异常
 *
 * @param index
 */
private void indexOutOfBounds(int index) {
    throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}

数组扩容

动态扩容思路:

通过默认容量创建的数组,是在堆空间中随机生成的地址;如此一来再申请空间拼接到该数组后,这种方式不可能实现;
我们只能再创建一个大容量的数组,然后将之前数组中的元素移动到这个数组中;然后将引用指向新数组即可!
由于数组elements最大的容量只有10，所以当数组存满元素时，就需要对数组进行扩容。
因为数组是无法动态扩容的，所以需要创建一个新的数组，这个数组的容量要比之前数组的容量大。
然后在将原数组中的元素存放到新数组中，这样就实现了数组的扩容。

该方法确保默认容量为多少,为了验证是否超过给定的默认容量,然后进行判断是否要扩容;这里size+1为数组当前数量+1, 因为每次add都会增加一个容量。

/**
 * 确保至少要有capacity个容量
 *
 * @param capacity
 */
private void ensureCapacity(int capacity) {

    // 获取数组当前容量
    int oldCapacity = elements.length;
    // 判断是否要扩容
    if (oldCapacity >= capacity)
        return; // 此时不扩容

    // 这种方式是扩容1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);

    E[] newElements = (E[]) new Object[newCapacity];
    // 将原来数组中的元素移动到新数组中
    for (int i = 0; i < size; i++) {
        newElements[i] = elements[i];
    }
    // 将数组引用指向新数组
    elements = newElements;
}

实现add函数，需要在添加新元素之前，判断数组越界和扩容。

/**
 * 在index位置插入一个元素
 *
 * @param index
 * @param element
 */
public void add(int index, E element) {
    // 在添加元素的时候,判断index是否有效
    rangeCheckForAdd(index);

    ensureCapacity(size + 1);

    // 注意: 插入元素后,元素是从后开始往后挪
    for (int i = size - 1; i >= index; i--) {
        elements[i + 1] = elements[i];
    }
    elements[index] = element;
    size++;
}

最终在最后一个元素的后面添加新元素，即添加元素到尾部的实现方式如下

/**
 * 添加元素到尾部
 *
 * @param element
 */
public void add(E element) {
    // elements[size++] = element;
    // 传入数组数量(相当于在最后插入元素)
    add(size, element);
}

删除元素

删除元素，实际上就是移除指定位置的元素，并将后面的元素向前移动。
如下图，当删除索引为3的元素时，只需要将后面的元素向前移动，然后在去掉最后一个元素，size减1即可。

数组越界

删除元素时传入的索引不能越界, 即不能小于0, 也不能大于等于size所以我们在删除元素之前需要先进行索引检查。

private void indexOutOfBounds(int index) {
    throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
	
private void rangeCheck(int index) {
    if (index < 0 || index >= size) {
        outOfBounds(index);
    }
}

数组缩容

当数组中的元素删除后，数组剩余的空间可能会很大，这样就会造成内存的浪费。
所以当数组中元素删除后，我们需要对数组进行缩容。
实现方法类似于扩容，当数组中容量小于某个值时，创建新的数组，然后将原有数组中的元素存入新数组即可。

/**
 * 数组缩容
 */
public void trim() {
    // 获取当前数组的容量
    int capacity = elements.length;
    // 当size大于等于容量的一半, 或则容量已经小于默认容量(10)时, 直接返回
    if (size >= capacity >> 1 || capacity < CAPACITY_DEFAULT) return;
    // 计算新的容量 = 原有容量的一半
    int newCapacity = capacity >> 1;
    // 创建新数组
    E[] newElements = (E[]) new Object[newCapacity];
    // 将原数组元素存入新数组
    for (int i = 0; i < size; i++) {
    	newElements[i] = elements[i];
    }
    // 引用新数组
    elements = newElements;
}

最终, remove方法实现如下

/**
 * 删除index位置的元素
 *
 * @param index
 * @return 被删除的元素
 */
public E remove(int index) {
    rangeCheck(index);
    E delEle = elements[index];

    // 当删除一个元素时,需要挪动后面元素的范围
    for (int i = index + 1; i <= size - 1; i++) {
        elements[i - 1] = elements[i];
    }
    size--;
    // 同clear的细节,当从后往前以后时,最后一个的地址需要释放
    elements[size] = null;
    // 判断数组是否需要缩容
    trim();
    return delEle;
}

/**
 * 删除传入的元素
 * @param element
 */
public void remove(E element){
    remove(indexOf(element));
}

清空数组

清空数组时，需要将所有的元素置为null，只有这样才能真正的释放对象，然后size置为0。

/**
 * 清除所有元素
 */
public void clear() {
    for (int i = 0; i < size; i++) {
        elements[i] = null;
    }
    size = 0;
}

修改元素

修改元素时，只需要将原有位置的元素替换掉即可，同样需要注意一下索引是否越界。

/**
 * 设置index位置的元素
 *
 * @param index
 * @param element
 * @return 原来的元素
 */
public E set(int index, E element) {
    rangeCheck(index);

    E oldEle = elements[index];
    elements[index] = element;
    return oldEle;
}

查询元素

查询元素，只需要将指定索引的元素返回，注意索引是否越界即可。

/**
 * 获取index位置的元素
 *
 * @param index
 * @return
 */
public E get(int index) {
    // 约束Index
    rangeCheck(index);
    return elements[index];
}

查看元素位置

可以通过循环, 查找元素在数组中的位置。
注意：假如数组中可以存储null，而null是不能调用equals方法的，所以需要对传入的元素进行判断，如果查找的元素是null，需要单独处理。
当元素存在时返回索引，否则返回变量ELEMENT_ON_FOUND的值。

/**
 * 查看元素的索引
 *
 * @param element
 * @return
 */
public int indexOf(E element) {
    if (element == null) {
        // 循环判断如果element为null,直接返回null的索引
        for (int i = 0; i < size; i++) {
            if (elements[i] == null)
                return i;
        }
    } else {
        for (int i = 0; i < size; i++) {
            // 因为element肯定不为null了,所以放在前面;避免空指针异常
            if (element.equals(elements[i]))
                return i;
        }
    }
    return ELEMENT_NOT_FOUNT;
}

是否包含某元素

只需通过判断索引是否等于ELEMENT_ON_FOUND即可。

/**
 * 是否包含某个元素
 *
 * @param element
 * @return
 */
public boolean contains(E element) {
    // 如果element元素可以找到
    return indexOf(element) != ELEMENT_NOT_FOUNT;
}

元素的数量

size的值，即为元素的数量

/**
 * 元素的数量
 *
 * @return
 */
public int size() {
    return size;
}

数组是否为空

通过判断size的值是否为0即可

/**
 * 是否为空
 *
 * @return
 */
public boolean inEmpty() {
    return size == 0;
}

动态数组打印

可以重写toString方法, 来打印ArrayList中的元素。

@Override
public String toString() {
    // 打印格式: size=3, [10, 20, 30]
    // 使用StringBuilder 效率高一些
    StringBuilder string = new StringBuilder();
    string.append("size=").append(size).append(", [");
    for (int i = 0; i < size; i++) {
        string.append(elements[i]);
        if (i != size - 1) {
            string.append(", ");
        }
    }
    string.append("]");
    return string.toString();
}

这样就实现了动态数组的基本操作。

ArrayList能否进一步优化？

在ArrayList中，如果要删除索引0位置的元素，则需要将索引0之后的元素全部往前移一位。
如果要在索引0位置添加元素，也需要将索引0及之后的元素全部往后移一位。

在ArrayList中增加一个记录首元素位置的属性。
删除索引0位置的元素，我们只需要将first属性改为1。
-在索引0位置添加元素，则只需要将first属性改为0。

如果继续往前插入元素，则将插入的元素存放在索引8这个位置，并将first改为8。
当要获取索引8下一个元素时，对索引取模，则拿到索引0位置的元素。

如果插入元素，则可选择挪动前半段数据或后半段数据。
在索引2处插入元素99，可以选择将元素22，33左移，然后插入99即可。
扩容和缩容同样可以优化。

重点总结

动态扩容思路

通过默认容量创建的数组,是在堆空间中随机生成的地址;如此一来
再申请空间拼接到该数组后,这种方式不可能实现;
我们只能再创建一个大容量的数组,然后将之前数组中的元素移动到
这个数组中;然后将引用指向新数组即可!

如何确保容量是否越界

该方法确保默认容量为多少, 为了验证是否超过给定的默认容量,然后进行判断是否要扩容; 这里size+1为数组当前数量+1, 因为每次add都会增加一个容量。

1	ensureCapacity(size + 1);

增加泛型

使用泛型, 使动态数组可以添加任何类型的数据。

1	elements = (E[]) new Object[capacity];

clear方法的过渡细节

因为之前存储的都是int数据, 直接设置size=0时, 开辟的存储int类型的空间就不能被访问, 当add后, 就可以访问后面的空间, 所以此时的空间可以重复利用;

当使用泛型后, 动态数组中存储的都是对象类型, 实际存储的都是对象的地址, 每一个对象的地址又有一块空间引用着; 此时如果仍设置 size=0, 当clear后,开辟的存储空间中的地址没有被销毁, 地址仍被对象空间引用着; 这样以来存储对象的空间就不会被释放; 但是存储地址的数组可以重复利用; 所以要将地址数组都置为null, 然后size=0, 这样以来,引用该地址的对象空间也就释放了!

remove、indexOf的细节

remove最后一个地址也要情况, 同clear细节
在indexOf方法中,不用==比较, 因为比较的是地址值,一般重写equals方法自己定义比较内容即可;
null值处理: 当往数组传null的时候,indexOf的比较处理: 如果那null.equals来比较会出现空指针异常;