【数据结构】顺序表与ArrayList

  一、什么是顺序表

概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

如下图：

优点：访问速度比较快，在给定下标的情况下时间复杂度低至O(1)

因此，顺序表适用于经常进行 下标查找 或者 更新 的操作

那么下面我们就来试着自己实现一个顺序表MyArrayList，并实现基础的增删查改的操作吧

二、MyArrayList的实现

1、定义MyList接口

public interface MyList {
    // 新增元素,默认在数组最后新增
    void add(int data);
    // 在 pos 位置新增元素
    void add(int pos, int data);
    // 判定是否包含某个元素
    boolean contains(int toFind);
    // 查找某个元素对应的位置
    int indexOf(int toFind);
    // 获取 pos 位置的元素
    int get(int pos);
    // 给 pos 位置的元素设为 value -> 更新
    void set(int pos, int value);
    //删除第一次出现的关键字key
    void remove(int toRemove);
    // 获取顺序表长度
    int size();
    // 清空顺序表
    void clear();
    // 打印顺序表，
    void display();

    boolean isFull();
}

2、MyArrayList实现接口

1、定义成员变量与构造方法

    public int[] elem;
    public int usedSize;

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

2、添加元素add

（1）尾部添加元素

public void add(int data) {
        //判断是否满了，如果满了就扩容
        if(isFull()) {
            //扩容
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        this.elem[usedSize] = data;
        this.usedSize++;
    }

（2）指定下标添加元素

    public void add(int pos, int data) {
        try {
            checkPosOfAdd(pos);
        }catch (PosNotLegalException e) {
            e.printStackTrace();
        }
        if(isFull()) {
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        //移动元素
        for (int i = usedSize-1; i >= pos; i--) {
            elem[i+1] = elem[i];
        }
        //插入元素
        elem[pos] = data;
        usedSize++;
    }

     /*
     该方法来 判断 添加元素时 pos是否合法
     */
    private void checkPosOfAdd(int pos) throws PosNotLegalException{
        if(pos < 0 || pos > usedSize) {
            throw new PosNotLegalException("pos位置不合法!");
        }
    }

3、判断是否包含某个元素

    public boolean contains(int toFind) {
        //只需要寻找usedSize次
        for (int i = 0; i < usedSize; i++) {
            if(elem[i] == toFind) {
                return true;
            }
        }
        return false;
    }

4、查找某个元素对应的位置

public int indexOf(int toFind) {
        for (int i = 0; i < usedSize; i++) {
            if(elem[i] == toFind) {
                return i;
            }
        }
        return -1;
    }

5、获取或修改某一下标的值

注意：在获取或修改某一下标元素值时，要判断所给下标是否合法，如果不合法应给出相应的错误提示

（1）判断下标合法性

    private void checkPosOfGetAndSet(int pos) throws PosNotLegalException{
        if(pos < 0 || pos >= usedSize) {
            throw new PosNotLegalException("get/set获取元素的时候" +
                    "pos位置不合法！");
        }
    }

（2）获取

    public int get(int pos) {
        try {
            checkPosOfGetAndSet(pos);
        }catch (PosNotLegalException e) {
            e.printStackTrace();
        }
        return elem[pos];
    }

（3）修改

    public void set(int pos, int value) {
        try {
            checkPosOfGetAndSet(pos);
        }catch (PosNotLegalException e) {
            e.printStackTrace();
        }

        elem[pos] = value;
    }

7、删除某一下标元素的值

    public void remove(int toRemove) {
        //1、要查找是否存在要删除的关键字 toRemove
        int pos = indexOf(toRemove);
        if(pos == -1) {
            System.out.println("没有要删除的数字！");
            return;
        }
        for (int i = pos; i < usedSize-1; i++) {
            elem[i] = elem[i+1];
        }
        usedSize--;
    }

8、清空顺序表

    public void clear() {
        /*for (int i = 0; i < usedSize; i++) {
            elem[i] = null;
        }*/
        usedSize = 0;
    }

9、打印顺序表

    public void display() {
        for (int i = 0; i < usedSize; i++) {
            System.out.print(elem[i] +" ");
        }
        System.out.println();
    }

10、其它方法

    public int size() {
        return usedSize;
    }
    public boolean isFull() {
        return usedSize == elem.length;
    }
    public boolean isEmpty() {
        return usedSize == 0;
    }

三、ArrayList

1、简介

实际上像MyArrayList那样自己定义一个顺序表也是不难的，不过在java中已经帮我们写好了ArrayList类了，我们只需要会调用即可。像前文中编写的MyArrayList类只是为了让我们更好地去理解ArrayList的底层实现，从而在应用时可以更加得心应手。

注意：

1. ArrayList 是以泛型方式实现的，使用时必须要先实例化
2. ArrayList 实现了 RandomAccess 接口，表明 ArrayList 支持随机访问
3. ArrayList 实现了 Cloneable 接口，表明 ArrayList 是可以 clone 的
4. ArrayList 实现了 Serializable 接口，表明 ArrayList 是支持序列化的
5. 和 Vector 不同， ArrayList 不是线程安全的，在单线程下可以使用，在多线程中可以选择 Vector 或者CopyOnWriteArrayList
6. ArrayList 底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

2、构造

public static void main(String[] args) {
    // ArrayList创建，推荐写法
    // 构造一个空的列表
    List<Integer> list1 = new ArrayList<>();
    // 构造一个具有10个容量的列表
    List<Integer> list2 = new ArrayList<>(10);
    list2.add(1);
    list2.add(2);
    list2.add(3);
    // list2.add("hello"); // 编译失败，List<Integer>已经限定了，list2中只能存储整形元素
    // list3构造好之后，与list中的元素一致
    ArrayList<Integer> list3 = new ArrayList<>(list2);
    // 避免省略类型，否则：任意类型的元素都可以存放，使用时将是一场灾难
    List list4 = new ArrayList();
    list4.add("111");
    list4.add(100);
}

3、常见方法

public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    list.add("JavaSE");
    list.add("JavaWeb");
    list.add("JavaEE");
    list.add("JVM");
    list.add("测试课程");
    System.out.println(list);
    // 获取list中有效元素个数
    System.out.println(list.size());
    // 获取和设置index位置上的元素，注意index必须介于[0, size)间
    System.out.println(list.get(1));
    list.set(1, "JavaWEB");
    System.out.println(list.get(1));
    // 在list的index位置插入指定元素，index及后续的元素统一往后搬移一个位置
    list.add(1, "Java数据结构");
    System.out.println(list);
    // 删除指定元素，找到了就删除，该元素之后的元素统一往前搬移一个位置
    list.remove("JVM");
    System.out.println(list);
    // 删除list中index位置上的元素，注意index不要超过list中有效元素个数,否则会抛出下标越界异常
    list.remove(list.size()-1);
    System.out.println(list);
    // 检测list中是否包含指定元素，包含返回true，否则返回false
    if(list.contains("测试课程")){
        list.add("测试课程");
    }
    // 查找指定元素第一次出现的位置：indexOf从前往后找，lastIndexOf从后往前找
    list.add("JavaSE");
    System.out.println(list.indexOf("JavaSE"));
    System.out.println(list.lastIndexOf("JavaSE"));
    // 使用list中[0, 4)之间的元素构成一个新的SubList返回,但是和ArrayList共用一个elementData数组
    List<String> ret = list.subList(0, 4);
    System.out.println(ret);
    list.clear();
    System.out.println(list.size());
}

4、遍历

ArrayList 可以使用三方方式遍历： for 循环 + 下标、 foreach 、使用迭代器 
public static void main(String[] args) {
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);
// 使用下标+for遍历
    for (int i = 0; i < list.size(); i++) {
        System.out.print(list.get(i) + " ");
    }
    System.out.println();
// 借助foreach遍历
    for (Integer integer : list) {
        System.out.print(integer + " ");
    }
    System.out.println();
    Iterator<Integer> it = list.listIterator();
    while(it.hasNext()){
        System.out.print(it.next() + " ");
    }
    System.out.println();
}

