资讯专栏INFORMATION COLUMN

实现一个ArrayList过程

NickZhou / 1349人阅读

摘要:构造器一个无参构造器一个参数为型的有参构造器一个参数为型的有参构造器。参数为型的构造器用来实现将其他继承类的容器类转换成。此处仅实现前两种。默认的大小无参构造器中的是定义的私有变量,默认值是,用来创建一个大小为的数组。

前言

ArrayList,可随意添加和删除元素而不许考虑数组的大小。

构造器

一个无参构造器、一个参数为int型的有参构造器、一个参数为Collection型的有参构造器。参数为Collection型的构造器用来实现将其他继承Collection类的容器类转换成ArrayList。此处仅实现前两种。

public ArrayListDemo(){
 this(DEFAULT_CAPACITY);
}
public ArrayListDemo(int size){
 if (size < 0){
  throw new IllegalArgumentException("默认的大小" + size);
 }else{
  elementData = new Object[size];
 }
}

无参构造器中的DEFAULT_CAPACITY是定义的私有变量,默认值是10,用来创建一个大小为10的数组。有参构造器中,则是通过int参数来生成指定大小的Object数组。而可以看到elementData才是真正的用来存储元素的数组。

add方法

核心内容是往容器中添加元素,add方法有两个重载方法,一个是add(E e),另一个是add(int index,E e),但是其还要处理动态数组,即数组大小不满足的时候,扩大数组的内存。

public void add(E e){
 isCapacityEnough(size + 1);
 elementData[size++] = e;
}

isCapacityEnough方法用来判断是否需要扩容,传入的参数就是最小的扩容空间。因为add一个元素,所以最小的扩容空间,即所有元素+1,这里的size就是真正的元素个数。

private void isCapacityEnough(int size){
 if (size > DEFAULT_CAPACITY){
  explicitCapacity(size);
 }
 if (size < 0){
  throw new OutOfMemoryError();
 }
}

判断需要扩容的空间是不是比默认的空间大,如果需要的空间比默认的空间大,就调用explicitCapacity继续扩容,这里有个size小于0的判断,出现size小于0主要因为当size超过Integer.MAX_VALUE就会变成负数。

private final static int MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;
private void explicitCapacity(int capacity){
 int newLength = elementData.length * 2;
 if (newLength - capacity < 0){
  newLength = capacity;
 }
 if (newLength > (MAX_ARRAY_LENGTH)){
  newLength = (capacity > MAX_ARRAY_LENGTH ? Integer.MAX_VALUE : MAX_ARRAY_LENGTH);
 }
 elementData = Arrays.copyOf(elementData, newLength);
}

首先,定义一个数组最大的容量的常理为最大值,这个值按照官方的源码中的解释是要有些VM保留了数组的头部信息在数组中,因此实际存放数据的大小就是整数的最大值 - 8.

接着设定一个要扩容的数组的大小,虽然上面说了有一个扩容空间的值size+1,这个是实际我们最小需要扩容的大小。但为了继续增加元素,而不频繁的扩容,因此一次性的申请多一些的扩容空间。newlength打算申请为数组长度的2倍,然后去判断这个长度是否满足需要的扩容空间的值,即有了后续的两段代码

if (newLength - capacity < 0){
 newLength = capacity;
}
if (newLength > (MAX_ARRAY_LENGTH)){
 newLength = (capacity > MAX_ARRAY_LENGTH ? Integer.MAX_VALUE : MAX_ARRAY_LENGTH);
}

如果2倍的长度仍然不满足,则申请到需要的扩容长度。在我们只增加一个元素的情况下,这个判断是永远不会生效的,但是如果有addAll方法,则增加的元素很多,就要导致一次申请2倍的长度是不够的。第二个判断是判断newLength的长度如果超过上面定义的数组最大长度则判断要需要的扩容空间是否大于数组最大长度,如果大于则newLength为 MAX_VALUE ,否则为 MAX_ARRAY_LENGTH。

最后,调用Arrays.copyOf(elementData, newLength)得到一个扩容后的数组。

add的另一个重载方法如下

public void add(int index, E e) {
 //判断是不是越界
 checkRangeForAdd(index);
 //判断需不需要扩容
 isCapacityEnough(size + 1);
 //将index的元素及以后的元素向后移一位
 System.arraycopy(elementData,index,elementData,index + 1,size - index);
 //将index下标的值设为e
 elementData[index] = e;
 size++;
}
private void checkRangeForAdd(int index){
 //这里index = size是被允许的,即支持头,中间,尾部插入
 if (index < 0 || index > size){
  throw new IndexOutOfBoundsException("指定的index超过界限");
 }
}
get方法

用来得到容器中指定下标的元素

private void checkRange(int index) {
 if (index >= size || index < 0){
  throw new IndexOutOfBoundsException("指定的index超过界限");
 }
}
public E get(int index){
 checkRange(index);
 return (E)elementData[index];
}
indexOf方法

用来得到指定元素的下标,判断传入的元素是否为null,如果为null,则依次与null。如果不为空,则用equals依次比较。匹配成功就返回下标,匹配失败就返回-1。

