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

数据结构：ArrayList与顺序表

article 2025/1/7 16:13:09

目录

 📖一、什么是List

📖二、线性表

📖三、顺序表

🐬1、display()方法

🐬2、add(int data)方法

🐬3、add(int pos, int data)方法

🐬4、contains(int toFind)方法

🐬5、indexOf(int toFind)方法

🐬6、get(int pos)方法

🐬7、set(int pos, int value)方法

🐬8、remove(int toRemove)方法

🐬9、size()方法

🐬10、clear()方法

🐬11、完整代码 

📖四、ArrayList简介

📖五、ArrayList的构造 

🐬1、ArrayList()无参构造

🐬2、ArrayList(int initialCapacity))带参构造

🐬3、ArrayList(Collection c)利用Collection进行构造

📖六、ArrayList使用

🐬1、addAll(Collection c)方法

🐬2、remove(int index)方法

🐬3、remove(Object o)方法

🐬4、lastIndexOf(Object o)方法

🐬5、ListsubList(int fromIndex,int toIndex)方法

📖七、ArrayList的遍历 

🐬1、for循环+下标 

🐬2、for each

🐬3、迭代器

 📖一、什么是List

在集合框架中，List是一个接口，继承自Collection。而Collection也是一个接口，同时他有一些方法，因此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 tolndex)截取部分 list

📖二、线性表

线性表（linearlist）是n个具有相同特性的数据元素的有限序列。线性表是⼀种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列... 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

📖三、顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。 在数组上他们通常表现为数据的增删查改。（顺序表具有扩容能力，通常以自身的1.5倍或2倍进行扩容）

然而我们知道数组是不具备增删查改的功能的，因此我们需要自己创建一个类，自己来实现自己创建IList接口

下面我们就来实现一个顺序表

🐬1、display()方法

打印顺序表

🐬2、add(int data)方法

新增元素 , 默认在数组最后新增（尾插）

🐬3、add(int pos, int data)方法

在 pos 位置新增元素

🐬4、contains(int toFind)方法

判定是否包含某个元素

🐬5、indexOf(int toFind)方法

查找某个元素对应的位置

🐬6、get(int pos)方法

获取 pos 位置的元素

🐬7、set(int pos, int value)方法

给 pos 位置的元素设为 value

🐬8、remove(int toRemove)方法

删除第一次出现的关键字 key

🐬9、size()方法

获取顺序表长度

🐬10、clear()方法

清空顺序表

🐬11、完整代码 

Ilist接口

package List;

public interface IList {
    void add(int data);

    void add(int pos, int data);

    boolean contains(int toFind);

    int indexOf(int toFind);

    int get(int pos);

    void set(int pos, int value);

    void remove(int toRemove);

    int size();

    void clear();

    void display();
}

MyArrayList类 

import List.EmptyTable;
import List.IList;
import List.Illegality;

import java.nio.channels.ScatteringByteChannel;
import java.util.Arrays;

public class MyArrayList implements IList {
    public int[] arr;
    public int usedsize;

    public static final int DEFAULT_SIZE = 10;

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

