当前位置: 首页 > news >正文

Collection与数据结构 顺序表与ArrayList

1. 线性表

线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列…
线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。
在这里插入图片描述

2. 顺序表

顺序表是一段物理空间连续的线性表,在底层一般使用数组来实现,在数组的基础上完成增删查改.下面是顺序表的一些接口.

2.1 接口

public interface Ilist {void add(int data);//为顺序表的尾部增加元素void add(int data ,int pos);//为指定位置添加元素void display();//打印顺序表int size ();//检测顺序表中元素的个数boolean contains(int toFind);//检测顺序表中是否包含该元素int indexOf(int toFind);//返回所要寻找第一个元素的下标int get(int index);//获取指定下标的元素void set(int index,int val);//把指定下标的元素指定为指定元素void remove(int toRomve);//移除第一个指定的元素void clear();//清空顺序表
}

下面我们来实现这些接口:

import java.util.Arrays;/*** 顺序表底层是用数组来实现的*/
public class MyArrayList implements Ilist {private int[] elem;private int size;//记录有效数据public static final int DEFAULT_CAPACITY = 5;//默认容量private boolean isFull(){return size == elem.length;//判断顺序表的容量是否为满}private void checkPos(int pos){if (pos < 0 || pos >= size){throw new PosException("pos is false");//判断插入位置是否合法}}private boolean isEmpty(){return this.size == 0;}public MyArrayList() {this.elem = new int[DEFAULT_CAPACITY];//默认容量为5this.size = 0;}//无参数的构造方法public void add(int data){//在末尾的位置添加元素if (isFull()){elem = Arrays.copyOf(elem,elem.length*2);//扩容}elem [size] = data;size++;}public void add(int data ,int pos){//在指定位置添加元素checkPos(pos);if (isFull()){elem = Arrays.copyOf(elem,elem.length*2);//扩容}for (int i = size-1; i >= pos ; i--) {//数组整体后移elem [i+1] = elem [i];}elem[pos] = data;size++;}public void display(){//打印顺序表System.out.print("["+" ");for (int i = 0; i < size; i++) {//打印有效元素System.out.print(elem[i]+" ");}System.out.print("]");}public int size (){//返回当前顺序表大小return this.size;}public boolean contains(int toFind){for (int i = 0; i < size; i++) {//在这里不可以用elem.length,后面的扩容之后未赋值if(elem[i] == toFind){return true;}}return false;}public int indexOf(int toFind){//返回要找的元素第一个返回的下标for (int i = 0; i < size; i++) {//在这里不可以用elem.length,后面的扩容之后未赋值if(elem[i] == toFind){return i;}}return -1;}public int get(int index){//获取index位置的值checkPos(index);if (isEmpty()){//存在默认容量5,若没有此方法,可能会在未初始化的位置上直接获取元素,获取成功//但是为0,不符合实际throw new EmptyException("array is empty");}return elem[index];}public void set(int index,int val){//把index位置的值改为valcheckPos(index);if (isEmpty()){//存在默认容量5,若没有此方法,可能会在未初始化的位置上直接添加元素,//添加成功,但是不符合实际throw new EmptyException("array is empty");}elem[index] = val;}public void remove(int toRomve){//移除第一次出现的元素if (isEmpty()){throw new EmptyException("array is empty");}int index = indexOf(toRomve);//先找到下标的位置for (int i = index+1; i < size; i++) {elem[i-1] = elem[i];}elem[size-1] = 0;size --;}public void clear(){size = 0;}
}public class EmptyException extends NullPointerException{public EmptyException(String s) {super(s);}
}public class PosException extends ArrayIndexOutOfBoundsException{public PosException(String s) {super(s);}
}

下面通过一些测试用例;来测试:

public class Main {public static void main(String[] args) {MyArrayList list = new MyArrayList();list.add(0);list.add(1);list.add(3);list.add(4);list.add(2,2);list.add(5);list.display();System.out.println(list.size());list.remove(2);list.display();System.out.println(list.size());}
}

在这里插入图片描述

3.ArrayList简介

在这里插入图片描述
[说明]

  1. ArrayList是以泛型的方式实现的,使用时必须先实例化.
  2. ArrayList的底层是一段连续的存储空间,并且可以动态扩容,是一个动态类型的顺序表.

4.ArrayList的使用

