首页 > 其他分享 >第1章. 动态数组(ArrayList)

第1章. 动态数组(ArrayList)

时间：2023-12-06 20:11:32浏览次数：32  
标签：index elements int ArrayList 数组 动态 public size

动态数组

一、动态数组接口设计

// 这里可以写一个List接口,然后ArrayList类去实现这个接口,实现接口中的方法。但为了方便起见,直接将这些方法写在类中。
// 这些方法暂时不添加泛型、和正确的返回值
public class ArrayList {
    // 动态数组的长度
    private int size;

    // 动态数组的所有元素
    private int[] elements;

    // 返回动态数组的长度
    public int size() {
        return 0;
    }

    // 判断动态数组是否为空
    public boolean isEmpty() {
        return false;
    }
    
    // 判断是否包含某个元素
    public boolean contains(int element) {
        return false;
    }
    
    // 添加元素到动态数组末尾
    public void add(int element) {
        
    }
    
    // 添加元素到动态数组index索引位置
    public void add(int index, int element) {

    }
    
    // 返回index索引位置对应的元素
    public int get(int index) {
        return 0;
    }
    
    // 删除index索引位置对应的元素,并返回所删除的元素
    public int remove(int index) {
        return 0;
    }
    
    // 设置index位置的元素,并返回旧值
    public int set(int index, int element) {
        return 0;
    }
    
    // 查看指定元素第一次出现的位置
    public int indexOf(int element) {
        return 0;
    }
    
    // 清除所有元素
    public void claer() {
        
    }
    
    // 打印数组,重写toString()方法
    @Override
    public String toString() {
       
    }
}

二、动态数组的设计

public class ArrayList {
    // 动态数组的长度
    private int size;

    // 动态数组的所有元素
    private int[] elements;
     
}

三、动态数组的构造器

// 提供一个带参构造器,创建用户输入的数组容量,若用户输入容量小于默认初始容量10,则创建10个长度的数组
// 动态数组的默认初始容量

private static final int DEFAULT_CAPACITY = 10;

public ArrayList(int capacity) {
    capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
    elements = new int[capacity];
}


// 提供一个空参构造器,默认数组的初始容量为10
public ArrayList() {
    //elements = new int[DEFAULT_CAPACITY];
    this(DEFAULT_CAPACITY);
}

四、核心操作

4.1 获取第一个元素位置：indexOf
// 查看指定元素第一次出现的位置,如果找不到则返回-1
public int indexOf(int element) {
    // 遍历动态数组。注意size和elements.length的区别
    for (int i = 0; i < size; i ++) {
        if (elements[i] == element) {
            return i;
        }
    }
    return ELEMENT_NOT_FOUND;
}
  • 注意区别size和elements.length的区别
    • size表示的是当前数组元素的个数
    • elements.length表示的是数组的长度，也即动态数组的容量capacity
    • size <= elements.length。所以在遍历动态数组的时候，一定是i < size而不是i < elements.length。
4.2 清除元素：clear
// 清除所有元素
public void clear() {
    size = 0;
}
  • 为什么不写成elements=null？
    • 原因是当用户执行clear()操作后，后面可能还需要使用add操作，所以数组分配的这些内存空间后面可能还需要使用。
    • size = 0 的操作已经对用户来说已经无法访问动态数组中的元素了。但这数组的内存空间还在。
4.3 打印数组：toString
// 打印数组
@Override
public String toString() {
    StringBuilder sb = new StringBuilder();
    sb.append("size = ").append(size).append(", ").append("[");
    for (int i = 0; i < size; i ++) {
        if (i == size - 1) {
            sb.append(elements[i]);
            break;
        }
        sb.append(elements[i]).append(",");
    }
    sb.append("]");

    return sb.toString();
}
  • 打印引用对象，默认是调用其toString()方法
  • 所以需要重写toStirng方法，在toString()方法中将元素拼接成字符串
  • 字符串拼接建议使用StringBuilder
4.4 删除元素：remove

