【数据结构与算法】1、学习动态数组数据结构（基本模拟实现 Java 的 ArrayList 实现增删改查）-阿里云开发者社区

一、什么是数据结构

(1) 概念

🍃 数据结构是计算机存储、组织数据的方式

(2) 分类

🎉 线性结构

线性表（数组、链表、栈、队列、哈希表）

🎉 树形结构

二叉树
AVL 树
红黑树
B 树
堆
Trie
哈夫曼树
并查集

🎉 图形结构

邻接矩阵
邻接表

二、线性表

🎁 线性表是具有 n 个相同类型元素的有限序列（n >= 0）

a1 是首节点（首元素）， an 是尾结点（尾元素）
a1 是 a2 的前驱
a2 是 a1 的后继

常见的线性表有：

🎗️ 数组

🎗️ 链表

🎗️ 栈

🎗️ 队列

🎗️ 哈希表（散列表）

三、数组（Array）

(1) 数组的底层结构

🎁 数组是一种顺序存储的线性表，全部元素的内存地址是连续的

// 【new】向堆空间申请一段存储空间
int[] array = new int[]{11, 22, 33};

(2) 数组缺点

👓数组有个致命的缺点：无法动态修改容量
👓数组创建完毕后，能够存储的数据就固定了
👓数组操纵元素的方式不够面向对象

🎐 自己实现动态数组，弥补数组的缺点

四、动态数组（Dynamic Array）接口设计

public interface List<E> {
    /**
     * 元素的数量
     */
    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();
}

五、动态数组的设计和基本代码实现

(1) 成员变量

Java 中的成员变量会自动初始化，比如：

🎑 int 类型自动初始化为 0

🎑 对象类型自动初始化为 null

🎑 size 记录动态数组中元素的个数

🎑 elements 用于实际存储数据

🎑 动态数组的底层是数组

(2) 代码

/**
 * 只支持存储 int 类型数据的动态数组
 */
public class ArrayListInt {
    private int size;
    private int[] elements;
    public static final int DEFAULT_CAPACITY = 10;
    public static final int ELEMENT_NOT_FOUND = -1;
    public ArrayListInt() {
        this(DEFAULT_CAPACITY);
    }
    public ArrayListInt(int capacity) {
        capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
        elements = new int[capacity];
    }
    public int size() {
        return size;
    }
    public boolean isEmpty() {
        return size == 0;
    }
    /**
     * 获取 index 索引处的元素
     */
    public int get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("size: " + size + ", " + "index: " + index);
        }
        return elements[index];
    }
    /**
     * 设置 index 位置的元素
     *
     * @param index   下标
     * @param element 要设置的元素
     * @return 原来的元素ֵ
     */
    public int set(int index, int element) {
        // 获取 index 位置的元素
        int old = get(index);
        elements[index] = element;
        return old;
    }
    /**
     * 返回元素的索引
     */
    public int indexOf(int element) {
        // 如果数组为空, 直接找不到
        if (isEmpty()) return ELEMENT_NOT_FOUND;
        for (int i = 0; i < size; i++) {
            if (element == elements[i]) return i;
        }
        return ELEMENT_NOT_FOUND;
    }
    /**
     * 检查数组中是否包含 element 元素
     */
    public boolean contains(int element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }
    /**
     * 清除全部元素
     * 只要【size = 0】就无法获取到数组中的任何元素了
     */
    public void clear() {
        size = 0;
    }
}

① get ()

🎈 该方法的作用：获取 index 索引处的元素

🎈 数组可通过索引获取到元素

🎈 要做参数（index）校验

② indexOf ()

🎈 返回某个元素的索引

🎈 遍历每个下标的元素，拿数组中的每个元素和参数元素进行比较

③ clear ()

🎈 清除全部元素（清空数组）

🎈 在当前的代码中，只要【size = 0】就无法获取到数组中的任何元素了（就可以理解为清空了数组）

六、add 方法和扩容

🎈 add(int element)：往数组的尾部添加元素 element

🎈 add(int index, int element)：往数组的 index 索引位置添加元素 element

(1) add (int element)