注意：

1. ArrayList 最长使用的遍历方式是： for 循环 + 下标 以及 foreach
2. 迭代器是设计模式的一种，后序容器接触多了再给大家铺垫

5、扩容机制

ArrayList 是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容。以下是 ArrayList 源码中扩容方式： 
Object[] elementData; // 存放元素的空间
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 默认空间
private static final int DEFAULT_CAPACITY = 10; // 默认容量大小
public boolean add(E e) {
    ensureCapacityInternal(size + 1); // Increments modCount!!
    elementData[size++] = e;
    return true;
}
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
// overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// 获取旧空间大小
    int oldCapacity = elementData.length;
// 预计按照1.5倍方式扩容
    int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果用户需要扩容大小 超过 原空间1.5倍，按照用户所需大小扩容
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
// 如果需要扩容大小超过MAX_ARRAY_SIZE，重新计算容量大小
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
// 调用copyOf扩容
    elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
// 如果minCapacity小于0，抛出OutOfMemoryError异常
    if (minCapacity < 0)
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

总结：

1. 检测是否真正需要扩容，如果是调用 grow 准备扩容
2. 预估需要库容的大小
         初步预估按照1.5 倍大小扩容
         如果用户所需大小超过预估1.5 倍大小，则按照用户所需大小扩容
         真正扩容之前检测是否能扩容成功，防止太大导致扩容失败