// 删除index索引位置对应的元素,并返回所删除的元素
public int remove(int index) {
    // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
    }
    // 保存要被删除的值
    int remove = elements[index];

    // 从被删除的后一个元素开始往前移动
    for (int i = index + 1; i < size; i ++) {
        elements[i - 1] = elements[i];
    }
    size --;

    return remove;
}
4.5 动态数组扩容

  • 需要扩容的地方：add方法
// 确保有needCapacity的容量
private void ensureCapacity(int needCapacity) {
    // 当前容量为nowCapacity
    int nowCapacity = elements.length;
    // 当前容量大于等于所需要的容量，容量够
    if (nowCapacity >= needCapacity) return;
    // 容量不够,则扩容至1.5倍
    int newCapacity = nowCapacity + (nowCapacity >> 1);
    int[] newElements = new int[newCapacity];

    // 拷贝元素
    for(int i = 0; i < elements.length; i ++) {
        newElements[i] = elements[i];
    }
    elements = newElements;

    System.out.println(nowCapacity + "扩容为：" + newCapacity);
}
4.6 添加元素：add

// 添加元素到动态数组末尾
public void add(int element) {
    add(size, element);
}

// 添加元素到动态数组index索引位置
public void add(int index, int element) {
    //        // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
    //        if (index < 0 || index > size) {
    //            throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
    //        }
    
    // 扩容
    rangeCheckForAdd(index);

    // 当前动态数组的元素个数为size,我们确保需要size+1个容量
    ensureCapacity(size + 1);

    for (int i = size - 1; i >= index; i --) {
        elements[i + 1] = elements[i];
    }
    elements[index] = element;
    size ++;
}

五、给动态数组添加泛型

使用泛型技术可以让动态数组更加通用，可以存放任何数据类型的数据。

public class ArrayList<E> {
    // 动态数组的长度
    private int size;
    // 动态数组的所有元素
    private E[] elements;
    
    // 特别重要！
    elements = (E[]) new Object[capacity];
}

ArrayList<Integer> list = new ArrayList<>();
  • elements = (E[]) new Object[capacity];
  • E[] newElements = (E[])new Object[newCapacity];

不能elements = new E[capacity]；的原因是泛型是编译时期的，而new是运行时期的

六、内存管理细节

给动态数组添加泛型之后，考虑到内存管理细节，需要修改某些方法的内部实现。

6.1 对象数组

6.2 清空操作clear()细节
// 清除所有元素
public void clear() {
    // (内存管理细节)对象内存清空，但是对象数组所分配的内存还在
    for (int i = 0; i < size; i ++) {
        elements[i] = null;
    }
    size = 0;
}
6.3 删除操作remove()细节
// 删除index索引位置对应的元素,并返回所删除的元素
public E remove(int index) {
    // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
    rangeCheck(index);

    // 保存要被删除的值
    E remove = elements[index];

    // 从被删除的后一个元素开始往前移动
    for (int i = index + 1; i < size; i ++) {
        elements[i - 1] = elements[i];
    }

    // (内存管理细节)将最后一个元素变为null
    elements[size - 1] = null;

    size --;

    return remove;
}
6.4 indexOf()方法小细节
// 查看指定元素第一次出现的位置,如果找不到则返回-1
public int indexOf(E element) {
    // 遍历动态数组。注意size和elements.length的区别
    for (int i = 0; i < size; i ++) {
        // 小细节 不再是 ==
        if (elements[i].equals(element)) {
            return i;
        }
    }
    return ELEMENT_NOT_FOUND;
}
6.5 null值处理细节
// 查看指定元素第一次出现的位置,如果找不到则返回-1
public int indexOf(E element) {
    // 遍历动态数组。注意size和elements.length的区别

    // 找null。则element为空,不可以element.equals(elements[i]),直接用elements[i] == null判断
    if (element == null) {
        for (int i = 0; i < size; i ++) {
            if (elements[i] == null) {  // elements[i]为空
                return i;
            }
        }
    } else {
        // 找不为null。则element不为空,可以element.equals(elements[i])
        for (int i = 0; i < size; i ++) {
            // 避免空指针异常
            if (element.equals(elements[i])) {
                return i;
            }
        }
    }
    return ELEMENT_NOT_FOUND;
}

