【数据结构】每天五分钟,快速入门数据结构(一)——数组

目录

一.初始化语法

二.特点

三.数组中的元素默认值

四.时间复杂度

五.Java中的ArrayList类 可变长度数组

1 使用

2 注意事项

3 实现原理

4 ArrayList源码

5 ArrayList方法

一.初始化语法

// 数组动态初始化(先定义数组,指定数组长度,后续再进行赋值)
int[] arr = new int[7]; 
arr[0] = 1; 
// 数组静态初始化(在创建数组时直接赋值)
String[] names = new String[]{"张三","李四","王五"};
int[] nums = {0,0,1,1,1,2,2,3,3,4}; 
//遍历数组中的元素
for( int i = 0;i < arr.length; i++){System.out.println(arr[i]);
}

二.特点

  • 数组下标从0开始

  • 随机访问能力:可以通过索引进行o(1)时间复杂度的访问

  • 一旦初始化就不能改变长度

  • 物理上和逻辑上都是连续的

三.数组中的元素默认值

  • int :0;

  • char: 空;

  • boolean: false;

  • double: 0.0;

  • 引用类型:null

四.时间复杂度

在数组中的任意位置插入:O(n) 通过索引值访问数组元素:O(1)

查找数组中某个值所在的索引值:O(n)或者O(log n)(有序数组二分查找) 删除数组中的某个元素:O(n)

五.Java中的ArrayList类 可变长度数组

1 使用

 ArrayList<String> sites = new ArrayList<String>(); // 创建一个可变长数组sites.add("张三"); // 添加元素sites.add("李四");sites.add("王五");System.out.println(sites); // 打印输出数组元素System.out.println(sites.get(1));  // 访问第二个元素sites.set(1, "柳柳"); // 修改元素内容,第一个参数为索引位置,第二个为要修改的值sites.remove(3); // 删除元素sites.size(); // 获取数组长度

2 注意事项

  • 数组下标从0开始

  • 数组中存储的元素类型只能为引用类型,因此需要使用基本类型的包装类

3 实现原理

自动创建一个长度为n的数组,当存放的数据量超过n时,就重新创建一个更长的数组,再将原数组内容复制到新数组中,更改数组名指向地址。

4 ArrayList源码

