List与ArrayList

2023-09-13 17:57:28

目录

一、List及其使用

        1.1 List的概念

        1.2 常见接口的介绍

        1.3 List的使用

二、线性表和顺序表

        2.1 线性表

        2.2 顺序表

三、ArrayList介绍

四、ArrayList的使用

        4.1 ArrayList构造

        4.2 ArrayList的常用方法

        4.3 ArrayList的遍历

        4.4 ArrayList的扩容机制

五、ArrayList的具体使用

        5.1 简单洗牌算法

        5.2 杨辉三角

六、ArrayList的问题

一、List及其使用

        1.1 List的概念

        在集合框架中，List是一个接口，继承自Collection。
         

        Collection也是一个接口，该接口中规范了后序容器中常用的一些方法：
                

        Iterable也是一个接口，表示实现该接口的类是可以逐个元素进行遍历的：

                 

        从数据结构角度看，List就是一个线性表，即n个具有相同类型元素的有限序列，在该序列上可以执行增删改查以及变量等操作。

        1.2 常见接口的介绍

        List中有许多方法：

        

        虽然方法多，但常用方法如下：

方法解释
boolean add(E e)尾插 e
void add(int index, E element)将 e 插入 index 位置
boolean addAll(Collection<? extends E> c)尾插 c 中的元素
E remove(int index)删除 index 位置元素
boolean remove(Object o)删除遇到的第一个 o
E get(int index)获取下标 index 位置的元素
E set(int index, E element)将 index 位置的元素设置为element
void clear()清空
boolean contains(Object o)判断 o 是否包含在线性表中
int indexOf(Object o)返回第一个 o 的下标
int lastIndexOf(Object o)返回最后一个 o 的下标
List<E> subList(int fromIndex, int toIndex)截取部分list

        1.3 List的使用

                List是个接口，并不能直接用来实例化。如果要使用，必须去实例化List的实现类。在集合框架中，ArrayList和LinkedList都实现了List接口。

二、线性表和顺序表

        2.1 线性表

        线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种广泛使用的数据结构，常见线性表有：顺序表、链表、栈、队列......        

        2.2 顺序表

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

public interface IList {
    //新增元素,默认在数组最后新增
    public void add(int data);
    // 在 pos 位置新增元素
    public void add(int pos, int data);
    // 判定是否包含某个元素
    public boolean contains(int toFind) ;
    // 查找某个元素对应的位置
    public int indexOf(int toFind);
    // 获取 pos 位置的元素
    public int get(int pos);
    // 给 pos 位置的元素设为 value  更新
    public void set(int pos, int value);
    //删除第一次出现的关键字key
    public void remove(int toRemove) ;
    // 获取顺序表长度
    public int size();
    // 清空顺序表
    public void clear() ;
    // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
    public void display();
    boolean isFull();
    public boolean isEmpty();
}
public class MyArrayList implements IList{
    private  int[] elem;
    private  int usedSize;
    //顺序表默认大小
    private static  int DEFAULT_Size=10;

    public MyArrayList(){
        elem=new int[DEFAULT_Size];
    }
    public  MyArrayList(int capacity){
        elem=new int[capacity];
        DEFAULT_Size=capacity;
    }

    //添加一个数据
    @Override
    public void add(int data) {
        chackCapacity();
        this.elem[usedSize]=data;
        this.usedSize++;
    }
    //检查容量
    private void chackCapacity(){
        if(isFull()){
            elem= Arrays.copyOf(elem,elem.length*2);
        }
    }

