Java-数据结构-顺序表(ArrayList)

在之前的博客中,我们大部分都在学习数据结构相关的理论知识,而今天我们要学到的ArrayList便有所不同了,ArrayList这部分算是重要的知识,所以大家打起精神,让我们一起学习~

在学习ArrayList之前,我们需要先认识一下List:

一、认识 List 接口

① List 的定义

在Java中,List是一个接口,它继承自 Collection 接口。List 接口代表一个有序的元素序列,允许元素重复。也就是说我们可以按照添加顺序存储一组元素,并且同一元素可以多次出现。List 接口为我们提供了许多方法来控制列表中的元素

我们可以通过这张关系图看出来,List在其中所处的位置,以及它继承什么,它的子类都有什么。

② List 的基本方法

List 接口包括 Collection 接口的所有方法,因为Collection是List的超级接口。

③ List 的使用

首先我们由刚刚的图能够知道,List 是一个接口,它不能直接用来实例化!

而想要具体使用 List 就需要我们实例化 List 的实现类~所以就引出我们本篇博客的主要内容:ArrayList

二、认识 ArrayList

① 线性表

📚 线性表的定义

线性表是由n个具有相同数据类型的元素构成的有限序列,其中元素之间存在一对一的前后关系。常见的线性表有:顺序表、链表、栈、队列...

📕 元素类型:线性表中的元素具有相同的数据类型,可以是基本数据类型(如整数、浮点数等)或者自定义的对象类型。

📕 元素的数量:线性表中的元素个数是有限的,通过计数器或者链式结构进行统计。

📕 元素顺序:线性表中元素的顺序是有序的,每个元素都唯一对应一个前驱元素和一个后继元素(除了第一个元素没有前驱,最后一个元素没有后继)。

(注:线性表在逻辑上是线性结构,也就是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组链式结构的形式存储。)

② 顺序表

📚 顺序表的定义

顺序表使用数组或者类似数组的存储结构,元素在内存中连续存储,通过数组下标访问元素。顺序表的插入和删除操作需要移动大量元素,但是随机访问效率较高。

③ ArrayList 的定义

在上图中,我们可以知道 ArrayList 就是 List 的实现类,而 ArrayList 同时也是顺序表的一种。

ArrayList 与我们之前所学习过的"数组"很像,在逻辑上基本是一致的但是 ArrayList 由于是 List 接口的实现,所以也就理所应当的拥有很多的方法,比如 ArrayList 相比于"数组",则会更为灵活,因为当我们创建"数组"时,必须声明"数组"的大小才能够使用它,一旦声明了数组的大小就很难去更改它。而 ArrayList 中所拥有的方法就能够解决这个问题,ArrayList 允许我们创建可调整大小的数组,并会自动扩容~所以 ArrayList 也被称为 "动态数组"。

(注:ArrayList 的自动扩容为原来的1.5倍,就是旧容量加上旧容量值右移一位得到的)

所以在学习 ArrayList 之后,我们以后无论是做题还是工作,大部分时候都是优先选择 ArrayList 的~

④ ArrayList 的创建

📚 在Java中创建数组列表的方法

//向上转型 利用多态使用 List 创建一个 ArrayList
List<Integer> list = new ArrayList<>();
//直接创建 ArrayList
ArrayList<Integer> arrayList = new ArrayList<>();

(注:Integer 也可以换成其他的"基本数据类型对应包装类"或其他自定义类~)

三、ArrayList 的方法

接下来我将边为大家讲解示范 ArrayList 的各种方法,同时模拟实现一个 MyArrayList 以便大家更好的理解~

① ArrayList 基本框架

上面我们提到了,ArrayList 其实就是"动态数组",所以我们可以用数组来作为 MyArrayList 中存储数据的载体,并且为了后续能够使 MyArrayList 拥有自动扩容的能力,我们还需要创建出一个"有效大小 usedSize""默认容量 DEFAULT_SIZE"以协助我们后续编写方法

public class MyArrayList {
    //创建数组作为顺序表
    public int[] elem;
    //数组的有效大小
    public int usedSize;
    //初始容量
    private static final int DEFAULT_SIZE = 10;

