深入理解ArrayList(三)

欢迎点击「算法与编程之美」↑关注我们!

本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列博客。

在上一讲深入理解ArrayList(二)我们改进了代码,让其能够实现任意数据类型的插入操作,本节我们将在上一讲的基础上继续分析代码存在的问题,并提出改善代码的建议。

1 问题描述

我们来看一下,上一讲改进后的代码存在哪些问题,先来看一个简单的测试案例。

编写以上测试用例,运行后我们得到下面的错误信息。

虽然我们能够实现字符串的添加操作,但是当我们向MyList中添加11个字符串的时候,就出现了上面的错误。下面我们一起来分析这是原因导致的错误。

2 问题分析

这个错误相信大家平时在做数组的学习和开发的时候,经常会遇到ArrayIndexOutOfBoundsException,这是一个数组索引越界的异常,指的是我们当前的数组大小为10,即最大的下标索引为9,而在上述示例时,当i=10时满足i

仔细的分析这个问题,发现其根本原因在于初始化的时候指定了固定的数组大小,因为你指定了10,所以就意味着你只能插入10个字符串。

有些同学可能会说,初始化的时候,我指定其大小为10000,这种做法是否可行呢?

这种做法也不可取,原因有两点:

其一,10000的数组在初始化的时候,耗时较长,代价较高,万一用户最终添加的字符串只有10个以内呢,那你初始化10000是不是有点多此一举,不划算呢?

其二,用户在添加完10000个字符串后,还想继续添加呢?此时又回到了刚开始的问题,所以这种做法并没有从本质上解决问题。

仔细分析上述问题产生的原因在于数组下标越界,而数组下标越界的原因在于数组容量不够。因此核心的问题在于我们要解决在添加元素之前确保数组的容量是足够的。

如果当前容量不够的话,则需要分配新的数组,而如果使用新的数组,就需要把以前数组的内容复制到新数组,然后再添加新的元素。这些操作都是需要注意的地方。

3 解决方案

按照上面的思路我们需要做的工作有:

1)检查当前数组容量是否足够保存新添加的元素。

由于之前我们使用size变量标记当前数组的位置,因此可以通过size来获得当前数组已经保存了多少元素。当我们需要添加一个新的元素时,此时需要的数组最小容量minCapacity就是size+1。

另外当前数组的总容量是elementData.length,所以我们只需要判断一下minCapacity是否大于该值。

2)当容量不够的时候,我们就需要确定新数组的容量,申请新的数组,并将原数组的内容复制到新数组。

上述代码注意最后一步的赋值操作,将新申请的数组重新赋值给成员变量elementData,这样elementData就是扩容后的数组。

我们可以自己写代码完成上述操作,但是这种方式不够高效,其实我们可以使用JDK定义的Arrays.copyOf()方法高效完成这个操作。

这个方法只要指定原数组变量以及新数组的大小,即可完成上面for循环里面的任务,非常简单易用。

综上,我们得到了最终的代码如下:

在调用add方法之前,先确保数组有足够的容量,如果容量不足,则确定新的数组容量为以前数组大小+1,然后通过Arrays.copyOf()方法完成数组复制,最后添加新的元素。

4 总结

针对上一讲的底层数组无法实现自动扩容的问题,提出一种动态数组扩容方法,该方法首先判断当前数组容量是否够用,如果不够则确定新的数组容量,申请新的数组,完成原数组到新数组的复制操作,最后将添加的元素添加在新数组里面。

请继续思考本文完善后的代码有没有什么问题,有没有什么可以改进的地方呢?欢迎留言。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180410G00Y7100?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券