    //在pos插入一个数据
    @Override
    public void add(int pos, int data) {
        try {
            chackPosOnAddOrGetOrSet(pos);
        }catch (PosError e){
            e.printStackTrace();
            return;
        }
        chackCapacity();
        for (int i = usedSize; i >pos ; i++) {
            elem[i]=elem[i-1];
        }
        elem[pos]=data;
        usedSize++;
    }
    /*检查pos的合法性*/
    private void chackPosOnAddOrGetOrSet(int pos) throws PosError{
        if(pos<0||pos>=this.usedSize)
            throw new PosError("下标异常"+pos);
    }
    //判断顺序表是否包含toFind
    @Override
    public boolean contains(int toFind) {
        if(isEmpty())
            return false;
        for (int x:elem) {
            if(x==toFind)
                return true;
        }
        return false;
    }
    //获取toFing对应的下标
    @Override
    public int indexOf(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if(elem[i]==toFind)
                return i;
        }
        return -1;
    }
    //获取pos下标对应的元素值
    @Override
    public int get(int pos) {
        if(isEmpty())
            return -1;
        chackPosOnAddOrGetOrSet(pos);
        return this.elem[pos];
    }
    //设置下标为pos的元素值为value
    @Override
    public void set(int pos, int value) {
        chackPosOnAddOrGetOrSet(pos);
        elem[pos]=value;
    }
    //删除toRemove
    @Override
    public void remove(int toRemove) {
        int index=indexOf(toRemove);
        if(index<0){
            System.out.println("要删除的数不存在");
            return;
        }
        for(int i=index;i<this.usedSize-1;i++){
            this.elem[i]=this.elem[i+1];
        }
        this.usedSize--;
    }
    //获取当前顺序表的大小
    @Override
    public int size() {
        return this.usedSize;
    }
    //清空
    @Override
    public void clear() {
        for (int i = 0; i < usedSize; i++) {
            set(i,0);
        }
    }
    /*遍历顺序表当中的元素*/
    @Override
    public void display() {
        if(isEmpty()){
            throw new MyArrayIsEmpty("顺序表是空的");
        }
        for(int i=0;i<elem.length;i++){
            System.out.println(this.elem[i]+" ");
        }
        System.out.println();
    }
    /*判断顺序表是否已满*/
    @Override
    public boolean isFull() {
        /*if(usedSize==DEFAULT_Size)
                return true;
        else
            return false;*/
        return  usedSize==DEFAULT_Size;
    }

    @Override
    public boolean isEmpty() {
        return elem.length==0;
    }
}
public class MyArrayIsEmpty extends RuntimeException{
    public MyArrayIsEmpty(String massage){
        super(massage);
    }
}
public class PosError extends RuntimeException{
    public PosError(String massage){
        super(massage);
    }
}

三、ArrayList介绍

        在集合框架中，ArrayList是一个普通的类，实现了List接口，具体框架如下：
        

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

四、ArrayList的使用

        4.1 ArrayList构造

方法解释
ArrayList()无参构造
ArrayList(Collection<? extends E> c)利用其他 Collection 构建 ArrayList
ArrayList(int initialCapacity)指定顺序表初始容量
public static void main(String[] args) {
    //创建一个空列表 ArrayList()  默认size为0
    ArrayList<Integer> list1=new ArrayList<>();

    //创建一个容量为10的列表  ArrayList(int initialCapacity)创建指定容量的列表
    //ArrayList<Integer> 指定存放的元素类型为Integer
    ArrayList<Integer> list2=new ArrayList<>(10);
    list1.add(1);//第一次add时，底层数组size为10
    list1.add(2);
    list1.add(3);

    //ArrayList(Collection<? extends E> c)
    //参数c必须实现了Collection接口，是E的子类或E本身类型
    //list3的元素与list2相同
    ArrayList<Integer> list3=new ArrayList<>(list2);
}

        使用不带参数newArrayList对象时，默认size为0，当第一次add时，底层数组size为10，当数组需要扩容时，是以当前数组size的1.5倍进行扩容。

        4.2 ArrayList的常用方法

        ArrayList提供方法比较多，但常用方法如下所示：

方法解释
boolean add(E e)尾插 e
void add(int index, E e)将 e 插入到 index位置
boolean addAll(Collection<? extends E> c)尾插 c 中的元素
E remove(int index)删除 index位置的元素
boolean remove(Object o)删除遇到的第一个 o
E get(int index)获取下标 index 位置的元素
E set(int index, E e)将下标 index位置元素设为 e
void clear()清空
boolean contains(Object o)判断 o是否在线性表中
int indexOf(Object o)返回第一个 o所在下标
int lastIndexOf(Object o)返回最后一个 o所在下标
List<E> subList(int fromIndex, int toIndex)截取部分list
public static void main(String[] args) {
    ArrayList<Integer> list1=new ArrayList<>(10);
    list1.add(1);
    list1.add(2);
    list1.add(3);
    list1.add(4);

    System.out.println(list1);// 1 2 3 4
    //获取list1中有效元素的个数并打印
    System.out.println(list1.size());//4

    System.out.println("====");
    //获取和设置index位置的元素
    System.out.println(list1.get(2));//3
    list1.set(2,99);
    System.out.println(list1.get(2));//99

    System.out.println("====");
    //在index位置插入value
    list1.add(2,88);
    System.out.println(list1);//1 2 88 99 4

    System.out.println("====");
    //删除指定元素
    list1.remove(new Integer(88));
    System.out.println(list1);//1 2 99 4
    //删除index位置的元素   index不能超过list1的有效元素个数
    list1.remove(2);
    System.out.println(list1);// 1 2 4

    System.out.println("====");
    //检查list1中是否包含value
    System.out.println(list1.contains(99));//false
    System.out.println(list1.contains(2));//true

    System.out.println("====");
    list1.add(2);
    list1.add(1);
    System.out.println(list1);//1 2 4 2 1
    //获取第一次出现value的下标
    System.out.println(list1.indexOf(1));//0
    //获取最后一次出现value的下标
    System.out.println(list1.lastIndexOf(1));//4

    System.out.println("====");
    //截取list1   List<E> subList(int fromIndex, int toIndex)
    List<Integer> list2=list1.subList(1,3);
    System.out.println(list2);//2 4

    //截取的list2并没有分配内存，只是list2这个引用指向下标为1~2的元素
    list2.set(0,10);
    System.out.println(list1);// 1 10 4 2 1
    System.out.println(list2);//10  4
}

        

        4.3 ArrayList的遍历

        ArrayList 可以使用三方方式遍历：for循环+下标、foreach、使用迭代器。