    public MyArrayList() {
        this.elem = new int[DEFAULT_SIZE];
    }
}

② ArrayList.add(int data) 

这个很好理解,就是往顺序表中添加新的元素,但是,这与数组的" arr[0] = in.nextInt() "不太一样因为数组元素未初始化时,本身就有默认值 0 ,这样的操作只是将新的数据把 0 替换掉了而已并不是添加进去而 ArrayList 在逻辑上就是添加了新的元素,而并不是替换~

📚 那么我们再尝试一下,在刚刚创建的 MyArrayList 中也实现一个 add() 方法

📌 为防止越界访问,该方法需要做到能够识别顺序表是否已满

📌 若此时已满,该方法则发生自动扩容

    public void add(int data) {
        if(isFull()){
            //1.5倍扩容
            elem = Arrays.copyOf(elem,elem.length + (elem.length >> 1));
        }
        elem[usedSize] = data;
        usedSize++;
    }
    public boolean isFull() {
        if(usedSize >= elem.length) {
            return true;
        }
        return false;
    }

我们的顺序表初始大小是10,那么我们多输入几个数据试试,看看有没有自动扩容

是不是觉得有些晕晕的?不要忘了,ArrayList 是可以直接打印的,但我们的 MyArrayList 以数组作为载体,直接打印的话当然出现的是地址啦~所以我们接下来还得再实现一下 toString() 的重写才行~

③ ArrayList 的打印

打印数组各个元素时,我们需要将数组遍历一遍,但是 ArrayList 是能够直接打印其中元素的,其打印格式为:

于是我们也按照该格式重写 toString() 就好了:

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for(int i = 0;i < usedSize;i++){
            sb.append(elem[i]);
            if(i != usedSize - 1){
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }

📚 借此我们也顺便测试一下上面的 add()  方法编写的是否有误

看来格式是没有问题的,并且"检查顺序表是否已满""自动扩容"的功能目前看来也没有问题~

④ ArrayList.add(int pos,int data)

上面我们了解到了 ArrayList 的 add(int data) 方法,作用是直接在顺序表的末尾添加一个新元素,而还有另一个带下标参数的 add(int pos,int data) 方法,它的作用就是在顺序表的指定位置(pos)添加一个元素~

(注:并不是在 pos 之后插入数据,而是将数据放在 pos 的位置上,其余位置向后移动)
就像赛跑的时候,你超越了第二名,但你并不是第一名,只是第二名~

📚 还是让我们看看这个功能在 MyArrayList 中是如何实现的

📌 该方法需要判断 pos 的合法性

📌 该方法需要将位于 pos 以及之后的元素后移一位

📌 该方法仍需要判断顺序表是否已满,并自动扩容

首先为了判断 pos 的合法性,我们需要自定义一个异常类,用于在 pos 访问不合法时报错并给予提示

public class PosIllegal extends RuntimeException{
    public PosIllegal(){

    }
    public PosIllegal(String message){
        super(message);
    }
}

随后我们还需要判断 pos 是否合法

    private boolean checkPosInAdd(int pos) {
        if(pos > usedSize + 1 || pos < 0){
            throw new PosIllegal("pos的位置不合法");
        }
        return true;//合法
    }

(注:pos 是可以等于 usedSize 的,当 pos = usedSize 时,此时为尾插)

    // 在 pos 位置新增元素
    public void add(int pos, int data) {
        if(checkPosInAdd(pos)){
            usedSize++;
            if(isFull()) {
                elem = Arrays.copyOf(elem, elem.length << 1);
            }
            for (int i = usedSize - 2; i >= pos; i--) {
                elem[i + 1] = elem[i];
            }
            elem[pos] = data;
        }
    }

📚 让我们检验一下

📕 pos 不合法

📕 pos 合法

⑤ ArrayList.contains(int toFind)

ArrayList 的 contains 方法的作用:用于判断ArrayList中是否包含指定的元素。

📕 能查找到则返回 true

📕 查找不到则返回 false

📚 接下来我们模拟实现 contains(int toFind) 方法

只需要拥有查找指定元素的功能就行了~想查找到一个元素的方法很多,最简单的方式就是遍历数组,但既然是自己实现,就多写写自己不熟悉的代码嘛~不然怎么能起到练习的作用呢,所以我打算使用二分来实现 contains 方法

二分就需要我们先定义一个 left 和一个 right 表示起始点和终点(查找范围),并且每一步都求出两者的中间值 mid ,通过判断"顺序表 mid 位置的元素大小" 和 "toFind" 的大小,从而移动 left 和 right 的位置,以此慢慢缩短距离,找到 toFind 

    // 判定是否包含某个元素
    public boolean contains(int toFind) {
        int l = 0;
        int r = usedSize - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(toFind <= elem[mid]){
                r = mid;
            }else {
                l = mid + 1;
            }
        }
        if(elem[l] == toFind){
            return true;
        }
        return false;
    }

