JAVA 用数组实现 ArrayList

  我们知道 ArrayList 是一个集合,它能存放各种不同类型的数据,而且其容量是自动增长的。那么它是怎么实现的呢?

  其实 ArrayList 的底层是用 数组实现的。我们查看 JDK 源码也可以发现。而用数组实现集合的原理有两点:

  1、能自动扩容

  2、能存放不同类型的数据

这两点我们是这样解决的:

  1、当一个数据存放满了,我们就将这个数据复制到一个新的数组中,而这个新的数组容量要比原数组大。通过这样不断的扩大数组长度,也就是集合的容量。那么这里我们用到了这个方法  System.arraycopy

完整的写法为:public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

参数

@ src -- 这是源数组 @ srcPos -- 这是源数组中的起始位置 @dest -- 这是目标数组 @ destPos -- 这是目标数据中的起始位置  @ length -- 这是一个要复制的数组元素的数目

int arr1[] = {0,1,2,3,4,5};
int arr2[] = {0,10,20,30,40,50};
System.arraycopy(arr1,0,arr2,1,2);
//结果为:arr2 = [0,0,1,30,40,50];

  2、第二个问题,我们只需要声明为 Object 类型的数组就可以了。

完整代码如下:

package com.ys.collection;

public class MyArrayList {
	//用于存储数据
	private transient Object[] data = null;
	//集合的元素个数
	private int size = 0;
	//定义一个常量为 10.(后面用于定义默认的集合大小)
	private static final int DEFAULT_CAPACITY = 10;
	
	/***
	 * 有参构造函数
	 * 指定数组的大小
	 * @param length   
	 */
	public MyArrayList(int initialCapacity){
		if(initialCapacity < 0){
			throw new IllegalArgumentException("非法的集合初始容量值 Illegal Capacity: "+
					initialCapacity);
		}else{
			//实例化数组
			this.data = new Object[initialCapacity];
		}
	}
	
	/***
	 * 无参构造函数
	 * 指定数组的初始大小为 10
	 */
	public MyArrayList(){
		this(DEFAULT_CAPACITY);
	}
	
	/***
	 * 1、复制原数组,并扩容一倍
	 * 2、复制原数组,并扩容一倍,并在指定位置插入对象
	 * @param index
	 * @param obj
	 */
	public void checkIncrease(int index,Object obj){
		if(size >= data.length){
			//实例化一个新数组
			Object[] newData = new Object[size*2];
			
			if(index == -1 && obj == null){
				System.arraycopy(data, 0, newData, 0, size);
			}else{
				//将要插入索引位置前面的对象 拷贝
				System.arraycopy(data, index, newData, index+1, size-index);
			}
			
			//将 newData 数组赋值给 data数组
			data = newData;
			newData = null;
		}
	}
	
	/***
	 * 获取数组的大小
	 * @return
	 */
	public int getSize(){
		return this.size;
	}
	
