看了定长, 再来看变长数组, 在之前, 先补一些让类更安全的方法.
- 编程技巧 - 让类更安全
- 变长数组实现包
编程技巧 - 让类更安全
让类更安全的方法就是尽可能少的暴露内部数据. 除此之外, 还应该防着为初始化完成的类, 以及应该对包的上限进行一些限制.
添加两个私有变量如下, 一个表示当前的对象是否初始化完成, 一个表示包的大小限制:
private boolean initialized;
private static final int MAX_CAPACITY = 10000;
对于第一个initialized变量, 在每次操作核心方法之前, 加上一个如下私有方法的调用, 注意方法要加在合理的位置上, 不要重复调用:
private void checkInitialized() {
if (!initialized) {
throw new RuntimeException("Bag is not properly initialized");
}
}
然后在构造器的地方加上判断用户给定的包大小的判断:
@SuppressWarnings("unchecked")
public ArrayBag(int capacity) {
if (capacity > MAX_CAPACITY) {
throw new RuntimeException("Max bag capacity exceeds 10000");
}
bag = (T[]) new Object[capacity];
numberOfEntries = 0;
initialized = true;
}
现在这个类就比原来更加安全, 同时也可以防止包的大小过大.
变长数组实现包
变长数组实现包的核心算法就是, 每次包放满的时候, 就尝试将包的私有变量bag的长度扩大到原来的2倍长度. 其他所有逻辑都不变.
实现起来可以手工编写, 也可以使用Java的Arrays数组工具类.
这里先来定义一个私有方法, 用来扩充数组:
private void doubleCapacity() {
int length = 2 * bag.length;
checkCapacity(length);
bag = Arrays.copyOf(bag, length);
}
这里想到如果扩大一倍之后, 就可能会超过最大长度, 因此再定义一个私有方法用来检查长度:
private void checkCapacity(int capacity) {
if (capacity > MAX_CAPACITY) {
throw new RuntimeException("Cannot Resize Bag because exceeded MAX CAPACITY = 10000");
}
}
有了这个方法之后, 就可以来重新编写add方法了. 编写之前的add方法有可能返回false, 因为定长, 现在我们无需返回false, 只要返回true就可以. 如果数组无法扩充, 则直接就抛异常了, 无需返回false.
@Override
public boolean add(T newEntry) {
checkInitialized();
boolean isAddSuccess = true;
if (isArrayFull()) {
doubleCapacity();
}
bag[numberOfEntries] = newEntry;
numberOfEntries++;
return isAddSuccess;
}
通过这么编写, 就可以实现变长数组.
用数组实现包, 则包的特点就会带有数组的特点:
- 添加一个项(未超过长度), 时间是常数
- 添加一个项, 超过长度, 时间是复制原来数组的时间加上常数, 也就可以认为就是复制原来数组的时间, 即遍历原来数组的时间
- 删除未指定项目, 在实现中就是删除最后一个项目, 时间也是常数.
- 删除一个项目, 时间是在数组中搜索到这个项目的时间, 因此最差时间也是遍历原来数组的时间
今天继续放上女儿的最新作品: 
