Java使用数组实现ArrayList的动态扩容的方法
作者:小梁coding 发布时间:2023-03-23 11:24:39
提到数组大家肯定不会陌生,但我们也知道数组有个缺点就是在创建时就确定了长度,之后就不能更改长度。所以Java官方向我们提供了ArrayList这个可变长的容器。其实ArrayList底层也是用数组进行实现的,今天我们就自己使用数组实现ArrayList的功能。
一、整体框架
废话不多说,我们以存放int类型元素为例,看一下ArrayList需要的成员变量和需要实现的方法。
public class ArrayList
private int size;//用来记录实际存储元素个数
private int[] elements;//用来存储元素的数组
//构造方法:在创建ArrayList对象时,初始化elements数组
public ArrayList(int capacity){
elements = new int[capacity];
}
/**
* 元素的数量
* @return
*/
public int size() {}
/**
* 是否为空
* @return
*/
public boolean isEmpty() {}
/**
* 查看元素的索引
* @param element
* @return
*/
public int indexOf(int element) {}
/**
* 是否包含元素
* @param element
* @return
*/
public boolean contains(int element) {}
/**
* 获取index位置的元素
* @param index
* @return
*/
public int get(int index) {}
/**
* 设置index位置的元素
* @param index
* @param element
* @return 原来的元素
*/
public int set(int index, int element) {}
/**
* 在index索引位置插入元素
* @param index
* @param element
*/
public void add(int index, int element) {}
/**
* 添加元素到尾部
* @param element
*/
public void add(int element) {}
/**
* 删除index位置的元素
* @param index
* @return
*/
public int remove(int index) {}
/**
* 清除所有元素
*/
public void clear() {}
/**
* 用来打印列表
*/
public String toString() {}
}
二、方法实现
框架我们已经有了,接下来我们一步步实现方法就行。
size()方法:
这个方法很简单,因为我们有size属性,直接将其返回就行了。
public int size() {
return size;
}
isEmpty()方法:
这个方法也很简单,判断是否为空只需要判断size是否为0即可。
public boolean isEmpty() {
return size == 0;
}
indexOf(int element)方法:
这个方法是用来查询元素的所在索引位置,并返回。我们通过遍历列表查找即可,找到就将元素返回,没有找到返回-1。
public int indexOf(int element) {
for (int i = 0; i < size; i++) {
if (element.equals(elements[i])) {
return i;
}
return -1;
}
contains(int element)方法:
这个方法是用来查看所传元素是否在数组中,我们可以直接通过indexOf()方法查看返回值是否不等于-1,不等于-1返回true,等于-1返回false。
public boolean contains(int element) {
return indexOf(element) != -1;
}
get(int index)方法:
这个方法用来获取指定索引位置的元素,我们直接返回数组的指定索引位置元素即可。
public int get(int index) {;
return elements[index];
}
set(int index, int element)方法:
这个方法用来将指定索引位置元素改为指定元素,并将原来元素返回,我们通过数组索引获取到该位置元素,并将指定元素赋值给该位置索引并将原来元素返回。
public int set(int index, int element) {
int old = elements[index];
elements[index] = element;
return old;
}
add(int index, int element)方法:
个方法是在指定索引位置插入指定元素,我们首先将指定索引位置的元素以及之后所有的元素向后移动一位,然后再将指定元素赋值给数组的指定索引位置,最后并将size加1。
public void add(int index, int element) {
for (int i = size; i > index; i--) {
elements[i] = elements[i - 1];
}
elements[index] = element;
size++;
}
add(int element)方法:
这个方法是在数组尾部添加元素,我们直接调用add(int index, int element)方法,将size作为index的参数传入即可。
public void add(int element) {
add(size, element);
}
remove(int index)方法:
这个方法用来删除指定索引位置的元素,并将要删除元素返回,我们首先通过指定索引获取原来元素,当删除该元素后需要将index索引后面的所有元素向前移动一位,最后将size减1。
public int remove(int index) {
int old = elements[index];
for (int i = index + 1; i < size; i++) {
elements[i - 1] = elements[i];
}
size--;
return old;
}
clear()方法:
这个方法,用于清空数组中所有元素,我们只需要将size赋值为0即可。
public void clear() {
size = 0;
}
toString()方法:
这个方法用于将所有元素打印出来,通过StringBuilder对象进行拼接,最后转成字符串返回即可。
public String toString() {
StringBuilder string = new StringBuilder();
string.append("size=").append(size).append(", [");
for (int i = 0; i < size; i++) {
if (i != 0) {
string.append(", ");
}
string.append(elements[i]);
}
string.append("]");
return string.toString();
}
以上代码基本实现了对数组的进行数据的增删改查,但最后想达到我们的目的还要进一步优化。
三、优化
1.实现动态扩容
当我们向数组中添加元素时,如果数组已经满了我们就需要就数组进行动态扩容。扩容的原理并不是真的对原数组进行增加内存操作,而是重新创建一个更大的数组,并将原数组的元素赋给新的数组。我们声明一个私有方法确保添加元素前数组的容量足够。
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (oldCapacity >= capacity) return;
// 新容量为旧容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
int[] newElements = new int[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
elements = newElements;
}
我们在add()方法中首先调用ensureCapacity(int capacity)方法进行判断数组容量是否足够,不够进行扩容。
public void add(int index, E element) {
ensureCapacity(size + 1);
for (int i = size; i > index; i--) {
elements[i] = elements[i - 1];
}
elements[index] = element;
size++;
}
2. 确保索引不越界
当我们在调用传入索引的方法时,首先要保证传入索引在可用范围内,不然会出现角标越界的异常。
定义outOfBound()方法,用于抛出角标越界异常信息。
private void outOfBounds(int index) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
定义rangeCheck()方法用于检查索引是否越界,如果越界,调用outOfBound()抛出异常。
private void rangeCheck(int index) {
if (index < 0 || index >= size) {
outOfBounds(index);
}
}
而对于调用add()方法时所传入的索引范围可以取到size位置,我们在定义一个rangeCheckForAdd()方法,用于检查调用add()方法时索引是否越界。
private void rangeCheckForAdd(int index) {
if (index < 0 || index > size) {
outOfBounds(index);
}
}
在get()方法,set()方法和remove()方法中,先调用rangeCheck()方法,检查传入索引是否越界。
public int get(int index) {
rangeCheck(index);
return elements[index];
}
public int set(int index, E element) {
rangeCheck(index);
int old = elements[index];
elements[index] = element;
return old;
}
public int remove(int index) {
rangeCheck(index);
int old = elements[index];
for (int i = index + 1; i < size; i++) {
elements[i - 1] = elements[i];
}
size--;
return old;
}
3. 设置常量以及重写构造方法
对于类中的常数我们更希望封装成常量,并且声明一个默认容量,希望在创建对象时未传入容量参数或传入容量参数过小直接创建一个相对大小合适的数组。
private static final int DEFAULT_CAPACITY = 10;//我们将默认容量设为10
private static final int ELEMENT_NOT_FOUND = -1;//我们将获取指定元素的索引时,未找到的返回值-1封装为常量
//声明无参构造方法,在调用无参构造方法是直接创建默认容量的数组
public ArrayList(){
elements = new int[DEFAULT_CAPACITY];
}
//声明有参构造方法,在传入参数小于默认容量时,我们仍然创建默认容量数组
public ArrayList(int capaticy) {
capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capaticy;
elements = new int[capaticy];
}
四、使用泛型
以上步骤已经使用数组完全实现了ArrayList的全部功能,但只能存放int类型的数据,如果我们希望储存其他类型的数据我们只需要使用Java中的泛型就能够完成。
思路与上述完全一样,整体代码如下:
public class ArrayList<E> {
/**
* 元素的数量
*/
private int size;
/**
* 所有的元素
*/
private E[] elements;
private static final int DEFAULT_CAPACITY = 10;
private static final int ELEMENT_NOT_FOUND = -1;
public ArrayList() {
elements = (E[]) new Object[DEFAULT_CAPACITY];
}
public ArrayList(int capaticy) {
capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capaticy;
elements = (E[]) new Object[capaticy];
}
/**
* 清除所有元素
*/
public void clear() {
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
}
/**
* 元素的数量
* @return
*/
public int size() {
return size;
}
/**
* 是否为空
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 是否包含某个元素
* @param element
* @return
*/
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/**
* 添加元素到尾部
* @param element
*/
public void add(E element) {
add(size, element);
}
/**
* 获取index位置的元素
* @param index
* @return
*/
public E get(int index) {
rangeCheck(index);
return elements[index];
}
/**
* 设置index位置的元素
* @param index
* @param element
* @return 原来的元素ֵ
*/
public E set(int index, E element) {
rangeCheck(index);
E old = elements[index];
elements[index] = element;
return old;
}
/**
* 在index位置插入一个元素
* @param index
* @param element
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacity(size + 1);
for (int i = size; i > index; i--) {
elements[i] = elements[i - 1];
}
elements[index] = element;
size++;
}
/**
* 删除index位置的元素
* @param index
* @return
*/
public E remove(int index) {
rangeCheck(index);
E old = elements[index];
for (int i = index + 1; i < size; i++) {
elements[i - 1] = elements[i];
}
elements[--size] = null;
return old;
}
/**
* 查看元素的索引
* @param element
* @return
*/
public int indexOf(E element) {
if (element == null) {
for (int i = 0; i < size; i++) {
if (elements[i] == null) return i;
}
} else {
for (int i = 0; i < size; i++) {
if (element.equals(elements[i])) return i;
}
}
return ELEMENT_NOT_FOUND;
}
/**
* 保证要有capacity的容量
* @param capacity
*/
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (oldCapacity >= capacity) return;
// 新容量为旧容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
elements = newElements;
}
private void outOfBounds(int index) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
private void rangeCheck(int index) {
if (index < 0 || index >= size) {
outOfBounds(index);
}
}
private void rangeCheckForAdd(int index) {
if (index < 0 || index > size) {
outOfBounds(index);
}
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("size=").append(size).append(", [");
for (int i = 0; i < size; i++) {
if (i != 0) {
string.append(", ");
}
string.append(elements[i]);
}
string.append("]");
return string.toString();
}
}
来源:https://blog.csdn.net/weixin_44838502/article/details/106866724
猜你喜欢
- 前言:朋友们开始以下教程前,请先看第五大点的注意事项,以避免不必要的重复操作。 一、准备工作(以下为本实例使用工具)1、MyEcl
- java读写ini文件、FileOutputStream在上课让学生练习文件读写,就让他们做了一个使用文件保存账号和密码的练习,有一个比较爱
- Activiti 介绍Activiti是一个开源的工作流引擎,它实现了BPMN 2.0规范,可以发布设计好的流程定义,并通过api进行流程调
- 在 Java 语言中的类初始化块 文章中我们简单的介绍了下 Java 中的实例初始化块 ( IIB )。不过我觉得介绍的有点简单了,于是,再
- 我们开发任何一个Spring Boot项目,都会用到如下的启动类@SpringBootApplication public class Ap
- 定义Builder模式是一步步创建一个复杂对象的创建型模式,它允许用户在不知道内部构建细节的情况下,可以更精细的控制对象的构建过程。该模式是
- 早期的项目比较简单,多是用JSP 、Servlet + JDBC 直接搞定,后来使用 Struts1(Struts2)+Spring+Hib
- 最近同事问我有没有有关于技术的电子书,我打开电脑上的小书库,但是邮件发给他太大了,公司又禁止用文件夹共享,于是花半天时间写了个小的文件上传程
- 一、Spring Boot Admin 的概念 Spring Boot Admin是一个
- 一、链表的介绍什么是链表链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结
- 1、认识XML解析技术1.1、XML相关概念(1)DTD:XML语法规则,是XML文件的验证机制,可以通过比较XML文档和DTD文件看文档是
- 定义:用于顺序访问集合对象的元素,不需要知道集合对象的底层表示。特点: 1、它支持以不同的方式遍历一个
- Java 异常的栈轨迹(Stack Trace)详解 捕获到异常时,往往需要进行一些处理。比较简单直接的
- 本文实例为大家分享了C语言实现两个矩阵相乘的具体代码,供大家参考,具体内容如下程序功能:实现两个矩阵相乘的C语言程序,并将其输出代码如下:#
- 1 线程池的优势总体来说,线程池有如下的优势:(1)降低资源消耗。通过重复利用已创建的线程降低线程创建和销毁造成的消耗。(2)提高响应速度。
- 条件(也称为条件队列 或条件变量)为线程提供了一个含义,以便在某个状态条件现在可能为 true 的另一个线程通知它之前,一直挂起该线程(即让
- 一直使用的是FastJson,感觉还不错,很方便。看了一段别人的分析,觉得很有道理。为什么要使用Fastjson,其实原因不需要太多,喜欢就
- 如下所示: /** * 判断某个界面是否在前台 * * @param context
- Java是一门天然的面向对象的语言。而所有我们手动创造出来的类,都继承于同一个类,即Object类。可以看一下Object类的结构nativ
- 一.前言这一篇来看看 SpringIOC 里面的一个细节点 , 来简单看看 BeanDefinition 这个对象 , 以及有没有办法对其进