3. 使用 copyOf 进行扩容

四、总结

顺序表的优点：

  • 适合下标查找和更新的场景

缺点：

  • 1、不方便进行插入和删除操作，因为要移动数组元素，最坏情况下时间复杂度会达到O(n)
  • 2、扩容可能会浪费空间，例如长度为100的顺序表放满了，这时插入1个元素，顺序表就会扩容1.5倍，即多50个位置但实际只存储了1个元素，造成空间浪费

那么本篇文章就到此为止了，如果觉得这篇文章对你有帮助的话，可以点一下关注和点赞来支持作者哦。作者还是一个萌新，如果有什么讲的不对的地方欢迎在评论区指出，希望能够和你们一起进步✊

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

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

相关文章

网络1--通信过程的理解

网络1--通信过程的理解

1.封装与解包 通信的过程就是不断的封装和解包的过程 封装即就是按照“应用”“传输” “网络” “链路” 层&#xff0c;封装给每一层都加上相应的包头&#xff08;每一层都有协议&#xff0c;&#xff09;解包就是接受到的包文被一层层去掉相对应的包头。 任何一层的协议都…
阅读更多...
ATFX汇市：日本央行或3万亿干预，日元升值势头显著

ATFX汇市：日本央行或3万亿干预，日元升值势头显著

​ATFX汇市&#xff1a;4月29日&#xff0c;USDJPY创出历史新高160.21&#xff0c;随后进入快速回落阶段。五个交易日&#xff0c;最低价触及151.86点&#xff0c;相比最高价暴跌835基点&#xff0c;约5.21%。同期的美元指数跌幅仅为0.96%&#xff0c;两者跌幅严重不匹配&#…
阅读更多...
【intro】图卷积神经网络（GCN）-续

【intro】图卷积神经网络（GCN）-续

本文为【intro】图卷积神经网络&#xff08;GCN&#xff09;-CSDN博客后续&#xff08;因为经验告诉我超过2w字编辑器就会卡……&#xff09; 第一部分还是进一步再看看GCN 图卷积神经网络GCN_哔哩哔哩_bilibili 回顾 图神经网络的基本原理就是把图中的节点编码映射成一个低…
阅读更多...
RabbitMQ是如何保证消息可靠性的？——Java全栈知识（16）