七、最终迭代后的代码

package DataStructure._01动态数组;

/**
 * @author keyongkang
 * @date 2022-07-10-10:09
 */

public class ArrayList<E> {
    // 动态数组的长度
    private int size;

    // 动态数组的所有元素
    private E[] elements;

    // 动态数组的默认初始容量
    private static final int DEFAULT_CAPACITY = 10;
    private static final int ELEMENT_NOT_FOUND = -1;

    public ArrayList(int capacity) {
        capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
        elements = (E[])new Object[capacity];
    }

    public ArrayList() {
        //elements = new int[DEFAULT_CAPACITY];
        this(DEFAULT_CAPACITY);
    }

    private void rangeCheck(int index) {
        // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
        }
    }

    private void rangeCheckForAdd(int index) {
        // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
        }
    }

    // 返回动态数组的长度
    public int size() {
        return size;
    }

    // 判断动态数组是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 判断是否包含某个元素
    public boolean contains(E element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    // 添加元素到动态数组末尾
    public void add(E element) {
        add(size, element);
    }

    // 添加元素到动态数组index索引位置
    public void add(int index, E element) {
//        // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
//        if (index < 0 || index > size) {
//            throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
//        }
        rangeCheckForAdd(index);

        // 当前动态数组的元素个数为size,我们确保需要size+1个容量
        ensureCapacity(size + 1);

        for (int i = size - 1; i >= index; i --) {
            elements[i + 1] = elements[i];
        }
        elements[index] = element;
        size ++;
    }

    // 确保有needCapacity的容量
    private void ensureCapacity(int needCapacity) {
        // 当前容量为nowCapacity
        int nowCapacity = elements.length;
        // 当前容量大于等于所需要的容量，容量够
        if (nowCapacity >= needCapacity) return;
        // 容量不够,则扩容至1.5倍
        int newCapacity = nowCapacity + (nowCapacity >> 1);
        E[] newElements = (E[])new Object[newCapacity];

        // 拷贝元素
        for(int i = 0; i < elements.length; i ++) {
            newElements[i] = elements[i];
        }
        elements = newElements;

        System.out.println(nowCapacity + "扩容为：" + newCapacity);
    }

    // 返回index索引位置对应的元素
    public E get(int index) {
//        // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
//        if (index < 0 || index >= size) {
//            throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
//        }
        rangeCheck(index);
        return elements[index];
    }

    // 删除index索引位置对应的元素,并返回所删除的元素
    public E remove(int index) {
//        // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
//        if (index < 0 || index >= size) {
//            throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
//        }
        rangeCheck(index);

        // 保存要被删除的值
        E remove = elements[index];

        // 从被删除的后一个元素开始往前移动
        for (int i = index + 1; i < size; i ++) {
            elements[i - 1] = elements[i];
        }

        // (内存管理细节)将最后一个元素变为null
        elements[size - 1] = null;

        size --;

        return remove;
    }

    // 设置index位置的元素,并返回旧值
    public E set(int index, E element) {
//        // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
//        if (index < 0 || index >= size) {
//            throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
//        }

        rangeCheck(index);

        // 保存当前索引的旧值
        E old = elements[index];
        // 设置index位置的新值
        elements[index] = element;

        return old;
    }

    // 查看指定元素第一次出现的位置,如果找不到则返回-1
    public int indexOf(E element) {
        // 遍历动态数组。注意size和elements.length的区别

        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 ELEMENT_NOT_FOUND;
    }

    // 清除所有元素
    public void clear() {
        //size = 0;
        // (内存管理细节)对象内存清空，但是对象数组所分配的内存还在
        for (int i = 0; i < size; i ++) {
            elements[i] = null;
        }
        size = 0;
    }

    // 打印数组
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("size = ").append(size).append(", ").append("[");
        for (int i = 0; i < size; i ++) {
            if (i == size - 1) {
                sb.append(elements[i]);
                break;
            }
            sb.append(elements[i]).append(", ");
        }
        sb.append("]");

        return sb.toString();
    }
}

