当前位置： 首页 > article >正文

数据结构-ArrayLIst-一起探索顺序表的底层实现

article 2025/1/16 6:44:11

各位看官早安午安晚安呀

如果您觉得这篇文章对您有帮助的话

欢迎您一键三连，小编尽全力做到更好
欢迎您分享给更多人哦

大家好，我们今天来学习java数据结构的第一章ArrayList（顺序表）

1.ArrayList的概念

那小伙伴就要问了线性表到底是什么呢？
线性表 （ linear list ） 是 n 个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列...（我们后续都会进行讲解）
线性表首先是一个序列，也就是说，元素之间是有顺序的，如果元素存在多个，那么第一个元素无前驱。最后一个元素无后驱。其他每个元素都必须有一个前驱和后驱。
例如：
usedSize这个变量是非常重要的，我们的增删查改都要用到

1.2ArrayList的模拟实现

import java.util.Arrays;

public class MyArrayList {

    private int []elem;//用来存放数据
    private int usedSize;//非常重要，代表当前顺序表当中的有效数据个数

    private static final int DEFAULT_SIZE = 2;

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

    // 新增元素,默认在数组最后新增
    public void add(int data) {
        if(elem.length == usedSize){
            elem = Arrays.copyOf(elem,elem.length*2);
        }
        elem[usedSize] = data;
        this.usedSize++;//一定不要忘记加
    }
    // 在 pos 位置新增元素
    public void add(int pos, int data) {//只要带pos的都要进行检查
        if(checkPos(pos) ==false ){
            return;
        }
            if (elem.length == usedSize) {
            elem = Arrays.copyOf(elem, elem.length * 2);
        }
            //下面这种写法就错误了，导致pos后面的值都是pos位置的值
        /*for (int i = pos; i < usedSize -1; i++) {
            elem[i+1] = elem[i];
        }*/
        //应该从后往前
        for (int i = usedSize-1 ; i >= pos; i--) {
            elem[i+1] = elem[i];
        }
        elem[pos] = data;
        usedSize++;
    }

    /*public void delete(int pos){
        if(checkPos(pos) == false)
        if(this.usedSize == 0){
            System.out.println("数组里面没有元素了");
            return;
        }
        for (int i = 0; i < usedSize - 1; i++) {
            elem[i] = elem[i+1];
        }
    }
*/

    // 判定是否包含某个元素
    public boolean contains(int toFind) {//啥意思
        for (int i = 0; i < usedSize; i++) {
            if(elem[i] == toFind ) //这里是int类型，所以你能够直接比较，其他类型的话，要重写equals方法
                return true;
        }
        return false;
    }

    // 查找某个元素对应的位置
    public int indexOf(int toFind) {
        for (int i = 0; i < usedSize; i++) {
            if(elem[i] == toFind)
            return i;
        }
        System.out.println("没有你要找的值");
        return -1;
    }

    public boolean checkPos(int pos){
        if( pos < 0 || pos >= usedSize){
            System.out.println("下标错误");
            return false;
        }
        return true;
    }
    // 获取 pos 位置的元素
    public int get(int pos) {

        if(checkPos(pos) == false){
            return -1;
        }
        return elem[pos];
    }

    // 给 pos 位置的元素设为 value
    public void set(int pos, int value) {
        if(checkPos(pos) == false){
            return;
        }
        elem[pos] = value;
    }

    //删除第一次出现的关键字key
    public void remove(int data) {
        int index = this.indexOf(data);
        if(index == -1){
            System.out.println("没有这个数据");
            return;
        }
        for (int i = data; i < usedSize - 1; i++) {
            elem[i] = elem[i+1];
        }
       //如果是引用类型的话： elem[index] = null;
        this.usedSize--;

    }

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

    // 清空顺序表
    public void clear() {
        this.usedSize = 0;
        //但是如果是引用类型的话
/*
        for (int i = 0; i < usedSize; i++) {
            elem[i] = null;
            记得全部置为空
            引用类型的话，删除也要置为null
        }
*/
    }

    // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
    public void display() {
        for (int i = 0; i < usedSize; i++) {
            System.out.print(this.elem[i] + " ");
        }
    }
}

目前我们自己实现了顺序表这种结构，以后用到的时候，Java已经为我们提供好了

ArrayList（就是一个普通的类实现了List接口）

（自己看一下方法）（ArrayLIst里面的方法，底层方法）（我们可以看出来ArrsyList底层的数组我们在实例化对象时也是默认长度为我们的常量值，有效元素个数非常重要，我们增加删除元素等方法都要用的）

2：构造方法

我们要了解一个类首先要了解他的构造方法

ArrayList<E>中的E就表示列表中存储的元素的类型

ArrayList

2.1:构造方法一，三

       ArrayList<Integer> list = new ArrayList<>();   这种能用的方法更多
       List<Integer> list = new ArrayList<>();    一般我们用这一种，向上转型，动态绑定的等等，你俩用哪个主要看自己业务场景
       ArrayList<Integer> list = new ArrayList<>(15)

我们可以看到默认数组长度是10，前面源码图解上有

2.2:构造方法二

然后我把list1指定的类型换成Integer就解决问题了！

大家也可以看到我明明对于list3只add了一次但是，打印出来的值却把list1数组里面的内容也拷贝过来了（拷贝在外面构造方法那一步就完成了）

2.3:ArrayList常见操作