⑥ ArrayList.indexOf(int toFind)

ArrayList 的 indexOf 方法的作用是:用于返回指定元素在ArrayList中首次出现的索引位置。如果ArrayList中不包含该元素则返回-1。

上面我所写的二分代码,就是能够遇到重复数字时,只查到第一次出现的,所以我们只需要稍微改动即可:

    // 查找某个元素对应的位置
    public int indexOf(int toFind) {
        int l = 0;
        int r = usedSize - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(toFind <= elem[mid]){
                r = mid;
            }else {
                l = mid + 1;
            }
        }
        if(elem[l] == toFind){
            return l;
        }
        return -1;
    }

⑦ ArrayList.get(int pos)

ArrayList的get方法用于返回指定索引位置上的元素。

这样用起来看着没什么问题,也很好实现,但不妨让我们在写两行代码呢:

📚 那么让我们试着实现一下 get(int pos) 方法

📌 判断是否为空表

📌 判断 pos 是否合法

public class PosIllegal extends RuntimeException{
    public PosIllegal(){

    }
    public PosIllegal(String message){
        super(message);
    }
}
    //判断是否为空表
    public boolean isEmpty() {
        if(usedSize == 0) {
            return true;
        }
        return false;
    }
    public int get(int pos) {
        if(isEmpty()){
            throw new ListIsEmpty("顺序表为空!");
        }
        if(pos > usedSize - 1 || pos < 0){
            throw new PosIllegal("pos的位置不合法!");
        }
        return elem[pos];
    }

让我们再测试一下

⑧ ArrayList.set(int pos,int value)

ArrayList的set方法用于将指定索引位置上的元素替换为新的元素。

该方法与上面的 add(int pos,int data) 方法类似,就不过多介绍了,大家一定能看懂的~

    // 给 pos 位置的元素设为【更新为】 value
    public void set(int pos, int value) {
        if(checkPosInAdd(pos)){
            elem[pos] = value;
        }
    }

⑨ ArrayList.remove(int key)

ArrayList的remove方法用于从列表中删除指定位置的元素或指定元素的第一个匹配项。

实现这个方法我们只需要使用上面用到的 indexOf() 方法找到指定元素后,将其删除,将之后的元素一一向前移动即可~(还需要注意检查是否为空表)代码:

    public void remove(int key) {
        int index = indexOf(key);
        if(isEmpty()){
            throw new ListIsEmpty("顺序表为空!");
        }
        if(index < 0){
            return;
        }
        for(int i = index ;i < usedSize;i++){
            elem[i] = elem[i + 1];
        }
        usedSize--;
    }

⑩ size()与clear()

ArrayList.size() 方法的作用是返回 ArrayList 中元素的数量。

ArrayList.clear() 的作用是清空 ArrayList 中的所有元素,将其变为空列表。

    // 获取顺序表长度
    public int size() {
        return usedSize;
    }

    // 清空顺序表
    public void clear() {
        usedSize = 0;
    }

四、模拟ArrayList完整代码

📖 MyArrayList.java

import java.util.Arrays;

public class MyArrayList {
    public int[] elem;
    public int usedSize;
    private static final int DEFAULT_SIZE = 10;