🕰️ 每次往尾部添加元素的时候，是往数组的索引为 size 位置添加元素

public class ArrayListInt {
    /**
     * 往数组尾部添加元素
     */
    public void add(int element) {
        // TODO 扩容检测
        elements[size++] = element;
    }
}

(2) 打印动态数组中的元素

☆写法1：

public class ArrayListInt {
    /**
     * 遍历打印数组中的元素
     */
    public String printElements() {
        StringBuilder sb = new StringBuilder();
        sb.append("{size=").append(size).append(", [");
        for (int i = 0; i < size; i++) {
            sb.append(elements[i]);
            if (i != size - 1) {
                sb.append(", ");
            }
        }
        sb.append("]}");
        return sb.toString();
    }
}

🎨 遍历获取数组中的各个元素，然后进行拼接

🎨 Java 中大量字符串拼接用 StringBuilder 最好

☆写法2：

public class ArrayListInt {
 
    /**
     * 遍历打印数组中的元素
     */
    public String printElements() {
        StringBuilder sb = new StringBuilder();
        sb.append("{size=").append(size).append(", [");
        for (int i = 0; i < size; i++) {
            // 不是第 0 个元素就先拼接【, 】
            if (i != 0) {
                sb.append(", ");
            }
            sb.append(elements[i]);
        }
        sb.append("]}");
        return sb.toString();
    }
}

🎨 不是第 0 个元素就先拼接【, 】

🎨 相比写法1每次循环少了一次减法运算

(3) add (int index, int element)

☆ 往 index 位置插入元素 element

🎁 把 index 位置到 size - 1 位置【[index, size-1]】的元素往后挪动【空出 index 位置的元素】

🎁 把 element 元素赋值到 index 索引位置

🎁 从索引为 size - 1 处开始挪动

public class ArrayListInt {
    /**
     * 在 index 位置插入元素 element
     */
    public void add(int index, int element) {
        // 当 index 等于 size 的时候, 是往数组的尾部添加元素
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("size: " + size + ", " + "index: " + index);
        }
        // TODO 扩容检测
        // 挪动元素（从最后一个元素开始挪动）
        for (int i = size - 1; i >= index; i--) {
            elements[i + 1] = elements[i];
        }
        // 把元素 element 赋值到 index 索引位置
        elements[index] = element;
        size++; // 数组元素加1
    }
}

(4) 数组越界异常的封装

public class ArrayListInt {
    public void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("index: " + index + " size: " + size);
    }
    public void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            outOfBounds(index);
        }
    }
    public void rangeCheck4Add(int index) {
        if (index < 0 || index > size) {
            outOfBounds(index);
        }
    }
}

✏️ outOfBounds(int index)：封装抛异常的方法

✏️ rangeCheck(int index)：索引 index 不能小于 0 或大于等于 size，否则都会数组越界

✏️ rangeCheck4Add(int index)：添加元素的时候 index 是可以等于 size 的（此时是往数组的最后添加元素）

(5) MyJunit（接口测试）

🍃使用异常知识进行接口测试：当测试不通过的时候，会抛异常

🍃测试通过的时候，打印 Success!

