把玩算法 | 数组 (2)

为了能更加直观的看到数组存放的元素,还需要重写toString方法:

public String toString() { StringBuilder sb = new StringBuilder("["); for (int i = 0; i < size; i++) { if (i > 0) { sb.append(","); } sb.append(elements[i]); } sb.append("]"); return sb.toString(); }

add, get, set这几个方法的实现都比较简单,都是直接操作存放元素的数组来实现,还提供了size()方法来获取数组的大小。如果元素数组满了,add方法会在添加元素之前会数组进行扩展,相关的实现如下:

数组扩容

elements的初始化长度是固定的,当elements满了之后就没有空余的空间来存放后续添加的元素了,这时就需要进行扩容了。这里的实现也比较简单,创建一个新的数组,再将原先数组中的值复制过去,再将新的数组赋值给elements就可以了。

private void resize(int capacity) { Object[] newElements = new Object[capacity]; for (int i = 0; i < size; i++) { newElements[i] = elements[i]; } elements = newElements; }

在add方法中,将元素数组的长度调整为原先的2倍再加1(size * 2 + 1)

移除

移除数组中指定索引i处的元素时,需要将索引i之后的所有元素往前挪一格,并且还需要将数组中最后的一个元素设置为null,避免对失效位置对元素的引用。

例如,数组中存放了5个元素:[张三,李四,王五,赵六,钱七],如果要删除第二个元素,调用remove(1)方法的示例图如下:

把玩算法 | 数组

移除过程(灰色方格表示还未处理到的位置):

把玩算法 | 数组

实现如下:

public Element remove(int index) { for (int i = index + 1; i < size; i++) { elements[i - 1] = elements[i]; } size--; Element oldValue = (Element) elements[size]; elements[size] = null; if (size > 0 && size < elements.length / 4) { resize(elements.length / 2); } return oldValue; }

当数组的大小为其容量的四分之一时,将数组的容量缩减为数组容量的二分之一。

迭代

iterator()方法的实现如下:

public Iterator<Element> iterator() { return new Iterator<Element>() { int cursor; @Override public boolean hasNext() { return cursor < size; } @Override public Element next() { return (Element) elements[cursor++]; } @Override public void remove() { throw new UnsupportedOperationException("remove"); } }; }

内部维护了一个当前迭代器的指针cursor,相关方法的实现说明如下:

hasNext():表示是否还有下一个元素,如果cursor指针未超过数组的大小,那么说明还有下一个元素

next():获取下一个元素,并将cursor指针指向下一个元素

remove():这里不支持移除操作,直接抛出了UnsupportedOperationException异常

迭代示意图如下:

把玩算法 | 数组

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zypysd.html