package java.util;public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{// 序列版本号private static final long serialVersionUID = 8683452581122892189L;// 默认容量大小private static final int DEFAULT_CAPACITY = 10;// 空数组private static final Object[] EMPTY_ELEMENTDATA = {};// 用于保存ArrayList中数据的数组private transient Object[] elementData;// ArrayList中所包含元素的个数private int size;// 带初始容量参数的构造函数public ArrayList(int initialCapacity) {super();if (initialCapacity < 0)throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);this.elementData = new Object[initialCapacity];}// 默认构造函数,其默认初始容量为10public ArrayList() {super();this.elementData = EMPTY_ELEMENTDATA;}// 带Collection参数的构造函数public ArrayList(Collection<? extends E> c) {elementData = c.toArray();size = elementData.length;// c.toArray might (incorrectly) not return Object[] (see 6260652)if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, size, Object[].class);}// 将此 ArrayList 实例的容量调整为列表的当前大小(实际元素个数)public void trimToSize() {modCount++;if (size < elementData.length) {elementData = Arrays.copyOf(elementData, size);}}// 如有必要,增加此 ArrayList 实例的容量,以确保它至少能够容纳最小容量参数所// 指定的元素数public void ensureCapacity(int minCapacity) {int minExpand = (elementData != EMPTY_ELEMENTDATA)// any size if real element table? 0// larger than default for empty table. It's already supposed to be// at default size.: DEFAULT_CAPACITY;if (minCapacity > minExpand) {ensureExplicitCapacity(minCapacity);}}private void ensureCapacityInternal(int minCapacity) {if (elementData == EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}ensureExplicitCapacity(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) {// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win:elementData = Arrays.copyOf(elementData, newCapacity);}private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}// 返回ArrayList中的元素个数public int size() {return size;}// 判断ArrayList是否为空public boolean isEmpty() {return size == 0;}// 判断ArrayList是否包含Object(o)public boolean contains(Object o) {return indexOf(o) >= 0;}// 返回ArrayList中首次出现的指定元素的索引,或如果此列表不包含元素,则返回 -1public int indexOf(Object o) {if (o == null) {for (int i = 0; i < size; i++)if (elementData[i]==null)return i;} else {for (int i = 0; i < size; i++)if (o.equals(elementData[i]))return i;}return -1;}// 返回ArrayList中最后一次出现的指定元素的索引,或如果此列表不包含索引,则返回 -1public int lastIndexOf(Object o) {if (o == null) {for (int i = size-1; i >= 0; i--)if (elementData[i]==null)return i;} else {for (int i = size-1; i >= 0; i--)if (o.equals(elementData[i]))return i;}return -1;}// 返回此 ArrayList 实例的浅表副本public Object clone() {try {@SuppressWarnings("unchecked")ArrayList<E> v = (ArrayList<E>) super.clone();// 将当前ArrayList的全部元素拷贝到v中v.elementData = Arrays.copyOf(elementData, size);v.modCount = 0;return v;} catch (CloneNotSupportedException e) {// this shouldn't happen, since we are Cloneablethrow new InternalError();}}// 按适当顺序(从第一个到最后一个元素)返回包含此列表中所有元素的数组public Object[] toArray() {return Arrays.copyOf(elementData, size);}// 返回ArrayList的模板数组。所谓模板数组,即可以将T设为任意的数据类型@SuppressWarnings("unchecked")public <T> T[] toArray(T[] a) {if (a.length < size)// Make a new array of a's runtime type, but my contents:return (T[]) Arrays.copyOf(elementData, size, a.getClass());System.arraycopy(elementData, 0, a, 0, size);if (a.length > size)a[size] = null;return a;}// 位置访问操作   @SuppressWarnings("unchecked")E elementData(int index) {return (E) elementData[index];}// 返回ArrayList中指定位置上的元素public E get(int index) {rangeCheck(index);return elementData(index);}// 用指定的元素替代ArrayList中指定位置上的元素,并返回替代前的元素public E set(int index, E element) {rangeCheck(index);E oldValue = elementData(index);elementData[index] = element;return oldValue;}// 将指定的元素添加到ArrayList的尾部public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!elementData[size++] = e;return true;}// 将指定的元素插入ArrayList中的指定位置public void add(int index, E element) {rangeCheckForAdd(index);ensureCapacityInternal(size + 1);  // Increments modCount!!System.arraycopy(elementData, index, elementData, index + 1,size - index);elementData[index] = element;size++;}// 移除ArrayList中指定位置上的元素,并返回该位置上的元素public E remove(int index) {rangeCheck(index);modCount++;E oldValue = elementData(index);int numMoved = size - index - 1;if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);elementData[--size] = null; // clear to let GC do its workreturn oldValue;}// 移除ArrayList中首次出现的指定元素(如果存在则移除并返回true,否则返回false)public boolean remove(Object o) {if (o == null) {for (int index = 0; index < size; index++)if (elementData[index] == null) {fastRemove(index);return true;}} else {for (int index = 0; index < size; index++)if (o.equals(elementData[index])) {fastRemove(index);return true;}}return false;}// 私有方法,用于快速移除private void fastRemove(int index) {modCount++;int numMoved = size - index - 1;if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);elementData[--size] = null; // clear to let GC do its work}// 移除ArrayList中的所有元素public void clear() {modCount++;// clear to let GC do its workfor (int i = 0; i < size; i++)elementData[i] = null;size = 0;}// 按照指定 collection 的迭代器所返回的元素顺序,// 将该 collection 中的所有元素添加到ArrayList的尾部public boolean addAll(Collection<? extends E> c) {Object[] a = c.toArray();int numNew = a.length;ensureCapacityInternal(size + numNew);  // Increments modCountSystem.arraycopy(a, 0, elementData, size, numNew);size += numNew;return numNew != 0;}// 从指定的位置开始,将指定 collection 中的所有元素插入到ArrayList中public boolean addAll(int index, Collection<? extends E> c) {rangeCheckForAdd(index);Object[] a = c.toArray();int numNew = a.length;ensureCapacityInternal(size + numNew);  // Increments modCountint numMoved = size - index;if (numMoved > 0)System.arraycopy(elementData, index, elementData, index + numNew,numMoved);System.arraycopy(a, 0, elementData, index, numNew);size += numNew;return numNew != 0;}// 移除列表中索引在 fromIndex(包括)和 toIndex(不包括)之间的所有元素protected void removeRange(int fromIndex, int toIndex) {modCount++;int numMoved = size - toIndex;System.arraycopy(elementData, toIndex, elementData, fromIndex,numMoved);// clear to let GC do its workint newSize = size - (toIndex-fromIndex);for (int i = newSize; i < size; i++) {elementData[i] = null;}size = newSize;}// 私有方法,用于范围检测private void rangeCheck(int index) {if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}// 私有方法,用于add和addAllprivate void rangeCheckForAdd(int index) {if (index > size || index < 0)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}private String outOfBoundsMsg(int index) {return "Index: "+index+", Size: "+size;}// 移除ArrayList中Collection所包含的所有元素public boolean removeAll(Collection<?> c) {return batchRemove(c, false);}// 保留所有ArrayList和Collection共有的元素public boolean retainAll(Collection<?> c) {return batchRemove(c, true);}private boolean batchRemove(Collection<?> c, boolean complement) {final Object[] elementData = this.elementData;int r = 0, w = 0;boolean modified = false;try {for (; r < size; r++)if (c.contains(elementData[r]) == complement)elementData[w++] = elementData[r];} finally {// Preserve behavioral compatibility with AbstractCollection,// even if c.contains() throws.if (r != size) {System.arraycopy(elementData, r,elementData, w,size - r);w += size - r;}if (w != size) {// clear to let GC do its workfor (int i = w; i < size; i++)elementData[i] = null;modCount += size - w;size = w;modified = true;}}return modified;}// java.io.Serializable的写入函数// 将ArrayList的“容量,所有的元素值”都写入到输出流中private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException{// Write out element count, and any hidden stuffint expectedModCount = modCount;s.defaultWriteObject();// Write out size as capacity for behavioural compatibility with clone()s.writeInt(size);// Write out all elements in the proper order.for (int i=0; i<size; i++) {s.writeObject(elementData[i]);}if (modCount != expectedModCount) {throw new ConcurrentModificationException();}}// java.io.Serializable的读取函数:根据写入方式读出// 先将ArrayList的“容量”读出,然后将“所有的元素值”读出private void readObject(java.io.ObjectInputStream s)throws java.io.IOException, ClassNotFoundException {elementData = EMPTY_ELEMENTDATA;// Read in size, and any hidden stuffs.defaultReadObject();// Read in capacitys.readInt(); // ignoredif (size > 0) {// be like clone(), allocate array based upon size not capacityensureCapacityInternal(size);Object[] a = elementData;// Read in all elements in the proper order.for (int i=0; i<size; i++) {a[i] = s.readObject();}}}// 返回一个从指定位置开始遍历的ListIterator迭代器public ListIterator<E> listIterator(int index) {if (index < 0 || index > size)throw new IndexOutOfBoundsException("Index: "+index);return new ListItr(index);}// 返回一个ListIterator迭代器public ListIterator<E> listIterator() {return new ListItr(0);}// 返回一个Iterator迭代器public Iterator<E> iterator() {return new Itr();}// 返回一个指定范围的子List列表public List<E> subList(int fromIndex, int toIndex) {subListRangeCheck(fromIndex, toIndex, size);return new SubList(this, 0, fromIndex, toIndex);}
}

