JAVA-顺序表ArrayList(实现ArrayList)

1.线性表

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

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构(从内存看来)并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

1.1 什么是List

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

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

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

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

1.2 List常用方法

List常用方法：

List所有方法：

 

1.3 List的使用

注意：List是个接口，并不能直接用来实例化。

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

2. 顺序表

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

2.1 ArrayList简介

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

【说明】

1. ArrayList是以泛型方式实现的，使用时必须要先实例化

2. ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问

3. ArrayList实现了Cloneable接口，表明ArrayList是可以clone的

4. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的

5. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者 CopyOnWriteArrayList

6. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

2.2 ArrayList的使用 

2.2.1 ArrayList的构造方法

ArrayList有三个构造方法

无参的构造方法 ：

 

参数为int的构造方法：

泛型参数构造方法:

由于这个方法：套了很多方法不好讲解，我就对参数和最终使用做讲解

 使用：

ArrayList推荐写法：

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);}

 2.2.2 ArrayList常见方法

2.2.2.1 add或者addAll

一共有3种方法：

 

2.2.2.2  remove

 

2.2.2.3 get和set

这个很简单就不多说了

 

 2.2.2.4 contains

 判断是否有这个参数

2.2.2.5 indexOf和lastIndexOf

 

2.2.2.6 subList

注意：java中凡是区间都是左闭右开[ , )  也就是说上面代码只能截取到1和2下标 

2.2.2.7 clear

清空顺序表

2.3 ArrayList的遍历

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);//直接sout打印System.out.println("===sout===");System.out.println(list);// 使用下标+for遍历System.out.println("===for===");for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + " ");}System.out.println();// 借助foreach遍历System.out.println("===foreach===");for (Integer integer : list) {System.out.print(integer + " ");}System.out.println();//迭代器System.out.println("===Iterator===");Iterator<Integer> it1 = list.iterator();while (it1.hasNext()) {System.out.print(it1.next() + " ");}System.out.println();System.out.println("===ListIterator===");//专门给List用的迭代器ListIterator<Integer> it2 = list.listIterator();while(it2.hasNext()){System.out.print(it2.next() + " ");}System.out.println();System.out.println("===ListIterator 倒着打印===");ListIterator<Integer> it3 = list.listIterator(list.size());while (it3.hasPrevious()) {System.out.print(it3.previous() + " ");}System.out.println();}

这里面迭代器可能大家看不懂我给大家说明一下：

那hasprevious其实是判断前面是否还有？是true否false

previous向前移一位，sout并打印

 