public static void main(String[] args) {
    ArrayList<Integer> list=new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    //for循环遍历
    for(int i=0;i<list.size();i++){
        System.out.print(list.get(i)+" ");
    }
    System.out.println();
    //foreach遍历
    for (Integer x:list){
        System.out.print(x+" ");
    }
    System.out.println();
    //迭代器遍历
    Iterator<Integer> it=list.iterator();
    while (it.hasNext()){
        System.out.print(it.next()+" ");
    }
}

        4.4 ArrayList的扩容机制

        ArrayList是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容。以下是ArrayList源码中扩容方式：

        检测是否需要扩容，如果需要调用grow函数；估计容量大小，初步估计按1.5倍扩容，若用户所需超过估计的1.5倍大小，按用户所需大小扩容；扩容前进行检测是否能扩容；使用copyOf进行扩容。

五、ArrayList的具体使用

        5.1 简单洗牌算法

public class Card {
    //花色
    private String design_and_color;
    //数值
    private int value;

    public Card(String design_and_color, int value) {
        this.design_and_color = design_and_color;
        this.value = value;
    }

    @Override
    public String toString() {
        return "花色："+design_and_color+" 数值："+value;
    }

    public String getDesign_and_color() {
        return design_and_color;
    }

    public void setDesign_and_color(String design_and_color) {
        this.design_and_color = design_and_color;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }
}
public class CardText {
    //花色集合  红桃 ♥   黑桃  ♠   方块♦  梅花 ♣
    public static final String[] design_and_colors= {"♥", "♣", "♠", "♦"};
    //买一副牌
    public static List<Card> buyCard(){
        /*没有大小王，共52张牌，J Q K 分别用11 12 13代替*/
        List<Card> card=new ArrayList<>(52);
        for (int i = 0; i < 4; i++) {
            for(int j=1;j<=13;j++){
                Card card1=new Card(design_and_colors[i],j);
                card.add(card1);
            }
        }
        return card;
    }
    //洗牌
    public static  void brushCard(List<Card> cards){
        for (int i = 51; i >0 ; i--) {
            Random random=new Random(i);
            int j=random.nextInt(i);
            swap(cards,i,j);
        }
    }
    //交换两张牌
    public  static <j> void swap(List<Card> cards, int i,int j){
        Card tmp=cards.get(i);
        cards.set( i,cards.get(j));
        cards.set( j,tmp);

    }
    public static void main(String[] args) {
        //取一副牌
        List<Card> card=buyCard();
        System.out.println("拿到一副牌：");
        System.out.println(card);
        //洗牌
        brushCard(card);
        System.out.println("洗牌后：");
        System.out.println(card);
        //发牌 三人轮流拿牌，每人五张
        List<List<Card>> hands=new ArrayList<>();//hands代表三人各自取的牌
        hands.add(new ArrayList<>());//new ArrayList<>()代表每人手中的牌的集合
        hands.add(new ArrayList<>());
        hands.add(new ArrayList<>());
        for(int i=0;i<5;i++){
            for(int j=0;j<3;j++){
                hands.get(j).add(card.remove(0));
            }
        }
        System.out.println("第一个人手中的牌：");
        System.out.println(hands.get(0));

        System.out.println("第二个人手中的牌：");
        System.out.println(hands.get(1));

        System.out.println("第三个人手中的牌：");
        System.out.println(hands.get(2));
        System.out.println("剩余的牌：");
        System.out.println(card);
    }
}

        5.2 杨辉三角

               杨辉三角题目链接