    public MyArrayList() {
        this.elem = new int[DEFAULT_SIZE];
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for(int i = 0;i < usedSize;i++){
            sb.append(elem[i]);
            if(i != usedSize - 1){
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }

    // 新增元素,默认在数组最后新增
    public void add(int data) {
        if(isFull()){
            elem = Arrays.copyOf(elem,elem.length + (elem.length >> 1));
        }
        elem[usedSize] = data;
        usedSize++;
    }

    /**
     * 判断当前的顺序表是不是满的!
     *
     * @return true:满   false代表空
     */
    public boolean isFull() {
        if(usedSize >= elem.length) {
            return true;
        }
        return false;
    }

    private boolean checkPosInAdd(int pos) {
        if(pos > usedSize + 1 || pos < 0){
            throw new PosIllegal("pos的位置不合法");
        }
        return true;//合法
    }

    // 在 pos 位置新增元素
    public void add(int pos, int data) {
        if(checkPosInAdd(pos)){
            usedSize++;
            if(isFull()) {
                elem = Arrays.copyOf(elem, elem.length << 1);
            }
            for (int i = usedSize - 2; i >= pos; i--) {
                elem[i + 1] = elem[i];
            }
            elem[pos] = data;
        }
    }

    // 判定是否包含某个元素
    public boolean contains(int toFind) {
        int l = 0;
        int r = usedSize - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(toFind <= elem[mid]){
                r = mid;
            }else {
                l = mid + 1;
            }
        }
        if(elem[l] == toFind){
            return true;
        }
        return false;
    }

    // 查找某个元素对应的位置
    public int indexOf(int toFind) {
        int l = 0;
        int r = usedSize - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(toFind <= elem[mid]){
                r = mid;
            }else {
                l = mid + 1;
            }
        }
        if(elem[l] == toFind){
            return l;
        }
        return -1;
    }

    // 获取 pos 位置的元素
    public int get(int pos) {
        if(isEmpty()){
            throw new ListIsEmpty("顺序表为空!");
        }
        if(pos > usedSize - 1 || pos < 0){
            throw new PosIllegal("pos的位置不合法!");
        }
        return elem[pos];
    }

    public boolean isEmpty() {
        if(usedSize == 0) {
            return true;
        }
        return false;
    }

    // 给 pos 位置的元素设为【更新为】 value
    public void set(int pos, int value) {
        if(checkPosInAdd(pos)){
            elem[pos] = value;
        }
    }

    /**
     * 删除第一次出现的关键字key
     */
    public void remove(int key) {
        int index = indexOf(key);
        if(isEmpty()){
            throw new ListIsEmpty("顺序表为空!");
        }
        if(index < 0){
            return;
        }
        for(int i = index ;i < usedSize;i++){
            elem[i] = elem[i + 1];
        }
        usedSize--;
    }

    // 获取顺序表长度
    public int size() {
        return usedSize;
    }

    // 清空顺序表
    public void clear() {
        usedSize = 0;
    }
}

📖 PosIllegal.java

public class PosIllegal extends RuntimeException{
    public PosIllegal(){

    }
    public PosIllegal(String message){
        super(message);
    }
}

📖 ListIsEmpty.java

public class ListIsEmpty extends RuntimeException{
    public ListIsEmpty(){

    }
    public ListIsEmpty(String message){
        super(message);
    }
}

那么关于ArrayList(顺序表)的知识就为大家分享到这里啦~作者能力有限,如果有讲得不清晰或者不正确的地方,还请大家在评论区多多指出,我也会虚心学习的!那我们下次再见哦~

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/947569.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

stable diffusion安装mov2mov

第一步&#xff1a; 下载mov2mov&#xff0c;地址&#xff1a;https://gitcode.com/gh_mirrors/sd/sd-webui-mov2mov 下载包到web-ui的sd-webui-aki-v4.10\extensions文件夹面解压 第二步&#xff1a;在文件夹中调出cmd窗口&#xff0c;执行下列命令&#xff0c; git restore…

RWKV 语言模型

