一文带你了解动态数组方法实现

作者：xiaoyu

2022 年 3 月 10 日
本文字数：3771 字
阅读完需：约 12 分钟

数组（Array）

线性表

数组的特点

数组是一种顺序存储的线性表，数组内所有元素的内存地址都是连续的，
数组的长度一旦确定则不可更改
数组只能存储同一类型的数据
数组提供角标的方式访问元素

package array;
/** * @program: data-structure * @author:  * @created: 2021/11/16 * 动态数组源码解析 */public class ArrayList<E> {    //元素的数量    private int size;
    //所有的元素    private E[] elements;
    //初始容量    private static final int DEFAULT_CAPACITY = 10;
    //查找不到元素就-1    private static final int ELEMENT_NOT_FOUND = -1;
    // 元素的数量     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();}

复制代码

数组的缺点
数组一般都是都无法动态修改容量，只有在初始化数组的时候固定好数组长度。
实际应用中，数据的容量都是动态改变的。

动态数组（Dynamic Array）

概念

动态数组是指在声明时没有确定数组大小的数组，可以根据用户需求可以自动增加或者减少数组空间，有效的利用空间。

接口设计

创建ArrayList类，创建size属性来管理数组中元素的个数，创建elements属性来管理存取的数据。
可以对动态数组进行增删改查操作。

package array;
/** * @program: data-structure * @author:  * @created: 2021/11/16 * 动态数组源码解析 */public class ArrayList<E> {    //元素的数量    private int size;
    //所有的元素    private E[] elements;
    //初始容量    private static final int DEFAULT_CAPACITY = 10;
    //查找不到元素就-1    private static final int ELEMENT_NOT_FOUND = -1;
    // 元素的数量     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_FOUND = -1;
    /**     * 有参构造     *     * @param capacity     */    public ArrayList(int capacity) {        //容量小于10一律扩充为10，三元表达式        capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;        elements = (E[]) new Object[capacity];    }
    /**     * 无参构造，默认创建长度为10的数组     */    public ArrayList() {        this(DEFAULT_CAPACITY);    }}

复制代码

查看数组元素数量

size 的值，即为元素的数量。

public int size() {    return size;}

复制代码

数组是否为空

size 为空，则表示数组为空

public boolean isEmpty() {    return size == 0;}

复制代码

数组是否包含某个元素

通过判断索引(indexOf)是否等于ELEMENT_ON_FOUND即可。

public boolean contains(E element) {    return indexOf(element) != ELEMENT_NOT_FOUND;}

复制代码

根据索引获取对应位置的元素

通过数组下标进行查询

public E get(int index) {    return elements[index];}

复制代码

根据索引和元素替换对应的老元素

先获取原来的元素，然后把新增的元素替换到原来的元素位置，并且返回原来 index 位置的元素

public E set(int index, E element) {    E old = elements[index];    elements[index] = element;    return old;}

复制代码

添加元素

添加元素就是将指定位置之后的元素统一后移一位，并将指定元素插入到指定位置

数组越界

添加元素的时候索引的大小有限制，不能小于 0, 也不能大于 size。

private void rangeCheckForAdd(int index) {    if (index < 0 || index > size) {        outOfBounds(index);    }}

复制代码

数组动态扩容（核心所在）

由于数组长度是默认长度为 10，那么当数组存满元素，就需要对该数组进行扩容操作。
因为数组是无法动态增加的，就需要创建一个新的数组，并且数组容量一般都是原数组容量的 1.5 呗，然后将原数组的元素循环放入新数组中，这就是动态扩容。

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;    System.out.println("size=" + oldCapacity + ", 扩容到了" + newCapacity);}

复制代码

数组添加实现

数组添加之前需要先验证索引是否越界
然后判断当前数组是否需要扩容操作

public void add(int index, E element) {    //检查下标是否越界    rangeCheckForAdd(index);    // 判断数组是否需要越界    ensureCapacity(size + 1);    // 先从后往前开始, 将每个元素往后移一位, 然后再赋值    for (int i = size; i > index; i--) {        elements[i] = elements[i - 1];    }    // 复制    elements[index] = element;    size++;}

复制代码

删除元素

删除数组元素就是删除指定位置的元素，并将指定位置之后的元素统一前移一位

数组越界

移除元素的时候索引的大小有限制，不能小于 0, 也不能大于等于 size。

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

复制代码

动态缩容

当数组中的元素删除后，可能会导致数组的剩余空间很大，会造成内存的浪费
当删除数组中的元素，需要先判断是否打到缩容的条件，如果达不到，就不进行缩容处理
动态缩容实现方法类似于扩容，当数组中容量小于某个值时，创建新的数组，然后将原有数组中的元素存入新数组即可。

private void trimToSize() {    // 获取当前数组的容量    int oldCapacity = elements.length;    //设置新数组的容量为原数组容量的0.5倍    int newCapacity = oldCapacity >> 1;    // 当size大于等于容量的一半, 或则容量已经小于默认容量(10)时, 直接返回    if (size >= (newCapacity) || oldCapacity <= DEFAULT_CAPACITY) {        return;    }    //根据新的容量创建新数组    E[] newElements = (E[]) new Object[newCapacity];    for (int i = 0; i < size; i++) {        // 拷贝原数组元素到新数组        newElements[i] = elements[i];    }    elements = newElements;    System.out.println("size=" + oldCapacity + ", 缩容到" + newCapacity);
}

复制代码

数组的删除实现

数组删除之前需要先验证索引是否越界
然后判断当前数组是否需要缩容操作

public E remove(int index) {    rangeCheck(index);    trimToSize();    E old = elements[index];    for (int i = index; i < size; i++) {        elements[i] = elements[i + 1];    }    elements[--size] = null;    return old;}

复制代码

查询元素的对应位置

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

public int indexOf(E element) {    if (null == element) {        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 ELEMENT_NOT_FOUND;}

复制代码

发布于: 刚刚阅读数: 2

原文链接:【http://xie.infoq.cn/article/744705d5a1c21bba045009528】。文章转载请联系作者。

xiaoyu

关注

还未添加个人签名 2022.03.10 加入

还未添加个人简介

发布

暂无评论

创作场景

一文带你了解动态数组方法实现

数组（Array）

线性表

数组的特点

动态数组（Dynamic Array）

概念

接口设计

动态数组实现

构造方法

查看数组元素数量

数组是否为空

数组是否包含某个元素

根据索引获取对应位置的元素

根据索引和元素替换对应的老元素

添加元素

数组越界

数组动态扩容（核心所在）

数组添加实现

删除元素

数组越界

动态缩容

数组的删除实现

查询元素的对应位置

xiaoyu

评论