public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> list=new ArrayList<>();
    //设置第一行
    List<Integer> list2=new ArrayList<>();
    list2.add(1);
    list.add(list2);
    //设置剩余行
    for(int i=1;i<numRows;i++){
        //设置当前行
        List<Integer> tmp=new ArrayList<>();
        //设置当前行第一个数
        tmp.add(1);

        //获取前一行
        List<Integer> preRow=list.get(i-1);
        //设置当前行其他数
        for(int j=1;j<i;j++){
            int a=preRow.get(j-1)+preRow.get(j);
            tmp.add(a);
        }
        //设置当前行最后一个数
        tmp.add(1);

        list.add(tmp);
    }
    return list;
}

六、ArrayList的问题

        1. ArrayList底层使用连续的空间，任意位置插入或删除元素时，需要将该位置后序元素整体往前或者往后移动，时间复杂度为O(N)。

        2. 增容需要申请新空间，拷贝数据，释放旧空间，有不小的消耗。

        3. 增容一般是呈1.5倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到150，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了45个数据空间。
 

更多推荐

服务器如何提供性能呢？

服务器如何提供性能呢？一、将服务器虚拟化如果同期拥有多个项目，增加额外服务器会显得浪费，成本费用也会大幅度上升，这时不妨通过技术将其划分成多个虚拟空间，而每个空间又可以使用不同操作系统，运行不同应用程序，使得符合项目要求。这种方式通常能增加当前利用率，而不必投资额外的服务器。比如虚拟主机、VPS、云服务器等，就是服务器

spark 数据倾斜优化总结

一、数据倾斜产生原因数据倾斜就是部分task承担了过多的计算任务，导致整个stage都被卡。可能产生数据倾斜的场景如下操作场景join其中一个表比较小，但key值少join大表与大表，但key值中存在过多的特殊值，如0或nulljoinon条件包含key值过滤逻辑，导致部分数据被保留，部分被过滤，最终节点分布不均joi

2023_Spark_实验七：Scala函数式编程部分演示

1、Scala中的函数在Scala中，函数是“头等公民”，就和数字一样。可以在变量中存放函数，即：将函数作为变量的值（值函数）。defmyFun1(name:String):String="Hello"+nameprintln(myFun1("Tom"))defmyFun2():String="HelloWorld"/

大数据-kafka学习笔记

KafkaKafka是一个分布式的基于发布/订阅模式的消息队列（MessageQueue），主要应用于大数据实时处理领域。Kafka可以用作Flink应用程序的数据源。Flink可以轻松地从一个或多个Kafka主题中消费数据流。这意味着您可以使用Kafka来捕获和传输实时数据，并将其发送到Flink进行进一步处理。Fl

创建第一个MyBatis框架--保姆级教学

文章目录前言一、创建一个空的mybatis项目二、创建一个Maven模块三、各个文件的配置四、总结前言在idea上创建我的第一个MyBatis框架一、创建一个空的mybatis项目1、new一个新的项目2、选择最下面，创建一个空项目3、为空项目取一个名字,位置可以自己选4、点击完成后，开始配置以下版本，两个版本得一样，

HDMI字符显示实验

FPGA教程学习第十五章HDMI字符显示实验文章目录FPGA教程学习前言实验原理程序设计像素点坐标模块字符叠加模块实验结果知识点总结前言在HDMI输出彩条的基础上输出osd叠加信息。实验原理实验通过字符转换工具将字符转换为16进制coe文件存放到单端口的ROMIP核中，再从ROM中把转换后的数据读取出来显示到HDMI上

高云FPGA系列教程（9）：cmd-parser串口命令解析器移植

文章目录@[toc]cmd-parser库简介cmd-parser库源码获取GW1NSR-4C移植cmd-parser实际测试cmd-parse命令解析器优化本文是高云FPGA系列教程的第9篇文章。上一篇文章介绍片上ARMCortex-M3硬核处理器串口外设的使用，演示轮询方式和中断方式接收串口数据，并进行回环测试。本

千兆以太网硬件设计及链路层 MAC 协议格式

以太网系列文章：（1）千兆以太网硬件设计及链路层MAC协议格式（2）千兆以太网网络层ARP协议的原理与FPGA实现（3）CRC校验代码原理文章目录前言一、以太网MAC层接口介绍1.MII接口2.GMII接口3.RGMII接口二、以太网（MAC）帧协议介绍前言从本章开始，将分享千兆以太网设计的相关知识。将为大家分享千兆以

基于FPGA的图像sobel锐化实现,包括tb测试文件和MATLAB辅助验证

目录1.算法运行效果图预览2.算法运行软件版本3.部分核心程序4.算法理论概述5.算法完整程序工程1.算法运行效果图预览将FPGA的仿真结果导入到matlab显示图像效果2.算法运行软件版本MATLAB2022a,vivado2019.23.部分核心程序.................................