RWKV Language Model是一种独特的循环神经网络&#xff08;RNN&#xff09;架构的语言模型&#xff0c;具有诸多优势和特点&#xff0c;在自然语言处理领域展现出了良好的性能和应用潜力&#xff0c;以下是具体介绍&#xff1a; 核心原理 融合RNN与Transformer优点&#xff1a;…

基于单片机的温湿度采集系统(论文+源码)

2.1系统的功能 本系统的研制主要包括以下几项功能&#xff1a; (1)温度检测功能&#xff1a;对所处环境的温度进行检测&#xff1b; (2)湿度检测功能&#xff1a;对所处环境的湿度进行检测&#xff1b; (3)加热和制冷功能&#xff1a;可以完成加热和制冷功能。 (4)加湿和除…

「Mac畅玩鸿蒙与硬件49」UI互动应用篇26 - 数字填色游戏

本篇教程将带你实现一个数字填色小游戏&#xff0c;通过简单的交互逻辑&#xff0c;学习如何使用鸿蒙开发组件创建趣味性强的应用。 关键词 UI互动应用数字填色动态交互逻辑判断游戏开发 一、功能说明 数字填色小游戏包含以下功能&#xff1a; 数字选择&#xff1a;用户点击…

OCR图片中文字识别(Tess4j)

文章目录 Tess4J下载 tessdataJava 使用Tess4j 的 demo Tess4J Tess4J 是 Tesseract OCR 引擎的 Java 封装库&#xff0c;它让 Java 项目更轻松地实现 OCR&#xff08;光学字符识别&#xff09;功能。 下载 tessdata 下载地址&#xff1a;https://github.com/tesseract-ocr/…

Redis面试相关

Redis开篇 使用场景 缓存 缓存穿透 解决方法一&#xff1a; 方法二&#xff1a; 通过多次hash来获取对应的值。 小结 缓存击穿 缓存雪崩 打油诗 双写一致性 两种不同的要求 强一致 读锁代码 写锁代码 强一致&#xff0c;性能低。 延迟一致 方案一&#xff1a;消息队列 方…

【快速实践】深度学习 -- 数据曲线平滑化

希望对你有帮助呀&#xff01;&#xff01;&#x1f49c;&#x1f49c; 如有更好理解的思路&#xff0c;欢迎大家留言补充 ~ 一起加油叭 &#x1f4a6; 欢迎关注、订阅专栏 【深度学习从 0 到 1】谢谢你的支持&#xff01; 在观察数据结果时&#xff0c;我们通常希望获得整体趋…

RS485方向自动控制电路分享

我们都知道RS485是半双工通信&#xff0c;所以在传输的时候需要有使能信号&#xff0c;标明是发送还是接收信号&#xff0c;很多时候就简单的用一个IO口控制就好了&#xff0c;但是有一些低成本紧凑型的MCU上&#xff0c;一个IO口也是很珍贵的&#xff0c;因此&#xff0c;如果…

DevSecOps自动化在安全关键型软件开发中的实践、Helix QAC Klocwork等SAST工具应用

DevSecOps自动化对于安全关键型软件开发至关重要。 那么&#xff0c;什么是DevSecOps自动化&#xff1f;具有哪些优势&#xff1f;为何助力安全关键型软件开发&#xff1f;让我们一起来深入了解~ 什么是DevSecOps自动化&#xff1f; DevSecOps自动化是指在软件开发生命周期的各…

【ArcGISPro/GeoScenePro】解决常见的空间参考和投影问题

修复空间参考缺失的图像 数据 https://arcgis.com/sharing/rest/content/items/535efce0e3a04c8790ed7cc7ea96d02d/data 查看属性坐标 查看属性范围 范围值并不是零或接近于零。 这意味着栅格具有范围,因此其已正确进行

十二、Vue 路由

文章目录 一、简介二、安装与基本配置安装 Vue Router创建路由实例在应用中使用路由实例三、路由组件与视图路由组件的定义与使用四、动态路由动态路由参数的定义与获取动态路由的应用场景五、嵌套路由嵌套路由的概念与配置嵌套路由的应用场景六、路由导航<router - link>…