5 ArrayList方法

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【C#】使用代码实现龙年春晚扑克牌魔术(守岁共此时),代码实现篇

欢迎来到《小5讲堂》 大家好&#xff0c;我是全栈小5。 这是《C#》系列文章&#xff0c;每篇文章将以博主理解的角度展开讲解&#xff0c; 特别是针对知识点的概念进行叙说&#xff0c;大部分文章将会对这些概念进行实际例子验证&#xff0c;以此达到加深对知识点的理解和掌握。…

DS:栈和队列的相互实现

创作不易&#xff0c;感谢友友们三连&#xff01;&#xff01; 一、前言 栈和队列的相互实现是用两个栈去实现队列或者是用两个队列去实现栈&#xff0c;这样其实是把问题复杂化的&#xff0c;实际中没有什么应用价值&#xff0c;但是通过他们的相互实现可以让我们更加深入地理…

PyTorch使用Tricks:Dropout,R-Dropout和Multi-Sample Dropout等 !!

文章目录 1、为什么使用Dropout&#xff1f; 2、Dropout的拓展1&#xff1a;R-Dropout 3、Dropout的拓展2&#xff1a;Multi-Sample Dropout 4、Dropout的拓展3&#xff1a;DropConnect 5、Dropout的拓展4&#xff1a;Standout 6、Dropout的拓展5&#xff1a;Gaussian Dropout …