RabbitMQ是如何保证消息可靠性的？——Java全栈知识（16）

RabbitMQ 的消息不可靠也就是 RabbitMQ 消息丢失只会发生在以下几个方面&#xff1a; 生产者发送消息到 MQ 或者 Exchange 过程中丢失。Exchange 中的消息发送到 MQ 中丢失。消息在 MQ 或者 Exchange 中服务器宕机导致消息丢失。消息被消费者消费的过程中丢失。 大致就分为生…
阅读更多...
CANdela/Diva系列1--CANdela Studio的基本介绍

CANdela/Diva系列1--CANdela Studio的基本介绍

大家好&#xff0c;这个系列主要给大家介绍跟诊断相关的Vector 工具CANdela和Diva&#xff0c;首先介绍CANdela。 目录 1.CANdela的简介&#xff1a; 2.如何打开CANdela 工程&#xff1a; 3.CANdela工程的详细介绍&#xff1a; 3.1 工具栏的介绍&#xff1a; 3.2 工作树的…
阅读更多...
MobileNet网络详解

MobileNet网络详解

一、了解 网络亮点&#xff1a; 1、DW网络&#xff0c;大大减少运算量核参数数量 2、增加超参数&#xff1a;控制卷积层卷积核个数的超参数 &#xff0c;控制图像输入大小的超参数 &#xff0c;这两个超参数是人为设定的&#xff0c;不是机器学习到的。 二、DW卷积&#xff…
阅读更多...
通信录的动态版本

通信录的动态版本

一. 增加需求 在学习了动态开辟内存之后 我们对于通讯录产生了新的需求 要求我们做出一个动态增长的版本 即 随着我们储存联系人的增加 储存的空间增加 要求 &#xff1a; 1 初始空间为3 2 每次达到上限之后 扩容两个内存 二. 动手实施 我们首先要创建一个结构体 结构体…
阅读更多...
普洱茶泡多少茶叶才算淡茶?

普洱茶泡多少茶叶才算淡茶?

普洱茶淡茶一般放几克茶叶&#xff0c;品深茶官网根据多年专业研究与实践结果&#xff0c;制定了淡茶冲泡标准。在冲泡普洱茶淡茶时&#xff0c;茶叶的投放量是关键因素之一。淡茶冲泡标准旨在保持茶汤的清爽口感&#xff0c;同时充分展现普洱茶的独特风味。 根据《品深淡茶冲…
阅读更多...
uniapp日期区间选择器

uniapp日期区间选择器

uniapp日期区间选择器 在 uniapp 中创建一个简单的自定义日期范围的日期区间选择器&#xff1a; - 限制有效日期范围开始日期为 2024-01-01&#xff0c;结束日期为当日&#xff1b; - 默认日期区间为当日向前计算的7日区间&#xff1b; - 选择开始时间后&#xff0c;判断不可大…
阅读更多...
【Pytorch】6.torch.nn.functional.conv2d的使用

【Pytorch】6.torch.nn.functional.conv2d的使用

阅读之前应该先了解基础的CNN网络的逻辑 conv2d的作用 是PyTorch中用于执行二维卷积操作的函数。它的作用是对输入数据进行二维卷积操作&#xff0c;通常用于图像处理和深度学习中的卷积神经网络&#xff08;CNN&#xff09;模型。 conv2d的使用 我们先查看一下官方文档 inpu…
阅读更多...
【前端学习——正则】

【前端学习——正则】

https://www.bilibili.com/video/BV1da4y1p7iZ/?spm_id_from333.337.search-card.all.click&vd_source5cef5968d539682b683e7d01b00ad01b 学习网站 https://github.com/ziishaned/learn-regex/blob/master/translations/README-cn.md
阅读更多...
笔记本连接不上远程桌面，笔记本无法连接远程桌面的可能原因及解决方法

笔记本连接不上远程桌面，笔记本无法连接远程桌面的可能原因及解决方法