标签：index,elements,int,ArrayList,数组,动态,public,size
From： https://www.cnblogs.com/keyongkang/p/17880426.html

相关文章

  • 【转】编译型与解释型、动态语言与静态语言、强类型语言与弱类型语言的区别
    编译型和解释型我们先看看编译型，其实它和汇编语言是一样的：也是有一个负责翻译的程序来对我们的源代码进行转换，生成相对应的可执行代码。这个过程说得专业一点，就称为编译（Compile），而负责编译的程序自然就称为编译器（Compiler）。如果我们写的程序代码都包含在一个源文件中，那么通常编译......
  • VBA-Excel数组应用
    1）数组创建A类：动态数组Dimarr()  创建一个动态变量数组,不受长度/数据类型受制B类：静态数组Dimarr(5) asstring  创建一个一维数组,下标从0开始,最大下标值为5Dimarr(3,3)asInteger创建一个二维数组,开始arr(0,0),最后一个arr(3,3)Dimarr=array(1,2,3)创建一......
  • JNA加载存在多个依赖的so动态库
    之前记录过在windows上加载单个ddl动态库（JNA简单使用（一）（java和c++互操作）-浪迹天涯的派大星-博客园(cnblogs.com)），这次记录一下在linux上调用存在多个依赖的so动态库。1、背景需要c++分片处理一种特殊格式的文件，Java接受分片数据后保存，采用JNA的方式调用c++动态库的方式实现。......
  • 核电堆芯组件动态特性试验研究
    u  核电试验概述反应堆是核电事业的核心组成部分之一，堆内构件、堆芯燃料组件等部件在冷却剂流动冲击下，会诱发剧烈振动，导致堆芯内试验件流道不稳定。为了保障反应堆的安全运行，根据国家核安全法规规定，有必要对受冷却剂冲击的堆内构件进行振动特性试验，用于判断系统和零部件在一定流......
  • 【VUE】vue动态变换背景图片的实现 +背景图片铺满+ 一般路由的配置
    一、动态变换背景图片的实现代码如下：<template><divclass="body"v-loading="loading":style="{backgroundImage:'url('+bgi+')'}"></div></template><script>data(){reyurn{ b......
  • 稀疏数组 待完善
    packagearray;importjava.util.Arrays;publicclassArrayDemo08{publicstaticvoidmain(String[]args){//1.创建一个二维数组11*110：没有棋子1；黑棋2：白棋int[][]array1=newint[11][11];//二维数组的行数和列数array1[1][2]......
  • Power BI 利用函数动态生成日期表
    日期表是万能的维度表，本文介绍一种在PowerQuery中快速生成日期表的方法，只需要创建一个函数，函数接受三个参数：开始日期，结束日期，财年的开始月份，然后就可以生成一个完整的日期表。PowerQuery中创建一个空查询，切入高级模式：放入以下代码：letfnDateTable=(StartDateasdate,EndDate......
  • vue3使用虚拟化表格自定义表格并动态生成表头
    elementPlus的虚拟化表格用的是lang=tsx,先安装cnpmi@vitejs/plugin-vue-jsx然后去vite.config.ts里加配置importvueJsxfrom'@vitejs/plugin-vue-jsx'plugins:[vue(),vueJsx(),]再去tsconfig.json中加东西//不要把compilerOptio......
  • Linux环境中动态库文件（.so文件）的realname，soname和linkname--解释清楚
    realname：实际等同于库文件的filename，是在库文件生成时就被指定的，如：gcc-shared-o$(realname)dependenceflagsrealname的一般格式为lib$(name).so.$(major).$(minor).$(revision)，$(name)是动态库的名字，$(major).$(minor).$(revision)分别表示主版本号，子版本号和修正版本......
  • 动态库文件（.so文件）的realname，soname和linkname 介绍和使用说明
    动态库文件（.so文件）的realname，soname和linkname介绍和使用说明介绍动态库文件（.so文件）的realname，soname和linkname介绍编译时设置soname和realname参考makefile设置sonamereadelf查看动态库sonamereadelf-dlibxxx.soreadelf功能介绍 ......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99