2.4 ArratList扩容机制

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 codeif (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进行扩容

 

3. 实现顺序表

简单实现一下顺序表的大概

把要实现的方法都放在接口中：

public interface IList {// 新增元素,默认在数组最后新增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);//删除第一次出现的关键字keyvoid remove(int toRemove);// 获取顺序表长度int size();// 清空顺序表void clear();// 打印顺序表，// 注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的void display();
}

在用类去实现此接口，后面所有的方法都在此类中实现：

public class MyArrayList implements IList{private int[] array;//存放数据private int size;//用来记录元素个数//实现一个构造方法，默认初始化为大小为10public MyArrayList(){this.array = new int[10];}
}

size会默认为0，所有不用对他初始化

3.1 实现add

我们有size实现作为记录元素个数的下标，当刚好可以做为尾插的位置

 

但如果刚好满了，我们就需要扩容所以，可以用单独写一个方法判断一下

   @Overridepublic void add(int data) {if(isFull()){//拷贝原有元素并，扩容两倍this.array = Arrays.copyOf(array,size * 2);}this.array[size] = data;this.size++;}@Overridepublic boolean isFull() {if(array.length == size){return true;}return false;}

利用Arrays.copyOf进行扩容，他不仅可以拷贝原有的元素，还可以进行扩容操作。

 

那么在来做指定位置插入:

想要在指定位置插入，但是又不删除原位置的数据，就必须要移动

想要达到此效果，就需要从有效数据最后位置一个一个往后移动最终直接用给定的下标进行插入就可以了。

但是一旦有下标就需要进行判断下标是否合法：

    @Overridepublic void add(int pos, int data) {try {checkPosOfAdd(pos);//检查pos是否合法}catch (PosNotLegalException e) {e.printStackTrace();}//移动原数组for (int i = size-1; i >= pos; i--) {this.array[i + 1] = this.array[i];}this.array[pos] = data;this.size++;}private void checkPosOfAdd(int pos) {if(pos > size || pos < 0) {throw new PosNotLegalException("位置不合法");}}

注意：

尾插是可以做到的，所以判断pos合法性的时候 pos == size的位置可以不做判断

异常：

public class PosNotLegalException extends RuntimeException{public PosNotLegalException() {}public PosNotLegalException(String mag) {super(mag);}
}

3.2 实现contains

    @Overridepublic boolean contains(int toFind) {for (int i = 0; i < size; i++) {if(array[i] == toFind) {return true;}}return false;}

3.3 实现indexOf 

    @Overridepublic int indexOf(int toFind) {for (int i = 0; i < size; i++) {if(array[i] == toFind) {return i;}}return -1;}

3.4 实现get

    @Overridepublic int get(int pos) {try {checkPosOfGetAndSet(pos);//检查pos位置是否合法}catch (PosNotLegalException e) {e.printStackTrace();}return this.array[pos];}private void checkPosOfGetAndSet(int pos) {if(pos >= size || pos < 0) {throw new PosNotLegalException("Get/Set位置不合法");}}

3.5 实现set

    @Overridepublic void set(int pos, int value) {try {checkPosOfGetAndSet(pos);}catch (PosNotLegalException e) {e.printStackTrace();}array[pos] = value;}

3.6 实现remove

直接用indexOf判断是否有这个数据,有就从pos后面的数据一个个向前移动，但是最后的那个元素还是会在原位置上，不用担心size-1就可以做到删除了，再次add数据就会覆盖到他

    @Overridepublic void remove(int toRemove) {int pos = indexOf(toRemove);if(pos == -1) {System.out.println("没有要删除的数字");return;}for (int i = pos; i < size; i++) {array[i] = array[i+1];}this.array[size] = 0;this.size--;}

 3.7 实现size

    @Overridepublic int size() {return this.size;}

3.8 实现clear

    @Overridepublic void clear() {for (int i = 0; i < size; i++) {this.array[i] = 0;
//            this.array[i] = null;   如果顺序表是指针类型需要全部置为空
//        因为，只要没有引用这篇空间的引用，才会释放}this.size = 0;}

3.9 实现display

    @Overridepublic void display() {for (int i = 0; i < size; i++) {System.out.print(array[i] + " ");}System.out.println();}

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

DCN DCWS-6028神州数码 AC 设备配置笔记

DCN DCWS-6028神州数码 AC 设备配置笔记

DCN DCWS-6028神州数码 AC 设备配置笔记 一、前期准备 PC 电脑网络配置 目的：使 PC 能够访问 AC 的 web 管理控制台。配置详情：web 管理控制台地址为 192.168.1.10，将 PC 电脑 IP 地址配置在 192.168.1.1 - 192.168.1.254 网段内，如 192.168.1.110，子网掩码 255.255.255.…
阅读更多...
树概念及结构

树概念及结构

树概念及结构 6.1 树概念及结构6.1.1 树的概念6.1.2 树的术语解读6.1.3 树的表示 6.1 树概念及结构 6.1.1 树的概念 类似八股文一样的东西&#xff0c;需要记一下。 树是一种非线性的数据结构&#xff0c;它是由n&#xff08;n>0&#xff09;个有限结点组成一个具有层次关系…
阅读更多...
MySQL主从复制原理

MySQL主从复制原理

MySQL主从复制是一种异步、基于日志的、单向的数据库复制技术&#xff0c;它通过在主服务器上启用二进制日志&#xff08;binlog&#xff09;并将其发送给一个或多个从服务器&#xff0c;实现了从服务器与主服务器之间的数据同步。以下是MySQL主从复制原理的详细解释&#xff1…
阅读更多...
AMD-OLMo：在 AMD Instinct MI250 GPU 上训练的新一代大型语言模型。

AMD-OLMo：在 AMD Instinct MI250 GPU 上训练的新一代大型语言模型。

AMD-OLMo是一系列10亿参数语言模型&#xff0c;由AMD公司在AMD Instinct MI250 GPU上进行训练&#xff0c;AMD Instinct MI250 GPU是一个功能强大的图形处理器集群&#xff0c;它利用了OLMo这一公司开发的尖端语言模型。AMD 创建 OLMo 是为了突出其 Instinct GPU 在运行 “具有…
阅读更多...
Spring Boot框架：构建符合工程认证的计算机课程

Spring Boot框架：构建符合工程认证的计算机课程

2相关技术 2.1 MYSQL数据库 MySQL是一个真正的多用户、多线程SQL数据库服务器。 是基于SQL的客户/服务器模式的关系数据库管理系统&#xff0c;它的有点有有功能强大、使用简单、管理方便、安全可靠性高、运行速度快、多线程、跨平台性、完全网络化、稳定性等&#xff0c;非常…
阅读更多...
实现链式结构二叉树

实现链式结构二叉树

目录 需要实现的操作 链式结构二叉树实现 结点的创建 前序遍历 中序遍历 后序遍历 计算结点个数 计算二叉树的叶子结点个数 计算二叉树第k层结点个数 计算二叉树的深度 查找值为x的结点 销毁 层序遍历 判断是否为完全二叉树 总结 需要实现的操作 //前序遍历 void …
阅读更多...
DU模拟器（S5040A Open RAN Studio Player and Capture Appliance）

DU模拟器（S5040A Open RAN Studio Player and Capture Appliance）

下行测试过程&#xff0c;由是德科技(https://www.keysight.com/cn/zh/home.html)的DU模拟器&#xff08;S5040A Open RAN Studio Player and Capture Appliance&#xff09;产生标准5G NR下行测试信号&#xff0c;经前传接口发送到小站进行基带处理、中射频、变频后从相控阵天…
阅读更多...
工程认证标准下的Spring Boot计算机课程管理策略

工程认证标准下的Spring Boot计算机课程管理策略

5系统详细实现 5.1 管理员模块的实现 5.1.1 教师信息管理 基于工程教育认证的计算机课程管理平台的系统管理员可以管理教师&#xff0c;可以对教师信息修改删除以及查询操作。具体界面的展示如图5.1所示。 图5.1 教师信息管理界面 5.1.2 通知公告管理 系统管理员可以对通知公…
阅读更多...
GeoHash处理经纬度，降维，空间填充曲线

GeoHash处理经纬度，降维，空间填充曲线

个人博客&#xff1a;无奈何杨&#xff08;wnhyang&#xff09; 个人语雀&#xff1a;wnhyang 共享语雀&#xff1a;在线知识共享 Github&#xff1a;wnhyang - Overview 参考 https://segmentfault.com/a/1190000042971576 GeoHash原理以及代码实现_geohash编码-CSDN博客…
阅读更多...
游戏引擎学习第三天

游戏引擎学习第三天

视频参考:https://www.bilibili.com/video/BV1XTmqYSEtm/ 之前的程序不能退出&#xff0c;下面写关闭窗体的操作 PostQuitMessage 是 Windows API 中的一个函数&#xff0c;用于向当前线程的消息队列发送一个退出消息。其作用是请求应用程序退出消息循环&#xff0c;通常用于处…
阅读更多...
CSS中常见文本居中技巧详解

CSS中常见文本居中技巧详解

在网页设计中&#xff0c;文本居中是非常常见且重要的布局需求之一。无论是为了美观还是为了更好地传达信息&#xff0c;掌握文本居中的方法对于前端开发者来说都是必不可少的技能。本文将详细介绍几种常用的CSS文本居中方法&#xff0c;帮助读者解决实际开发中的问题。 默认情…
阅读更多...
Java基础教程（001）：Java基础概念：注释、关键字、字面量

Java基础教程（001）：Java基础概念：注释、关键字、字面量

文章目录 1、Java基础概念1.1 注释1.2 关键字1.3 字面量1.4 制表符 1、Java基础概念 1.1 注释 【1】注释概念 注释是在程序指定位置添加的说明性信息。 简单理解&#xff0c;就是对代码的一种解释。 【2】注释分类 单行注释&#xff1a;// 注释信息多行注释&#xff1a;/…
阅读更多...
SIwave：释放 SIwizard 求解器的强大功能

SIwave：释放 SIwizard 求解器的强大功能

SIwave 是一种电源完整性和信号完整性工具。SIwizard 是 SIwave 中 SI 分析的主要工具&#xff0c;也是本博客的主题。 SIwizard 用于研究 RF、clock 和 control traces 的信号完整性。该工具允许用户进行瞬态分析、眼图分析和 BER 计算。用户可以将 IBIS 和 IBIS-AMI 模型添加…
阅读更多...
Windows10 下通过 Visual Studio2022 编译 openssl 3.4

Windows10 下通过 Visual Studio2022 编译 openssl 3.4

Windows10 下通过 Visual Studio2022 编译 openssl 3.4 1 准备环境1.2 perl1.2.1 ActiveState Perl 和 Strawberry Perl 的区别1.2.2 perl 下载1.2.3 验证安装1.2 NASM1.2.1 Windows 安装 NASM1.2.2 解压1.2.3 配置 NASM 的环境变量1.3 VS 配置1.3.1 配置 VS nmake 的环境变量1…
阅读更多...
了解Hadoop：大数据处理的核心框架

了解Hadoop：大数据处理的核心框架

在当今数据爆炸的时代&#xff0c;海量数据的存储和处理已成为一个巨大的挑战。传统数据库和计算模型难以应对如此庞大的数据规模。为了解决这一问题&#xff0c;Apache Hadoop应运而生&#xff0c;它是一种分布式存储和处理框架&#xff0c;能够高效地处理海量数据。本文将详细…
阅读更多...
本溪与深圳市新零售产业互联协会共商世界酒中国菜湾区农业发展

本溪与深圳市新零售产业互联协会共商世界酒中国菜湾区农业发展

本溪满族自治县与深圳市新零售产业互联协会汇聚鹏城共商世界酒中国菜大湾区农业发展大计 2024年11月9日下午2点&#xff0c;深圳市新零售产业互联协会内气氛热烈&#xff0c;一场关乎农业产业发展未来的重要讨论正在这里举行。此次会议汇聚了来自本溪满族自治县和大湾区的众多精…
阅读更多...
互联网广告的变现逻辑｜计费模式｜CPC、CPM、OCPC、OCPM

互联网广告的变现逻辑｜计费模式｜CPC、CPM、OCPC、OCPM

写在前面 最近的工作和广告相关&#xff0c;就整理一下自己学到的关于互联网广告变现的一些知识。 广告是互联网主要变现手段之一&#xff0c;一般的互联网公司都会有个商业化部门专门做广告的变现。那广告究竟是怎么变现的呢&#xff1f;怎么广告的好坏和什么有关呢&#xff1…
阅读更多...
从0开始深度学习（29）——文本预处理

从0开始深度学习（29）——文本预处理

序列数据中&#xff0c;最常见的例子就是文本数据&#xff0c;例如&#xff0c;一篇文章可以被简单地看作一串单词序列&#xff0c;甚至是一串字符序列。 本节中&#xff0c;我们将解析文本的常见预处理步骤。 0 文本预处理步骤 将文本作为字符串加载到内存中。将字符串拆分为…
阅读更多...
JDBC学习笔记--JdbcUtil工具类

JDBC学习笔记--JdbcUtil工具类

目录 &#xff08;一&#xff09;为什么要使用JdbcUtil工具类 &#xff08;二&#xff09;创建一个prorperties文件 1.在文件目录或src目录下&#xff0c;选择新建FIle 2.创建properties文件 3.编写配置文件 Java基础&#xff1a;反射 4.获取资源的方式 第一种 第二种…
阅读更多...
DNS域名解析

DNS域名解析

1、DNS简介 DNS&#xff08;Domain Name System&#xff09;是互联网上的一项服务&#xff0c;它作为将域名和IP地址相互映射的一个分布式 数据库&#xff0c;能够使人更方便的访问互联网。 DNS系统使用的是网络的查询&#xff0c;那么自然需要有监听的port。DNS使用的是53端…
阅读更多...
最新文章

Copyright @ 2022~2023