在使用远程桌面功能时&#xff0c;笔记本无法成功连接的情况可能由多种原因引起。为了有效地解决这个问题&#xff0c;我们需要逐一排查这些可能的原因&#xff0c;并采取相应的解决措施。 首先&#xff0c;网络连接稳定性是远程桌面连接成功的关键。请确保笔记本和远程计算机之…
阅读更多...
深入剖析Spring框架：推断构造方法与@Bean注解的内部机制

深入剖析Spring框架：推断构造方法与@Bean注解的内部机制

你好&#xff0c;我是柳岸花开。 Spring框架作为Java开发中广泛使用的基础架构&#xff0c;其设计精巧、功能强大&#xff0c;尤其是其依赖注入&#xff08;DI&#xff09;和控制反转&#xff08;IoC&#xff09;特性&#xff0c;极大地提高了代码的可维护性和可测试性。本文将…
阅读更多...
125.两两交换链表中的节点（力扣）

125.两两交换链表中的节点（力扣）

题目描述 代码解决及思路 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), …
阅读更多...
基于TF的简易关键字语音识别

基于TF的简易关键字语音识别

⚠申明&#xff1a; 未经许可&#xff0c;禁止以任何形式转载&#xff0c;若要引用&#xff0c;请标注链接地址。 全文共计10182字&#xff0c;阅读大概需要10分钟 &#x1f308;更多学习内容&#xff0c; 欢迎&#x1f44f;关注&#x1f440;【文末】我的个人微信公众号&#…
阅读更多...
[Scrcpy]数据线连接安卓手机投屏windows电脑[win控制安卓手机]比Samsung Dex好用

[Scrcpy]数据线连接安卓手机投屏windows电脑[win控制安卓手机]比Samsung Dex好用

配置好&#xff0c;只需要两步即可完成安卓手机投屏windows 第一步&#xff1a;usb线连接windows电脑 第二步&#xff1a;cmd输入投屏命令srccpy 搞定 前言/背景 一些视频资料只能下载到手机&#xff0c;很不喜欢手机那么小屏幕播放&#xff0c;播放很不方便 在家的话可以投…
阅读更多...
上位机图像处理和嵌入式模块部署（树莓派4b镜像烧录经验总结）

上位机图像处理和嵌入式模块部署（树莓派4b镜像烧录经验总结）

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 陆陆续续也烧录了好多次树莓派的镜像了&#xff0c;这里面有的时候很快&#xff0c;有的时候很慢。特别是烧录慢的时候&#xff0c;也不知道是自己…
阅读更多...
Unity EventSystem入门

Unity EventSystem入门

概述 相信在学习Unity中&#xff0c;一定有被UI事件困扰的时候把&#xff0c;当添加UICanvas的时候&#xff0c;Unity会为我们自动添加EventSystem&#xff0c;这个是为什么呢&#xff0c;Unity的UI事件是如何处理的呢&#xff0c;在使用各个UI组件的时候&#xff0c;一定有不…
阅读更多...
流量暴涨！抖音+快手+小红书获客攻略！

流量暴涨！抖音+快手+小红书获客攻略！

在数字营销的海洋中&#xff0c;抖音、快手和小红书无疑是三座巨大的灯塔&#xff0c;照亮了品牌和个人获取流量的道路。这些平台不仅拥有庞大的用户基础&#xff0c;而且其独特的算法和社交特性让获客变得更加高效而精准。接下来&#xff0c;让我们深入探讨如何通过这三个平台…
阅读更多...
linux系统 虚拟机的安装详细步骤

linux系统 虚拟机的安装详细步骤

window&#xff1a; (1) 个人&#xff1a;win7 win10 win11 winxp (2)服务器&#xff1a;windows server2003 2008 2013 linux&#xff1a; (1)centos7 5 6 8 (2)redhat (3)ubuntu (4)kali 什么是linux: 主要是基于命令来完成各种操作&#xff0c;类似于DO…
阅读更多...
最新文章

Copyright @ 2022~2023