public class MyJunit {
    public static void test(boolean boolean_) {
        try {
            if (!boolean_) throw new Exception("测试不通过");
            System.out.println("\nSuccess!");
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

(6) 扩容【 ensureCapacity() 】

📖① 申请全新的数组空间（容量适宜）

📖② 把就数据的数据复制到全新的数组中

📔 添加的时候才会考虑扩容操作

/**
     * 扩容检测
     *
     * @param capacity 数组容量至少是 capacity
     */
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        // 如果所需容量足够, 则不扩容
        if (oldCapacity >= capacity) return;
        // 申请全新的数组空间（新容量是旧容量的 1.5 倍）
        capacity = oldCapacity + (oldCapacity >> 1);
        int[] newElements = new int[capacity];
        // 把旧数组中的数据复制到新数组中
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        // elements 指针指向新数组
        elements = newElements;
        System.out.println(oldCapacity + "扩容为" + capacity);
    }

七、remove (int index)

📔 作用：删除 index 索引处的元素，返回之前 index 索引处的元素

📙 思路：① 用后面的元素把要 删除的索引 index 位置的元素覆盖掉

📙 ② 数组 size 减 1

📙 ③ 如何覆盖❓ 遍历

public class ArrayListInt {
    /**
     * 删除 index 位置的元素
     *
     * @param index 下标
     * @return 原来的元素
     */
    public int remove(int index) {
        // 取出 index 索引处原来的元素
        int old = get(index);
        // 覆盖掉 index 索引处的元素
        for (int i = index; i < size; i++) {
            elements[i] = elements[i + 1];
        }
        // 最后一个元素不被访问到的关键代码
        size--;
        return old;
    }
}

八、仅能存储 int 类型的动态数组 ArrayListInt 完整代码

/**
 * 只支持存储 int 类型数据的动态数组
 */
@SuppressWarnings("all")
public class ArrayListInt {
    private int size;
    private int[] elements;
    public static final int DEFAULT_CAPACITY = 10;
    public static final int ELEMENT_NOT_FOUND = -1;
    public ArrayListInt() {
        this(DEFAULT_CAPACITY);
    }
    public ArrayListInt(int capacity) {
        capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
        elements = new int[capacity];
    }
    public int size() {
        return size;
    }
    public boolean isEmpty() {
        return size == 0;
    }
    /**
     * 获取 index 索引处的元素
     */
    public int get(int index) {
        rangeCheck(index);
        return elements[index];
    }
    /**
     * 设置 index 位置的元素
     *
     * @param index   下标
     * @param element 要设置的元素
     * @return 原来的元素ֵ
     */
    public int set(int index, int element) {
        // 获取 index 位置的元素
        int old = get(index);
        elements[index] = element;
        return old;
    }
    /**
     * 返回元素的索引
     */
    public int indexOf(int element) {  
        for (int i = 0; i < size; i++) {
            if (element == elements[i]) return i;
        }
        return ELEMENT_NOT_FOUND;
    }
    /**
     * 检查数组中是否包含 element 元素
     */
    public boolean contains(int element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }
    /**
     * 清除全部元素
     * 只要【size = 0】就无法获取到数组中的任何元素了
     */
    public void clear() {
        size = 0;
    }
    /**
     * 往数组尾部添加元素
     */
    public void add(int element) {
        add(size, element);
    }
    /**
     * 在 index 位置插入元素 element
     */
    public void add(int index, int element) {
        rangeCheck4Add(index);
        // 扩容检测, 保证容量至少是【size+1】
        ensureCapacity(size + 1);
        // 挪动元素（从最后一个元素开始挪动）
        for (int i = size - 1; i >= index; i--) {
            elements[i + 1] = elements[i];
        }
        // 把元素 element 赋值到 index 索引位置
        elements[index] = element;
        size++; // 数组元素加1
    }
    /**
     * 扩容检测
     *
     * @param capacity 数组容量至少是 capacity
     */
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        // 如果所需容量足够, 则不扩容
        if (oldCapacity >= capacity) return;
        // 申请全新的数组空间（新容量是旧容量的 1.5 倍）
        capacity = oldCapacity + (oldCapacity >> 1);
        int[] newElements = new int[capacity];
        // 把旧数组中的数据复制到新数组中
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        // elements 指针指向新数组
        elements = newElements;
        System.out.println(oldCapacity + "扩容为" + capacity);
    }
    /**
     * 删除 index 位置的元素
     *
     * @param index 下标
     * @return 原来的元素
     */
    public int remove(int index) {
        // 取出 index 索引处原来的元素
        int old = get(index);
        // 覆盖掉 index 索引处的元素
        for (int i = index; i < size - 1; i++) {
            elements[i] = elements[i + 1];
        }
        // 最后一个元素不被访问到的关键代码
        size--;
        return old;
    }
    public void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("index: " + index + " size: " + size);
    }
    public void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            outOfBounds(index);
        }
    }
    public void rangeCheck4Add(int index) {
        if (index < 0 || index > size) {
            outOfBounds(index);
        }
    }
    /**
     * 遍历打印数组中的元素
     */
    public String printElements() {
        StringBuilder sb = new StringBuilder();
        sb.append("{size=").append(size).append(", [");
        for (int i = 0; i < size; i++) {
            // 不是第 0 个元素就拼接【, 】
            if (i != 0) {
                sb.append(", ");
            }
            sb.append(elements[i]);
        }
        sb.append("]}");
        return sb.toString();
    }
}