【洛谷 P1364】医院设置 题解（图论+深度优先搜索）

医院设置题目描述设有一棵二叉树，如图：其中，圈中的数字表示结点中居民的人口。圈边上数字表示结点编号，现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻接点之间的距离为111。如上图中，若医院建在111处，则距离和=4+12+2×20+2×40=136=4+12+2\times20+2\ti

分布式调度 Elastic-job

分布式调度Elastic-job1.概述1.1什么是任务调度我们可以思考一下下面业务场景的解决方案:某电商平台需要每天上午10点，下午3点，晚上8点发放一批优惠券某银行系统需要在信用卡到期还款日的前三天进行短信提醒某财务系统需要在每天凌晨0:10分结算前一天的财务数据，统计汇总以上场景就是任务调度所需要解决的问题任务调

热文推荐
  1. 三分钟图解事务隔离级别

    详细见：三分钟图解事务隔离级别，看一遍就懂数据库中事务指的是什么“锁"是数据库系统区别于文件系统的一个关键特性，其对象是事务，用来锁定的是数据库中的对象，如表、页、行等。锁确实提高了并发性，但是却不可避免地存在一些潜在的并发一致性问题。不过好在锁只会带来四种问题（丢失更新、脏读、不可重复读、幻读），如果可以防止这四种情

  2. 项目设计集合（人工智能方向）：助力新人快速实战掌握技能、自主完成项目设计升级，提升自身的硬实力（不仅限NLP、知识图谱、计算机视觉等领域）

    优质项目专栏：提升自身的硬实力：汇总有意义的项目设计集合，助力新人快速实战掌握技能，助力用户更好利用CSDN平台，自主完成项目设计升级，提升自身的硬实力。专栏订阅：项目大全提升自身的硬实力资料合集更优惠第一期资料合集：https://download.csdn.net/download/sinat_39620217/8

  3. 一文详解 requests 库中 json 参数和 data 参数的用法

    在requests库当中，requests请求方法，当发送post/put/delete等带有请求体的请求时，有json和data2个参数可选。众所周知，http请求的请求体格式主要有以下4种：application/jsonapplicaiton/x-www-from-urlencodedmultipart/form

  4. 03-JavaScript-函数

    函数就是将特定功能的代码封装起来，当需要实现特定功能时，直接调用函数实现即可。一、函数定义和使用1.1定义函数语句式命名函数functionsum(a,b){returna+b;}变量函数表达式是一个匿名函数，它没有函数名letsum=function(a,b){returna+b;};1.2调用函数按顺序传入参数co

  5. 网络基础-应用层协议-HTTP/HTTPS

    HTTP/HTTPSHTTP基本概念协议格式请求报文请求方法请求资源地址协议版本应答报文常见Header常见状态码与状态描述Cookie&Sessionhttp协议特点HTTPS基本概念对称加密与非对称加密数据摘要&数据指纹HTTPS工作过程探究只采用对称加密只采用非对称加密双方都采用非对称加密对称加密+非对称加密中间

  6. 手机提词器有哪些？简单介绍这一款

    手机提词器有哪些？手机提词器在现代社会中越来越受欢迎，原因是它可以帮助人们提高演讲和朗读的效果。使用手机提词器可以让人们更加自信地面对演讲和朗读，不至于出现口误或读错字的情况。此外，手机提词器还可以帮助人们节省时间和精力，让人们可以更加专注于演讲和朗读的内容。目前市面上有很多种手机提词器，今天就给大家介绍一款好用的手机

  7. Harmony系统更改手机IP

    在当今的互联网环境中，我们经常需要更改手机的IP地址来绕过限制或保护我们的隐私。虽然在一些操作系统上更改IP地址相对较容易，但在Harmony系统上，这可能会有些困难。因此，本文将分享一种在Harmony系统上免费更改手机IP地址的方法。在Harmony系统上，我们可以通过使用VPN（VirtualPrivateNet

  8. 前端原生和主流框架是如何dom的

    前言随着互联网技术的发展，前端技术也在不断地发展和更新。DOM（DocumentObjectModel）是前端开发中非常重要的一个概念，可以理解为网页上的所有元素都是DOM节点，通过操作这些节点，可以实现网页的动态效果和交互功能。本文将介绍JavaScript操作DOM、jQuery操作DOM、Vue操作DOM、Rea

  9. C++之list

    目录一、关于list二、list相关函数三、相关函数的使用1、构造函数2、push_back3、迭代器4、push_front5、pop_back6、insert7、erase关于迭代器失效问题8、splice9、remove10、sort一、关于listlist和string、vector一样，都是容器，都有很强的相