4.1 ArrayList的构造方法

方法解释
public ArrayList()无参构造方法
public ArrayList(int initialCapacity)指定顺序表初始容量
public ArrayList(Collection<? extends E> c)利用Collection中的容器来构造

关于第三个构造方法,不太好理解,我们下面来解释一下:ArrayList已经传入了泛型的参数,就是E,这里用来构造ArrayList的Collection类中的元素必须是E的子类.

ArrayList<Integer> list = new ArrayList<>();
ArrayList<Integer> list1 = new ArrayList<>(list);
ArrayList<Number> list2 = new ArrayList<>(list);
ArrayList<Integer> list3 = new ArrayList<>(10);

4.2 ArrayList常见操作

方法解释
boolean add(E e)在尾部添加元素
void add(int index,E element)在指定位置添加元素
boolean addAll(Collection<? extends E> c)把c中的元素全部添加到顺序表尾部
E remove(int index)移除指定位置的元素
boolean remove(Object o)移除遇到的第一个元素o
E get(int index)获取指定位置的元素
E set(int index,E element)把指定位置的元素设置为指定的值
void clear()清空顺序表
boolean contains(Object o)检测顺序表中是否包含o
int indexOf(Object o)返回第一个指定元素所在的下标
int lastIndexOf(Object o)从后向前找,返回第一个元素所在的下标
List subList(int fromIndex,int toIndex)截取指定范围的字符串,左闭右开

在这里说明一下两个remove方法的区别,避免混淆,第一个remove方法时移除指定位置的元素,传入的元素类型为int类型的数据,而第二个remove方法移除的是第一个遇到的元素,这里传入的参数类型是和顺序表泛型相同的类型,当一个顺序表中存储的是Integer类型的数据的时候,要注意区分下标和元素.
下面对上述方法进行演示:

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,否则返回falseif(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.3 ArrayList的遍历

ArrayList有四种遍历方式,一种是通过sout直接输出,一种是for-i,一种是for-each,一种是使用迭代器.

import java.util.ArrayList;
import java.util.Iterator;
public class TestArrayList {public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);//通过sout去遍历ArrayListSystem.out.println(list);//通过fori遍历for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i)+" ");}System.out.println();//通过foreach遍历for (int x:list) {System.out.print(x+" ");}System.out.println();//通过迭代器遍历Iterator<Integer> iterator = list.iterator();while (iterator.hasNext()){System.out.print(iterator.next()+" ");}System.out.println();}
}

4.4 ArrayList扩容机制