九、泛型（让动态数组中能存放各种类型的数据）

🎁 可使用 Java 中的泛型让动态数据更加通用（在动态数组中能存放任何数据类型的数据）

(1) clear () 【对象数组】

🧣 当动态数组中可以存储任何类型的时候，对于 clear() 方法，仅仅把 size 设置为 0 是不够的

🧣 把 size 设置为 0 后，虽然使用动态数组的人无法获取到任何数据，但这些数据仍然存活在内存中【这些数据依然存在，只是你无法使用它而已】

🧣 最佳的方式是：把 size 设置为 0，并把这些内存都回收掉（置为 null）

/**
     * 清除全部元素
     */
    public void clear() {
        // 销毁堆空间的对象数据
        for (int i = 0; i < elements.length; i++) {
            elements[i] = null;
        }
        
        size = 0;
    }

(2) 对象的比较不用【==】

🎁 两个对象用 == 运算符进行比较的时候，比较的是两个对象的内存地址

🎁 若不想比较两个对象的内存地址，需要用 equals() 方法

public int indexOf(E element) {
        if (element == null) return ELEMENT_NOT_FOUND;
        // 如果数组为空, 直接找不到
        if (isEmpty()) return ELEMENT_NOT_FOUND;
        for (int i = 0; i < size; i++) {
            if (element.equals(elements[i])) return i;
        }
        return ELEMENT_NOT_FOUND;
    }

(3) remove (int index) 清空最后一个元素

/**
     * 删除 index 位置的元素
     *
     * @param index 下标
     * @return 原来的元素
     */
    public E remove(int index) {
        // 取出 index 索引处原来的元素
        E old = get(index);
        // 覆盖掉 index 索引处的元素
        for (int i = index + 1; i < size; i++) {
            elements[i - 1] = elements[i];
        }
        // 把最后一个元素置空
        elements[--size] = null;
        return old;
    }

(4) null 值处理

动态数组中应该要能够存放 null 值

/**
     * 返回元素的索引
     */
    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;
    }

(5) ArrayList 完整代码

/**
 * 泛型让动态数组中能存放任何数据类型的数据
 */