public int indexOf(Object o){
 if (o != null) {
  for (int i = 0 ; i < size ; i++){
   if (elementData[i].equals(0)){
    return i;
   }
  }
 }else {
  for (int i = 0 ; i < size ; i++){
   if (elementData[i] == null) {
    return i;
   }
  }
 }
 return -1;
}
contains方法

用来判断该容器中是否包含指定的元素。在有了indexOf方法的基础上,contains的实现就很简单了。

public boolean contains(Object o){
return indexOf(o) >= 0;
}
size方法

用来得到容器类的元素个数,实现很简单,直接返回size的大小即可。

public int size(){
 return size;
}
isEmpty方法

用来判断容器是否为空,判断size方法的返回值是否为0即可。

public boolean isEmpty(){
 return size() == 0;
}
remove方法

用来对容器类的元素进行删除,与add一样,remove方法也有两个重载方法,分别是remove(Object o)和remove(int index)

public E remove(int index) {
 E value = get(index);
 int moveSize = size - index - 1;
 if (moveSize > 0){
  System.arraycopy(elementData,index + 1, elementData,index,size - index - 1);
 }
 elementData[--size] = null;
 return value;
}
 
public boolean remove(Object o){
 if (contains(o)){
  remove(indexOf(o));
  return true;
 }else {
  return false;
 }
}

第一个remove方法是核心方法,首先得到要删除的下标元素的值,然后判断index后面的要前移的元素的个数,如果个数大于零,则调用库方法,将index后面的元素向前移一位。最后elementData[--size] = null;缩减size大小,并将原最后一位置空。

第二个remove方法不需要向第一个方法一样,需要告诉使用者要删除的下标对应的元素,只需要判断是否删除成功即可。如果要删除的元素在列表中,则删除成功,如果不在则失败。因此调用contains方法就可以判断是否要删除的元素在列表中。在则调用remove(int index),不在则返回失败。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/71914.html

相关文章

  • 数组和列表的转换问题

    摘要:以下指代数组,指代数组列表。常见的转换方法是或。在的使用过程中需要注意,当要转换的长度小于的时,不要试图通过传入形参的方式进行转换,虽然这在的长度大于时不会出现问题。所以,极度建议在转换之前初始化的长度为的,并且使用返回值重新给赋值。 Array 和 List 都是我们在开发过程中常见的数据结构。我们都知道 Array 是定长的,List 是可变长。而且,List 的实现类 Array...

    ChristmasBoy 评论0 收藏0
  • Java笔记-容器源码(持续更新)

    摘要:加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行操作即重建内部数据结构,从而哈希表将具有大约两倍的桶数。成员变量每个对由封装,存在了对象数组中。 虽是读书笔记,但是如转载请注明出处 http://segmentfault.com/blog/exploring/ .. 拒绝伸手复制党 LinkedLis...

    mrli2016 评论0 收藏0
  • Java容器类研究4:ArrayList

    摘要:显然,开发人员认为通过下标遍历的数组结构更加高效。在进行分裂时,原始保留中部至末尾的元素,新的保留原起始位置到中部的元素。同样,也会进行重新赋值,使得在使用前与保持一致。在遍历时,会调用方法,将动作施加于元素之上。 java.util.ArrayList ArrayList继承自AbstractList,AbstractList为随机访问数据的结构,如数组提供了基本实现,并且提供了It...

    xfee 评论0 收藏0
  • 深入了解Java集合中的ArrayList

    摘要:实现了接口,所以包含的基本方法新增,删除,插入等都实现了。线程安全问题在多线程情况下有线程进行修改时,是线程不安全的。线程安全性问题,取决于如何应用。反映的是当前数组中存了多少数据,而则反映的是内部数组的容量。 什么是ArrayList ArrayList 是一个可扩容数组Resizable-array,它实现了List接口的所有方法。 从对ArrayList的简单描述中我们可以得出...

    zeyu 评论0 收藏0
  • Java集合干货——ArrayList源码分析

    摘要:关于的具体实现,一些基本的都也知道,譬如数组实现,线程不安全等等,但是更加具体的就很少去了解了,例如初始化的长度,扩容等。 前言 在之前的文章中我们提到过ArrayList,ArrayList可以说是每一个学java的人使用最多最熟练的集合了,但是知其然不知其所以然。关于ArrayList的具体实现,一些基本的都也知道,譬如数组实现,线程不安全等等,但是更加具体的就很少去了解了,例如:...

    Render 评论0 收藏0
  • Java集合干货——ArrayList源码分析

    摘要:关于的具体实现,一些基本的都也知道,譬如数组实现,线程不安全等等,但是更加具体的就很少去了解了,例如初始化的长度,扩容等。 前言 在之前的文章中我们提到过ArrayList,ArrayList可以说是每一个学java的人使用最多最熟练的集合了,但是知其然不知其所以然。关于ArrayList的具体实现,一些基本的都也知道,譬如数组实现,线程不安全等等,但是更加具体的就很少去了解了,例如:...

    wupengyu 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<