ArrayList是动态的顺序表,在顺序表的容量不够的时候会自动扩容,下面是底层代码对ArrayList的扩容机制.

	public boolean add(E e) {modCount++;//底层是C/C++代码add(e, elementData, size);//调用另一个重载的add方法,指定添加容积return true;}private void add(E e, Object[] elementData, int s) {if (s == elementData.length)//容器满的时候需要扩容elementData = grow();//调用grow方法扩容elementData[s] = e;size = s + 1;}private Object[] grow() {return grow(size + 1);//最小容积是size+1,就是指定的添加容积+1}private Object[] grow(int minCapacity) {//传入指定的最小容积int oldCapacity = elementData.length;if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {int newCapacity = ArraysSupport.newLength(oldCapacity,//对数组扩容minCapacity - oldCapacity, /* minimum growth */    //计算原容量和最小容积的差值oldCapacity >> 1  //原容量的一半         /* preferred growth */);return elementData = Arrays.copyOf(elementData, newCapacity);//正式扩容} else {return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];}}public static int newLength(int oldLength, int minGrowth, int prefGrowth) {// preconditions not checked because of inlining// assert oldLength >= 0// assert minGrowth > 0int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow//若pre大,1.5被扩容,若是min大,直接加上指定的最小容积if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {return prefLength;} else {// put code cold in a separate methodreturn hugeLength(oldLength, minGrowth);}}

[总结]

  1. 预估要扩容的大小
  • 初步预估按照1.5倍扩容.
  • 如果用户所需大小预估超过1.5,则按照用户所需大小扩容.
  1. 使用copyOf扩容.

相关文章:

Collection与数据结构 顺序表与ArrayList

1. 线性表 线性表&#xff08;linear list&#xff09;是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构&#xff0c;常见的线性表&#xff1a;顺序表、链表、栈、队列… 线性表在逻辑上是线性结构&#xff0c;也就说是连续的一条直线。但是在…...

pytorch | torchvision.transforms.CenterCrop

torchvision.transforms.CenterCrop&#xff1e;从图像中心裁剪图片 transforms.CenterCrop torchvision.transforms.CenterCrop(size) 功能&#xff1a;从图像中心裁剪图片 size: 所需裁剪的图片尺寸 transforms.CenterCrop(196)的效果如下&#xff1a; &#xff08;也可…...

在Debian 11上安装GCC

GCC&#xff08;GNU Compiler Collection&#xff09;是一个功能强大的工具集合&#xff0c;可用于将不同编程语言的源代码编译成可执行文件或库。它支持多种编程语言&#xff0c;包括C、C、Java、Objective-C、Go、Fortran、Ada等。在Debian 11上安装GCC非常简单&#xff0c;以…...

kafka部署之简单密钥

一、说明 centos7.9kafka_2.13-2.7.0.tgzapache-zookeeper-3.8.0-bin.tar.gz官方文档&#xff1a;Apache Kafka 二、kafka配置 2.1、server.properties server.properties修改或增加如下配置 listenersSASL_PLAINTEXT://你的主机ip:9092 super.usersUser:admin authorizer…...

大模型重塑电商,淘宝、百度、京东讲出新故事

配图来自Canva可画 随着AI技术日渐成熟&#xff0c;大模型在各个领域的应用也越来越深入&#xff0c;国内互联网行业也随之进入了大模型竞赛的后半场&#xff0c;开始从“百模大战”转向了实际应用。大模型从通用到细分垂直领域的跨越&#xff0c;也让更多行业迎来了新的商机。…...

用静态工厂方法代替构造器

用静态工厂方法来代替构造方法。 public class Student {private String name;private int age;private String studentId;private Student(String name, int age, String studentId) {this.name name;this.age age;this.studentId studentId;}public static Student creat…...

Discourse 最多允许有几个分类级别

和 DISCUZ 不同&#xff0c;DISCUZ 可以允许分类下面还有分类&#xff0c;再继续分类这种嵌套式分类。 Discourse 最多只允许有 2 个分类。 如果你在已有的分类下再继续分类的话&#xff0c;系统会提示错误&#xff1a; 意思就是子分类不能再分子分类。 Discourse 尽量采取了…...

MySQL数据库主从复制和读写分离

MySQL数据库主从复制和读写分离 。## MySQL主从复制 MySQL主从复制的概念 MySQL主从复制是一个异步的数据复制过程&#xff0c;允许将一个MySQL服务器&#xff08;主服务器&#xff09;上的数据复制到一个或多个MySQL服务器&#xff08;从服务器&#xff09;。主从复制提供了…...

rust - 使用log4rs打印日志

本文提供了一种通过log4rs库记录日志的方法。这里没有采用读取yaml文件的方式&#xff0c;而是通过对象构造的方式来初始化日志&#xff0c;用于发包时不带配置文件的场景。 初始化日志 在release环境&#xff0c;仅需要将日志打印到文件中&#xff0c;而日常开发时&#xff…...

数据结构:单调栈和单调队列

文章目录 一、单调栈1.1、栈的思想1.2、单调栈1.2.1、单调栈的基本应用&#xff1a;找出数组中每个元素右侧第一个更大的元素1.2.2、单调栈的基本应用&#xff1a;找出数组中每个元素左侧第一个更大的元素1.2.3、单调栈拓展1.2.4、单调栈LeetCode题单 二、单调队列2.1、队列的思…...

大模型RAG性能提升路径

大模型相关目录 大模型&#xff0c;包括部署微调prompt/Agent应用开发、知识库增强、数据库增强、知识图谱增强、自然语言处理、多模态等大模型应用开发内容 从0起步&#xff0c;扬帆起航。 大模型应用向开发路径&#xff1a;AI代理工作流大模型应用开发实用开源项目汇总大模…...

机器视觉学习(九)—— 边缘检测

目录 一、边缘检测 1.1 Canny边缘检测 1.1.1 cv2.Canny函数 1.1.2 Canny边缘检测示例 1.2 角点检测 1.2.1 cv2.goodFeaturesToTrack()函数 1.2.2 OpenCV角点检测示例代码 1.3 直线检测 1.3.1 cv2.HoughLinesP()函数 1.3.2 OpenCV直线检测示例代码 1.4 圆形检测 1.4…...

基于单片机声音分贝采集和显示控制系统设计

**单片机设计介绍&#xff0c;基于单片机声音分贝采集和显示控制系统设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机声音分贝采集和显示控制系统设计&#xff0c;主要目标是实现声音分贝的实时采集、处理以及显示…...

CentOS使用Docker部署Halo并结合内网穿透实现公网访问本地博客

文章目录 1. Docker部署Halo1.1 检查Docker版本如果未安装Docker可参考已安装Docker步骤&#xff1a;1.2 在Docker中部署Halo 2. Linux安装Cpolar2.1 打开服务器防火墙2.2 安装cpolar内网穿透 3. 配置Halo个人博客公网地址4. 固定Halo公网地址 本文主要介绍如何在CentOS 7系统使…...

打造高效自动化渗透测试系统:关键步骤与实践

随着当前网络安全威胁的不断扩展与升级&#xff0c;开展渗透测试工作已经成为广大企业组织主动识别安全漏洞与潜在风险的关键过程。然而&#xff0c;传统的人工渗透测试模式对测试人员的专业能力和经验水平有很高的要求&#xff0c;企业需要投入较大的时间和资源才能完成。在此…...

绿联 部署vocechat,搭建私人聊天服务器,用于小型团队和家庭环境

1、镜像 privoce/vocechat-server:latest 2、安装 2.1、基础设置 重启策略&#xff1a;容器退出时总是重启容器。 2.2、网络 桥接即可。 2.3、存储空间 装载路径&#xff1a;/home/vocechat-server/data不可变更&#xff0c;权限读写。 2.4、端口设置 容器端口3000不可变…...

考研数学|高效刷透汤家凤《1800》经验分享

当然不需要换老师&#xff0c;如果你在基础阶段连汤老师的课都听不进去&#xff0c;那么换其他老师的话&#xff0c;很大可能也是白搭。 如果你现在对于1800还是一筹莫展的话&#xff0c;那么很明显&#xff0c;这反映出前期基础不扎实&#xff0c;没有真正理解和掌握这部分内…...

LLM推理入门指南②:深入解析KV缓存

在本系列文章《LLM推理入门指南①&#xff1a;文本生成的初始化与解码阶段》中&#xff0c;作者对Transformer解码器的文本生成算法进行了高层次概述&#xff0c;着重介绍了两个阶段&#xff1a;单步初始化阶段&#xff0c;即提示的处理阶段&#xff0c;和逐个生成补全词元的多…...

上采样技术在语义分割中的应用

目录 概要 一、概述 二、实现方法 1.转置卷积 2.反池化 3.双线性插值法 三、在经典网络中的的应用 1.U-Net 2.FCN 总结 概要 上采样是用于深度学习中提高语义分割精度的技术&#xff0c;可以实现图像放大和像素级别标注 一、概述 神经网络的基本结构为&#xff1a;…...

linux 组建raid5详细操作

raid5最多运行损坏一个盘&#xff0c;最少3个盘&#xff0c;容量为少一块硬盘的容量之和。 如果硬盘数量较多&#xff0c;比如8块以上&#xff0c;建议用raid6&#xff0c;raid6最多允许两块硬盘损坏。 如果需要 一、安装raid软件 deb包 apt-get install mdadm或dnf包 dnf …...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

GO协程(Goroutine)问题总结

在使用Go语言来编写代码时&#xff0c;遇到的一些问题总结一下 [参考文档]&#xff1a;https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现&#xff1a; 今天在看到这个教程的时候&#xff0c;在自己的电…...

如何应对敏捷转型中的团队阻力

应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中&#xff0c;明确沟通敏捷转型目的尤为关键&#xff0c;团队成员只有清晰理解转型背后的原因和利益&#xff0c;才能降低对变化的…...

书籍“之“字形打印矩阵(8)0609

题目 给定一个矩阵matrix&#xff0c;按照"之"字形的方式打印这个矩阵&#xff0c;例如&#xff1a; 1 2 3 4 5 6 7 8 9 10 11 12 ”之“字形打印的结果为&#xff1a;1&#xff0c;…...