@SuppressWarnings("all")
public class ArrayList<E> {
    private int size;
    private E[] elements;
    public static final int DEFAULT_CAPACITY = 10;
    public static final int ELEMENT_NOT_FOUND = -1;
    public ArrayList() {
        this(DEFAULT_CAPACITY);
    }
    public ArrayList(int capacity) {
        capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
        elements = (E[]) new Object[capacity];
    }
    public int size() {
        return size;
    }
    public boolean isEmpty() {
        return size == 0;
    }
    /**
     * 获取 index 索引处的元素
     */
    public E get(int index) {
        rangeCheck(index);
        return elements[index];
    }
    /**
     * 设置 index 位置的元素
     *
     * @param index   下标
     * @param element 要设置的元素
     * @return 原来的元素ֵ
     */
    public E set(int index, E element) {
        // 获取 index 位置的元素
        E old = get(index);
        elements[index] = element;
        return old;
    }
    /**
     * 返回元素的索引
     */
    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;
    }
    /**
     * 检查数组中是否包含 element 元素
     */
    public boolean contains(E element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }
    /**
     * 清除全部元素
     */
    public void clear() {
        // 销毁堆空间的对象数据
        for (int i = 0; i < elements.length; i++) {
            elements[i] = null;
        }
        size = 0;
    }
    /**
     * 往数组尾部添加元素
     */
    public void add(E element) {
        add(size, element);
    }
    /**
     * 在 index 位置插入元素 element
     */
    public void add(int index, E element) {
        rangeCheck4Add(index);
        // 扩容检测, 保证容量至少是【size + 1】
        ensureCapacity(size + 1);
        // 挪动元素（从最后一个元素开始挪动）
        for (int i = size - 1; i >= index; i--) {
            elements[i + 1] = elements[i];
        }
        // 把元素 element 赋值到 index 索引位置
        elements[index] = element;
        size++; // 数组元素加1
    }
    /**
     * 扩容检测
     *
     * @param capacity 数组容量至少是 capacity
     */
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        // 如果所需容量足够, 则不扩容
        if (oldCapacity >= capacity) return;
        // 申请全新的数组空间（新容量是旧容量的 1.5 倍）
        capacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[capacity];
        // 把旧数组中的数据复制到新数组中
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        // elements 指针指向新数组
        elements = newElements;
        System.out.println(oldCapacity + "扩容为" + capacity);
    }
    /**
     * 删除 index 位置的元素
     *
     * @param index 下标
     * @return 原来的元素
     */
    public E remove(int index) {
        // 取出 index 索引处原来的元素
        E old = get(index);
        // 覆盖掉 index 索引处的元素
        for (int i = index + 1; i < size; i++) {
            elements[i - 1] = elements[i];
        }
        // 把最后一个元素置空
        elements[--size] = null;
        return old;
    }
    public void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("index: " + index + " size: " + size);
    }
    public void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            outOfBounds(index);
        }
    }
    public void rangeCheck4Add(int index) {
        if (index < 0 || index > size) {
            outOfBounds(index);
        }
    }
    /**
     * 遍历打印数组中的元素
     */
    public String printElements() {
        StringBuilder sb = new StringBuilder();
        sb.append("{size=").append(size).append(", [");
        for (int i = 0; i < size; i++) {
            // 不是第 0 个元素就拼接【, 】
            if (i != 0) {
                sb.append(", ");
            }
            sb.append(elements[i]);
        }
        sb.append("]}");
        return sb.toString();
    }
}

JDK 中内置了动态数组类：java.util.ArrayList

如有错误和疑问，欢迎和我交流

【数据结构与算法】1、学习动态数组数据结构（基本模拟实现 Java 的 ArrayList 实现增删改查）

一、什么是数据结构

(1) 概念

(2) 分类

二、线性表

三、数组（Array）

(1) 数组的底层结构

(2) 数组缺点

四、动态数组（Dynamic Array）接口设计

五、动态数组的设计和基本代码实现

(1) 成员变量

(2) 代码

① get ()

② indexOf ()

③ clear ()

六、add 方法和扩容

(1) add (int element)

(2) 打印动态数组中的元素

(3) add (int index, int element)

(4) 数组越界异常的封装

(5) MyJunit（接口测试）

(6) 扩容【 ensureCapacity() 】

七、remove (int index)

八、仅能存储 int 类型的动态数组 ArrayListInt 完整代码

九、泛型（让动态数组中能存放各种类型的数据）

(1) clear () 【对象数组】

(2) 对象的比较不用【==】

(3) remove (int index) 清空最后一个元素

(4) null 值处理

(5) ArrayList 完整代码

热门文章

最新文章

相关课程

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

【数据结构与算法】1、学习动态数组数据结构（基本模拟实现 Java 的 ArrayList 实现增删改查）

一、什么是数据结构

(1) 概念

(2) 分类

二、线性表

三、数组（Array）

(1) 数组的底层结构

(2) 数组缺点

四、动态数组（Dynamic Array）接口设计

五、动态数组的设计和基本代码实现

(1) 成员变量

(2) 代码

① get ()

② indexOf ()

③ clear ()

六、add 方法和扩容

(1) add (int element)

(2) 打印动态数组中的元素

(3) add (int index, int element)

(4) 数组越界异常的封装

(5) MyJunit（接口测试）

(6) 扩容【 ensureCapacity() 】

七、remove (int index)

八、仅能存储 int 类型的动态数组 ArrayListInt 完整代码

九、泛型（让动态数组中能存放各种类型的数据）

(1) clear () 【对象数组】

(2) 对象的比较不用 【==】

(3) remove (int index) 清空最后一个元素

(4) null 值处理

(5) ArrayList 完整代码

热门文章

最新文章

相关课程

相关电子书

(2) 对象的比较不用【==】