Jest和Mocha对比:两者之间有哪些区别?

什么是单元测试&#xff1f; 所谓单元测试&#xff0c;是对软件中单个功能组件进行测试的一种软件测试方式&#xff0c;其目的是确保代码中的每一个基本单元都能正常运行。因此&#xff0c;开发人员在应用程序开发的整个过程&#xff08;即代码编写过程&#xff09;中都需要进行…

Avalonia学习(二十四)-系统界面

目前项目式练习&#xff0c;界面内容偏多&#xff0c;所以不给大家贴代码了&#xff0c;可以留言交流。此次为大家展示的是物联项目的例子&#xff0c;仅仅是学习&#xff0c;我把一些重点列举一下。 界面无边框 以前的样例主要是通过实现控件来完成的&#xff0c;前面已经有窗…

美团外卖商超药店商品销量

外卖药店商品月销量 外卖商超商品月销量

学习总结19

# 奶牛的耳语 ## 题目描述 在你的养牛场&#xff0c;所有的奶牛都养在一排呈直线的牛栏中。一共有 n 头奶牛&#xff0c;其中第 i 头牛在直线上所处的位置可以用一个整数坐标 pi(0< pi < 10^8) 来表示。在无聊的日子里&#xff0c;奶牛们常常在自己的牛栏里与其它奶牛交…

术业有专攻!三防加固平板助力工业起飞

在日常使用中的商业电脑比较追求时效性&#xff0c;以市场定位做标准&#xff0c;内部元件只需满足一般要求就行&#xff0c;使用寿命比较短。而三防平板电脑是主要运用在复杂、恶劣的环境下所以在需求方面较高,需要保证产品在恶劣条件下正常使用&#xff0c;满足行业领域的需求…

Jakarta Bean Validation

Validation 官网 https://beanvalidation.org/ 常见注解 Bean Validation中定义的注解&#xff1a; 注解详细信息Null被注释的元素必须为 nullNotNull被注释的元素必须不为 nullAssertTrue被注释的元素必须为 trueAssertFalse被注释的元素必须为 falseMin(value)被注释的元素…

【linux】体系结构和os管理

冯诺依曼体系结构 输入单元&#xff1a;包括键盘, 鼠标&#xff0c;扫描仪, 写板等 中央处理器(CPU)&#xff1a;含有运算器和控制器等 输出单元&#xff1a;显示器&#xff0c;打印机等 这里的存储器指的是内存 三者是相互连接的&#xff0c;设备之间会进行数据的来回拷贝&am…