public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(1,4);
        System.out.println(list);//到这里是【1,4,2，3】

        list.remove(1);//这两个老是搞混，这个是删除1小标的值
        list.remove(new Integer(1));//要删除1这个元素的值一定要用这种方法，因为这个参数是Object类型的
        System.out.println(list);//到这里是【2,3】

        // list.get(2);//这里会报一个数组越界异常，就是用来和UsedSize比较

        list.add(99);
        list.add(100);
        list.add(101);
        boolean isFalse = list.contains(new Integer(100));//这里最好用Integer类型的
        System.out.println(isFalse);//true

        List<Integer> list1 = list.subList(1,4);//左闭右开
        System.out.println(list1);

        list.set(1,200);
        System.out.println(list);
        System.out.println(list1);
        //list1得到的是从list数组里面的引用，只要改变其中一个元素的值，另一个也会改变

        list.clear();
        System.out.println(list);
        //全部清除
    }

2.4:ArrayList的三种遍历

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();
//ListIterator<Integer> it = list.listIterator();也可以
//ListIterator是Iterator的子类
while(it.hasNext()){
System.out.print(it.next() + " ");
}
System.out.println();
}
注意：
1. ArrayList 最长使用的遍历方式是： for 循环 + 下标 以及 foreach
2. 迭代器是设计模式的一种，后续博客我会继续讲解

2.5：ArrayList的扩容机制的缺陷

ArrayList是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容。以下是ArrayList源码中扩容方式
【 总结 】
1. 检测是否真正需要扩容，如果是调用 grow 准备扩容
2. 预估需要库容的大小
初步预估按照 1.5 倍大小扩容 ，如果用户所需大小超过预估1.5 倍大小，则按照用户所需大小扩容
真正扩容之前检测是否能扩容成功，防止太大导致扩容失败
3. 使用 copyOf 进行扩容

3：杨辉三角

力扣杨辉三角

实现：

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Test {
    public static void main(String[] args) {
        int num = 5;
        List<Integer> row = new ArrayList<>();
        List<List<Integer>> ret = new ArrayList<>();
        row.add(1);
        ret.add(row);
        for (int i = 1; i < num; i++) {
            List<Integer> curRow1 = new ArrayList<>();
            curRow1.add(1);//每行的第一个元素都是1

            List<Integer> previousRow = ret.get(i - 1);

            for (int j = 1; j < i; j++) {
                Integer x = previousRow.get(j) + previousRow.get(j - 1);
                curRow1.add(x);

            }
            curRow1.add(1);//每行的最后一个元素也都是1

            ret.add(curRow1);//把这一行的数组加进去
        }
        for (List<Integer>list:ret   //遍历数组
             ) {
            System.out.println(list);
        }
        System.out.println("============================");
        Iterator<List <Integer>> it = ret.listIterator();//使用迭代器遍历数组
//ListIterator<Integer> it = list.listIterator();也可以
//ListIterator是Iterator的子类
        while(it.hasNext()){
            System.out.print(it.next() + " ");
            System.out.println();
        }

    }
    }

上述就是数据结构-ArrayLIst-数组的深入包装 的全部内容了，能看到这里相信您一定对小编的文章有了一定的认可，数据结构的出现让我们对于数据的组织的利用有了更加方便的使用~~

有什么问题欢迎各位大佬指出
欢迎各位大佬评论区留言修正

您的支持就是我最大的动力​​​！！！！


http://www.kler.cn/a/504654.html

相关文章：

  • 微信小程序集成Vant Weapp移动端开发的框架
  • 39.【4】CTFHUB web sql 布尔注入
  • 《解锁鸿蒙Next系统人工智能语音助手开发的关键步骤》
  • ESP32,uart安装驱动uart_driver_install函数剖析，以及intr_alloc_flags 参数的意义
  • 赤店商城系统点餐小程序多门店分销APP共享股东h5源码saas账号独立版全插件全开源
  • 数据存储与信息技术领域 - 磁带技术：企业用磁带与音乐磁带
  • 二手车交易系统的设计与实现(代码+数据库+LW)
  • 抖音ip属地没有手机卡会显示吗
  • sql Server服务区cpu占用率高,原因分析
  • 【基于轻量型架构的WEB开发】课程 实验一 mybatis操作 Java EE企业级应用开发教程 Spring+SpringMVC+MyBatis
  • Java爬虫——使用Spark进行数据清晰
  • UnityDots学习（二）
  • Vue computed属性原理及其惰性求值特点
  • ros2-6.4.4 两轮差速控制机器人(问题解决）
  • 集成学习算法
  • RabbitMQ确保消息可靠性
  • LSTM火灾温度预测（Pytorch版本）
  • 【JavaScript】基础内容，HTML如何引用JavaScript, JS 常用的数据类型
  • Ubuntu创建AndroidStudio快捷启动图标
  • HTML拖拽功能（纯html5+JS实现）
  • 极限竞速 地平线5“d3dx12_43.dll”文件丢失或错误导致游戏运行异常如何解决？windows系统DLL文件修复方法
  • 智汇云舟参编《城市轨道交通安全防范系统技术要求》国标正式发布
  • 【原创】大数据治理入门（2）《提升数据质量：质量评估与改进策略》入门必看 高赞实用
  • 面试之《new关键字》
  • python创建pdf水印，希望根据文本长度调整水印字体大小，避免超出页面
  • [Qt]常用控件介绍-输入类控件-QSpinBox、DateTimeEdit、Dial、Silder控件