C#实现画图,及实现图像运动,C#中GDI+图形图像技术(Graphics类、Pen类、Brush类)C#之快速入门GDI+绘图 C#实现快速画图功能

下载源码 <-------- 在C#的世界里&#xff0c;GDI如同一位多才多艺的艺术家&#xff0c;以其强大的绘图能力&#xff0c;让开发者能够轻松地在应用程序中挥洒创意&#xff0c;绘制出丰富多彩的图形世界。GDI不仅支持基本的几何图形绘制&#xff0c;还能处理复杂的图像处理任…

Echart实现3D饼图示例

在可视化项目中&#xff0c;很多地方会遇见图表&#xff1b;echart是最常见的&#xff1b;这个示例就是用Echart&#xff0c; echart-gl实现3D饼图效果&#xff0c;复制即可用 //需要安装&#xff0c;再引用依赖import * as echarts from "echarts"; import echar…

Devart dotConnect发布全新版本,支持EF Core 9、完全兼容 .NET 9 等!

dotConnect &#xff08;最新版dotConnect Universal试用下载&#xff09;是Devart旗下一种基于 ADO.NET 架构构建的增强型数据连接解决方案&#xff0c;也是一个采用多项创新技术的开发框架。dotConnect 包含面向主要数据库和流行云应用程序的高性能数据提供程序&#xff0c;并…

借助 FinClip 跨端技术探索鸿蒙原生应用开发之旅

在当今数字化浪潮汹涌澎湃的时代&#xff0c;移动应用开发领域正经历着深刻的变革与创新。鸿蒙操作系统的崛起&#xff0c;以其独特的分布式架构和强大的性能表现&#xff0c;吸引了众多开发者的目光。而FinClip 跨端技术的出现&#xff0c;为开发者涉足鸿蒙原生应用开发提供了…

UE5.3 虚幻引擎 Windows插件开发打包(带源码插件打包、无源码插件打包)

0 引言 随着项目体量的增大&#xff0c;所有代码功能都放一起很难管理。所以有什么办法可以将大模块划分成一个个小模块吗。当然有&#xff0c;因为虚幻引擎本身就遇到过这个问题&#xff0c;他的解决办法就是使用插件的形式开发。 例如&#xff0c;一个团队开发了文件I/O模块插…

如何轻松关闭 iPhone 上的 HEIC [HEIC 图像技巧]

您是否正在为关闭 iPhone 上的 HEIC 而烦恼&#xff1f;你不是一个人; Apple 的首选图像文件格式仍可能存在一些兼容性问题。当您与某人共享照片或尝试在Windows计算机上打开图像时&#xff0c;就会出现此问题。幸运的是&#xff0c;Apple 使关闭 HEIC iPhone 变得更加容易。 …

GRU-PFG:利用图神经网络从股票因子中提取股票间相关性

“MCI-GRU: Stock Prediction Model Based on Multi-Head Cross-Attention and Improved GRU” 论文地址&#xff1a;https://arxiv.org/pdf/2410.20679 摘要 金融市场因复杂性及大数据时代的来临&#xff0c;使得准确预测股票走势变得尤为重要。传统的时序分析模型&#xff0…

UE5失真材质

渐变材质函数&#xff1a;RadialGradientExponential&#xff08;指数径向渐变&#xff09; 函数使用 UV 通道 0 来产生径向渐变&#xff0c;同时允许用户调整半径和中心点偏移。 用于控制渐变所在的位置及其涵盖 0-1 空间的程度。 基于 0-1 的渐变中心位置偏移。 源自中心的径…

Go语言在实际项目中的应用:从RESTful API到日志监控 (十四)

Go语言在实际项目中的应用&#xff1a;从RESTful API到日志监控 &#x1f680; Go语言&#xff08;又叫Golang&#xff09;作为一种现代化的编程语言&#xff0c;凭借其简洁的语法和强大的性能&#xff0c;已经成为了很多企业技术栈的一部分。在实际项目中&#xff0c;Go不仅仅…