	/***
	 * 根据元素获得在集合中的索引
	 * @param o
	 * @return
	 */
	public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < data.length; i++)
                if (data[i]==null)
                    return i;
        } else {
            for (int i = 0; i < data.length; i++)
                if (o.equals(data[i]))
                    return i;
        }
        return -1;
    }
	
	/***
	 * 在尾部添加元素
	 * @param obj
	 * @return
	 */
	public boolean add(Object obj){
		//检查是否需要扩容
		checkIncrease(-1, null);
		data[size++] = obj;
		return true;
		
	}
	
	/**
	 * 判断给定索引是否越界
	 * @param index
	 * @return
	 */
	public boolean checkIndexOut(int index){
		if(index > size || index < 0){
			throw new IndexOutOfBoundsException("指定的索引越界,集合大小为:"+size+",您指定的索引大小为:"+index);
		}
		return true;
	}
	
	public boolean add(int index,Object obj){
		//如果给定索引长度刚好等于原数组长度,那么直接在尾部添加进去
		if(index == size){
			add(obj);
		}
		//checkIndexOut()如果不抛异常,默认 index <=size,且 index > 0
		else if(checkIndexOut(index)){	
			if(size < data.length){
				System.arraycopy(data, index, data, index+1, size-index);
				data[index] = obj;
			}else{
				//需要扩容
				checkIncrease(index, obj);
			}
			size++;
		}
		
		return true;
	}
	
	/***
	 * 根据索引获得元素
	 * @param index
	 * @return
	 */
	public Object get(int index){
		checkIndexOut(index);
		return data[index];
		
	}
	
	/***
	 * 删除所有元素
	 */
	public void removeAll(){
		for(int i = 0 ; i < data.length ; i++){
			data[i] = null;
		}
	}
	
	/***
	 * 根据索引删除元素
	 * @param index
	 * @return
	 */
	public Object remove(int index){
		if(index == size+1){
			throw new IndexOutOfBoundsException("指定的索引越界,集合大小为:"+size+",您指定的索引大小为:"+index);
		}else if(checkIndexOut(index)){
			//保存对象
			Object obj = data[index];
			if(index == size){
				data[index] = null;
			}else{
				//将后边的数组向前移动一位
				System.arraycopy(data, index+1, data, index, size-index);
			}
			size--;
			return obj;
		}
		
		return null;
	}
	
	/***
	 * 删除指定的元素,删除成功返回 true,失败返回 false
	 * @param obj
	 * @return
	 */
	public boolean remove(Object obj){
		for(int i = 0 ; i < size ; i++){
			if(obj.equals(data[i])){
				remove(i);
				return true;
			}
		}
		return false;
	}
	
	/***
	 * 在指定位置修改元素,通过索引,修改完成后返回原数据
	 * @param index
	 * @param obj
	 * @return
	 */
	public Object change(int index,Object obj){
		checkIndexOut(index);
		Object oldObj = data[index];
		data[index] = obj;
		return oldObj;
	}
	
	/***
	 * 查看集合中是否包含某个元素,如果有,返回 true,没有返回 false
	 * @param obj
	 * @return
	 */
	public boolean contain(Object obj){
		for(int i = 0 ; i < data.length ; i++){
			if(obj.equals(data[i])){
				return true;
			}
		}
		return false;
	}
	
	
	
	
	
	public static void main(String [] args){
		
		MyArrayList my = new MyArrayList();
		//System.out.println(my.data.length);
		my.add(0,3);
		//System.out.println(my.getSize());
		my.add(0,4);
		//System.out.println(my.getSize());
		my.add(0,5);
		//my.removeAll();
		//my.remove(2);
		//System.out.println(my.get(2));
		System.out.println(my.indexOf(null));
		System.out.println(my.contain(2));
		for(int i = 0 ; i < my.data.length ; i++){
			System.out.println(my.data[i]);
		}
		
		
	}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏菜鸟致敬

Python中is和==的区别

Python中对象包含的三个基本要素,分别是:id(身份标识)、type(数据类型)和value(值)。

733
来自专栏lzj_learn_note

3-序列、列表、元组

序列就是一堆数据元素的集合,并对每个元素进行编号。在Python中,字符串、列表、元组都属于序列,他们都具有一些特定的操作,如索引、切片、相加、相乘、in、长度...

773
来自专栏King_3的技术专栏

leetcode-31-下一个排列

实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

512
来自专栏IT可乐

JDK1.8源码(一)——java.lang.Object类

  本系列博客将对JDK1.8版本的相关类从源码层次进行介绍,JDK8的下载地址。   首先介绍JDK中所有类的基类——java.lang.Object。   ...

50515
来自专栏debugeeker的专栏

《coredump问题原理探究》Linux x86版3.6节栈布局之gcc内嵌关键字

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xuzhina/article/detai...

461
来自专栏猿人谷

strcpy函数和strncpy函数的区别

strcpy函数和strncpy函数的原型介绍在我的另一篇文章中介绍了,见strcpy,strncpy,strlen等函数原型 strcpy:字串复制  ...

2196
来自专栏老司机的技术博客

宝宝都能学会的python编程教程6:列表(list)

上期编程题的答案如上图。 列表(list) list是一种有序的集合,可以随时添加和删除其中的元素。 当索引超出了范围时,Python会报一个IndexErr...

3356
来自专栏决胜机器学习

有趣的算法(五) ——Dijkstra双栈四则运算

有趣的算法(五)——Dijkstra双栈四则运算 (原创内容,转载请注明来源,谢谢) 一、概念 近期看到算法书上,提到dijkstra双栈的方法,实现输入一...

4427
来自专栏idba

理解Python 生成器与迭代器

前一段时间和同事聊到Python技术知识,发现自己对生成器,迭代器傻傻分不清楚,于是乎查文档,找资料,有了此文。

721
来自专栏一个会写诗的程序员的博客

《零基础 Java 开发 》 第五章 数组第五章 数组

数组是一个基础的数据结构,它用来存储一组相同类型的元素的集合。数组非常有用,例如Java提供的集合类ArrayList、HashMap等都是基于数组来实现的。

683

扫码关注云+社区