    @Override
    public void display() {
        for (int i = 0; i < this.usedsize; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }

    @Override
    public void add(int data) {
        if(isFull()){
            Expansion();
        }
        this.arr[this.usedsize] = data;
        this.usedsize++;
    }

    public boolean isFull(){
        return this.usedsize == DEFAULT_SIZE;
    }

    public void Expansion(){
        this.arr = Arrays.copyOf(this.arr, 2*this.arr.length);
    }

    @Override
    public void add(int pos, int data) {
        try{
            check1(pos);
            if(isFull()){
                Expansion();
            }
            int right = this.usedsize;
            while(pos < right){
                arr[right] = arr[--right];
            }
            this.arr[pos] = data;
            this.usedsize++;
        }catch(Illegality e){
            e.printStackTrace();
        }
    }

    public void check1(int pos) throws Illegality{
        if( pos < 0 || pos > this.usedsize){
            throw new Illegality("pos不合法");
        }
    }
    @Override
    public boolean contains(int toFind) {
        for (int i = 0; i < this.usedsize; i++) {
            if(this.arr[i] == toFind){
                return true;
            }
        }
        return false;
    }

    @Override
    public int indexOf(int toFind) {
        for (int i = 0; i < this.usedsize; i++) {
            if(this.arr[i] == toFind){
                return i;
            }
        }
        return -1;
    }

    @Override
    public int get(int pos) {
        try{
            empty();
            check2(pos);
            return this.arr[pos];
        }catch (Illegality e){
            e.printStackTrace();
        }catch (EmptyTable e){
            e.printStackTrace();
        }
        return -1;
    }
    public void check2(int pos) throws Illegality{
        if(pos < 0 || pos >= this.usedsize){
            throw new Illegality("pos不合法");
        }
    }

    public void empty() throws EmptyTable {
        if(this.usedsize == 0){
            throw new EmptyTable("顺序表为空");
        }
    }

    @Override
    public void set(int pos, int value) {
        try{
            empty();
            check2(pos);
            this.arr[pos] = value;
        }catch (Illegality e){
            e.printStackTrace();
        }catch (EmptyTable e){
            e.printStackTrace();
        }
    }

    @Override
    public void remove(int toRemove) {
        try{
            empty();
            int pos = indexOf(toRemove);
            if(pos == -1){
                return;
            }
            for (int i = pos; i < this.usedsize ; i++) {
                arr[pos] = arr[++pos];
            }
            this.usedsize--;
        }catch (EmptyTable e){
            e.printStackTrace();
        }
    }

    @Override
    public int size() {
        return this.usedsize;
    }

    @Override
    public void clear() {
        this.usedsize = 0;
    }

}

异常 

package List;

public class Illegality extends RuntimeException{
    public Illegality(String message){
        super(message);
    }
}
package List;

public class EmptyTable extends RuntimeException{
    public EmptyTable(String message){
        super(message);
    }
}

主函数 

public class Test {
    public static void main(String[] args) {
        MyArrayList myArrayList = new MyArrayList();
       
    }
}

📖四、ArrayList简介

在上面我们自己实现了一个顺序表MyArrayList,但是在Java中编译器自带了一个顺序表ArrayList类，它同样实现了List接口，虽然它和我们自己实现的顺序表大同小异，但是它还有一些地方需要注意。

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

📖五、ArrayList的构造 

🐬1、ArrayList()无参构造

🐬2、ArrayList(int initialCapacity))带参构造

🐬3、ArrayList(Collection<? extends E> c)利用Collection进行构造

而它传入的值是限制通配符的上界本身和他的子类 

📖六、ArrayList使用

ArrayList实现的顺序表是实现了List接口，大多的方法的使用是和我们自己实现的接口是一样的，因此下面我们会对那些不同的进行讲解

🐬1、addAll(Collection<? extends E> c)方法

尾插c中的元素

🐬2、remove(int index)方法

删除 index 位置元素

🐬3、remove(Object o)方法

删除遇到的第一个o

🐬4、lastIndexOf(Object o)方法

返回最后一个o的下标

IndexOf返回的是相同元素第一个出现的下标，而lastIndexOf返回的是最后一个的下标

🐬5、List<E>subList(int fromIndex,int toIndex)方法

截取部分 list

📖七、ArrayList的遍历 

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

🐬1、for循环+下标 

🐬2、for each

🐬3、迭代器

好了今天的分享就到这里了，还请大家多多关注，我们下一篇见！


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

相关文章：

  • 【AI落地】AI生成测试用例，claude or gpt?（提效至少 50%）
  • 图漾相机基础操作
  • Windows提示msvcp120.dll丢失怎么解决？Windows文件丢失的4种解决方法，教你修复msvcp120.dll文件
  • 海外招聘丨 弗拉瑞克商学院—博士研究员：智能家居技术业务和能源管理中的数据分析和人工智能
  • clickhouse query_log 常用查询语句
  • GitHub 基础使用指南
  • 每日一学——日志管理工具（Graylog）
  • C++和OpenGL实现3D游戏编程【连载19】——着色器光照初步（平行光和光照贴图）（附源码）
  • 主从复制（Redis的特性）
  • 深入探索 Kubernetes：从基础概念到实战运维
  • 复杂对象的创建与组装 - 建造者模式（Builder Pattern）
  • flutter在windows平台中运行报错
  • BOOST 库在机器视觉中的应用及示例代码分析
  • 【C++】B2099 矩阵交换行
  • 基于 GitHub Actions 的流程自动化实践
  • Apache Traffic存在SQL注入漏洞(CVE-2024-45387)
  • 感冒之嗓子红肿，咽红且痛，微恶风寒，无浑身疼痛，无清鼻涕
  • Redis数据库笔记—— Hash（哈希）的扩容机制(rehash)
  • Python爬虫基础——requests模块
  • Harmony OS开发-ArkTS语言速成五
  • 嵌入式Linux（二）·配置VMware使用USB网卡连接STM32MP157实现Windows、Ubuntu以及开发板之间的通信
  • 基于海思soc的智能产品开发（camera sensor的两种接口）
  • React中的合成事件
  • 源代码编译安装X11及相关库、vim，配置vim（2）
  • 智能工厂的设计软件 应用场景的一个例子：为AI聊天工具添加一个知识系统 之13 方案再探之4：特定于领域的模板 之 div模型（完整版）
  • SpringCloud源码-Ribbon