【springboot+vue项目(十五)】基于Oauth2的SSO单点登录(二)vue-element-admin框架改造整合Oauth2.0

Vue-element-admin 是一个基于 Vue.js 和 Element UI 的后台管理系统框架&#xff0c;提供了丰富的组件和功能&#xff0c;可以帮助开发者快速搭建现代化的后台管理系统。 一、基本知识 &#xff08;一&#xff09;Vue-element-admin 的主要文件和目录 vue-element-admin/ |…

人工智能_普通服务器CPU_安装清华开源人工智能AI大模型ChatGlm-6B_001---人工智能工作笔记0096

使用centos安装,注意安装之前,保证系统可以联网,然后执行yum update 先去更新一下系统,可以省掉很多麻烦 20240219_150031 这里我们使用centos系统吧,使用习惯了. ChatGlm首先需要一台个人计算机,或者服务器, 要的算力,训练最多,微调次之,推理需要算力最少 其实很多都支持C…

stable diffusion webui学习总结(2):技巧汇总

一、脸部修复&#xff1a;解决在低分辨率下&#xff0c;脸部生成异常的问题 勾选ADetailer&#xff0c;会在生成图片后&#xff0c;用更高的分辨率&#xff0c;对于脸部重新生成一遍 二、高清放大&#xff1a;低分辨率照片提升到高分辨率&#xff0c;并丰富内容细节 1、先通过…

【LeetCode】树的BFS(层序遍历)精选6题

目录 1. N 叉树的层序遍历&#xff08;中等&#xff09; 2. 二叉树的锯齿形层序遍历&#xff08;中等&#xff09; 3. 二叉树的最大宽度&#xff08;中等&#xff09; 4. 在每个树行中找最大值&#xff08;中等&#xff09; 5. 找树左下角的值&#xff08;中等&#xff09…

票务系统平台架构设计与实现

票务系统是一个复杂的平台&#xff0c;涉及到用户购票、票务管理、支付结算等多方面功能。本文将介绍票务系统平台的架构设计原则、技术选型以及实现过程&#xff0c;帮助读者了解如何构建一个高效、稳定的票务系统。 正文&#xff1a; 1. 系统设计原则 在设计票务系统平台时…

【计算机网络】网络基础

初识网络 一、网络发展二、认识协议三、认识网络协议1. 协议分层2. OSI 七层模型3. TCP/IP五层模型4. OS和网络协议栈 四、网络传输基本流程1. TCP/IP 协议通讯过程2. 以太网通信&#xff08;1&#xff09;以太网通信原理&#xff08;2&#xff09;数据碰撞 3. 数据跨网络传输 …

计算机网络概论和数据通信基础

文章目录 计算机网络概论从物理构成上看&#xff0c;计算机网络包括硬件、软件和协议三大部分计算机网络的功能组成计算机网络的分类网络体系结构分层与体系结构接口、协议和服务数据传送单位OSI模型TCP/IP模型 数据通信基础数字信号调制为模拟信号正交振幅调制QAM 模拟数据编码…

STM32Cubemx TB6612直流电机驱动

一、TB6612FNG TB6612是一个支持双电机的驱动模块&#xff0c;支持PWM调速。PWMA、AIN1、AIN2 为一组控制引脚&#xff0c;PWMA 为 PWM 速度控制引脚&#xff0c;AIN1、AIN2 为方向控制引脚&#xff1b;PWMB、BIN1、BIN2 为一组控制引脚&#xff0c;PWMB 为 PWM 速度控制引脚&…

例40:滚动条的使用

建立一个EXE工程&#xff0c;在窗体上放一个文本框和一个水平滚动条。设置滚动条的最大最小属性分别为&#xff1a;100和1。如图36。 图36 为滚动条的change事件输入代码&#xff1a; Sub Form1_HScroll1_Change(hWndForm As hWnd, hWndControl As hWnd, hNewPos As Long, n…

【高效开发工具系列】PyCharm使用

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…