java基础-数组扩容详解
作者:haijiao12138 发布时间:2022-05-24 00:34:58
数组与链表的比较:
数组通过下标访问的话是O(1)
数组一旦声明 长度就是固定的
数组的数据是物理逻辑均连续的
链表增删要快一些, 数组遍历快一些
长度一定的话, 数组的存储空间比链表要小
ArrayList:
ArrayList是List接口的实现类,它是支持根据需要而动态增长的数组;java中标准数组是定长的,在数组被创建之后,它们不能被加长或缩短。这就意味着在创建数组时需要知道数组的所需长度,但有时我们需要动态程序中获取数组长度。ArrayList就是为此而生的。
扩容机制发生在add()方法调用的时候;
public boolean add(E e) {
//扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
该行代码ensureCapacityInternal()是用来扩用的,形参是最小扩容量,进入该方法后:
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
通过方法calculateCapacity(elementData, minCapacity)获取:
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果传入的是个空数组则最小容量取默认容量与minCapacity之间的最大值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
使用 ensureExplicitCapacity方法可以判断是否需要扩容:
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果最小需要空间比elementData的内存空间要大,则需要扩容
if (minCapacity - elementData.length > 0)
//扩容
grow(minCapacity);
}
需要扩容,进入ArrayList扩容的关键方法grow():扩大为原来的1.5倍;
private void grow(int minCapacity) {
// 获取到ArrayList中elementData数组的内存空间长度
int oldCapacity = elementData.length;
// 扩容至原来的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 再判断一下新数组的容量够不够,够了就直接使用这个长度创建新数组,
// 不够就将数组长度设置为需要的长度
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//若预设值大于默认的最大值检查是否溢出
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 调用Arrays.copyOf方法将elementData数组指向新的内存空间时newCapacity的连续空间
// 并将elementData的数据复制到新的内存空间
elementData = Arrays.copyOf(elementData, newCapacity);
}
复制代码
至此得出ArrayList扩容的本质是计算出新的扩容数组的size后实例化,并将原有数组内容复制到新数组中去。
LinkedList:
链表实现扩容,直接在尾指针后面加入新的元素即可。
实现LinkedList:LinkedList的底层实现是链表。更深理解是一个双向链表。
节点代码:
//节点
public class Node {
Node previous;//前继,指向前一个Node
Object data;//节点数据
Node next;//后继,指向后一个Node
public Node() {
}
public Node(Node previous, Object data, Node next) {
super();
this.previous = previous;
this.data = data;
this.next = next;
}
}
初始化MyLinkedList:
public class MyLinkedList {
private Node first;//首节点
private Node last;//尾节点
private int size;//链表大小
public MyLinkedList() {
first = null;
last = null;
size = 0;
}
}
尾部添加,实现add(Object obj)方法:
public void add(Object obj){
Node node = new Node(null,null,null);
if(first==null){//first=null,说明LinkedList中没有一个节点
node.data = obj;
first = node;
last = node;//第一个节点和最后一个节点都是node
size++;
}else{
node.data = obj;
last.next = node;//和最后一个连接起来
node.previous = last;
last = node;//当前节点变为末尾节点
size++;
}
现get(int index)方法,获取index处的节点并返回Node:
使用循环,遍历链表:
public Node get(int index) {
RangeCheck(index);
Node temp = null;
if(index < (size>>1)){//改进的遍历方法,右移运算符的巧用
temp = first;
for(int i=0;i<index;i++){
temp = temp.next;
}
}else {
temp = last;
for(int i=size-1;i>index;i--){
temp = temp.previous;
}
}
return temp;
}
任意位置插入,实现add(int index,Object obj)方法:插入的步骤注意顺序,不要产生断链。
public void add(int index,Object obj) {
RangeCheck(index);//对传入的索引必须进行检查,判断是否越界
Node node = new Node(null,null,null);
node.data = obj;
Node node2=first;
for(int i=0;i<index-1;i++){
node2 = node2.next;
}
node.next = node2.next;
node2.next.previous=node;
node2.next = node;
node.previous=node2;
size++;
}
RangeCheck():
private void RangeCheck(int index) {
if(index<0||index >= size){
throw new IndexOutOfBoundsException("IndexOutOfBounds"+index);//不合法则抛出异常
}
}
实现remove(Object obj)方法:
public boolean remove(Object obj) {
Node node = first;
if(obj==null){
while(node!=null){
if(node.data==null){
removefast(node);
return true;
}
node = node.next;
}
}else {
while(node!=null){
if(obj.equals(node.data)){
removefast(node);
return true;
}
node = node.next;
}
}
return false;
}
private void removefast(Node node){
node.previous.next=node.next;
size--;
node.data=null;
node.previous = node.next = null;
}
实现set(int index,Object obj)方法:
public Object set(int index,Object obj) {
Node node = get(index);
Object oldObject=node.data;
node.data = obj;
return oldObject;
}
来源:https://blog.csdn.net/qq_40604313/article/details/118683783
猜你喜欢
- thymeleaf介绍简单说, Thymeleaf 是一个跟 Velocity、FreeMarker 类似的模板引擎,它可以完全替代 JSP
- 本篇给大家详细讲解了MTKAndroid平台开发流程,大致分为44个步骤,我们把每个步骤的命令详细讲解了下,一起来学习下。1.拷贝代码仓库从
- 本文我将要介绍一下mybatis的框架原理,以及mybatis的入门程序,实现用户的增删改查,她有什么优缺点以及mybatis和hibern
- 本文实例总结了MFC程序设计常用技巧。分享给大家供大家参考。具体如下:1.属性页的添加:创建对话框的类,该类要从CpropertyPage继
- 封面图下个季度的目标是把前端监控相关的内容梳理出来,梳理出来之后可能会在公司内部做个分享~Flutter应用程序既括代码也包括一些其他的资产
- Java xml出现错误 javax.xml.transform.TransformerException: java.lang.NullP
- 可以给已有实体类动态的添加字段并返回新的实体对象,不影响原来的实体对象结构。添加依赖<dependency> &n
- 调用和回调机制在一个应用系统中, 无论使用何种语言开发, 必然存在模块之间的调用, 调用的方式分为几种:1.同步调用同步调用是最基本并且最简
- 前言:本文主要讲解以c语言编写猜数字游戏,目的是介绍C语言中的循环和分支的具体用法。一:猜数字游戏基本介绍&对程序预期.猜数字游戏,
- 本文实例为大家分享了java仿windows记事本小程序的具体代码,供大家参考,具体内容如下import java.awt.Checkbox
- 面试题1:说一下抽象类和接口有哪些区别?正经回答:抽象类和接口的主要区别:从设计层面来说,抽象类是对类的抽象,是一种模板设计;接口是行为的抽
- 1、引入依赖<dependency> <groupId>org.apache.pdfbox</gr
- 当目标数据库不能直连的,需要一个服务器作为中间跳板的时候,我们需要通过SSH通道连接数据库。ps:使用ssh连接,相当于本地开了个端口去连接
- springboot配置文件中属性变量引用@@这种属性应用方式是field_name=@field_value@。两个@符号是springb
- Spring Boot 自动装配最重要的注解@SpringBootApplication@Target(ElementType.TYPE)@
- 一、什么是网关限流:在微服务架构中,网关层可以屏蔽外部服务直接对内部服务进行调用,对内部服务起到隔离保护的作用,网关限流,顾名思义,就是通过
- 什么是WebSocket?WebSocket协议是基于TCP的一种新的网络协议。它实现了浏览器与服务器全双工(full-duplex)通信—
- 前言 实际业务开发中,集合的判断和操作也是经常
- 前言最近一直被无尽的业务需求淹没,没时间喘息,终于接到一个能让我突破代码舒适区的活儿,解决它的过程非常曲折,一度让我怀疑人生,不过收获也很大
- 1.获取签名与模板进入阿里云平台,进入短信服务模块,在以下位置添加签名和模板(格式一定按照要求填写 审批的比较严格)2.编写模板与签名的枚举