自己动手实现java数据结构(一) 向量(3)
因此,向量提供了trimToSize方法,允许用户在必要的时候手动的使向量收缩,以增加空间效率。 * 收缩内部数组,使得"内部数组的大小"和"向量逻辑大小"相匹配,提高空间利用率 * trimToSize(){ :::如果当前向量逻辑长度 小于 内部数组的大小 this.size < :::创建一个和当前向量逻辑大小相等的新数组 Object[] newElements = .size]; :::将当前旧内部数组的数据复制到新数组中 :::Tips: 这里使用Arrays.copy方法进行复制,效率更高 int i = 0; i< newElements.length; i++){ newElements[i] = .elements[i]; } :::用新数组替换掉之前的老内部数组 this.elements = newElements; :::设置当前容量 this.capacity = .size; } } 3.4.3 toString方法String toString(){ :::空列表 .isEmpty()){ return "[]":::列表起始使用"[" StringBuilder s = new StringBuilder("["); :::从第一个到倒数第二个元素之间 int i=0; i<size-1; i++:::使用","进行分割 s.append(elements[i]).append(",").append(" "); } :::最后一个元素使用"]"结尾 s.append(elements[size - 1]).append("]"); s.toString(); } 4.向量的Iterator(迭代器)在我们使用数据结构容器时,会遇见以下问题: 1. 需要理解内部设计才能遍历容器中数据。如果说基于数组的向量还可以较轻松的通过循环下标来进行遍历,那么更加复杂的数据结构例如哈希表、平衡二叉树等在遍历时将变得更加困难。同时在业务代码中如果存储数据的容器类型一旦被改变(向量--->链表)? ,意味着大量代码的推倒重写。 2.?缺少对容器遍历行为的抽象,导致重复代码的出现。这一问题必须在实现了多个数据结构容器之后才会体现出来。例如,上面提到的向量的toString方法中,如果将遍历内部数组的行为抽象出来,则可以使得多种不同的类型的数据结构容器复用同一个toString方法。 为此java在设计数据结构容器架构时,抽象出了Iterator接口,用于整合容器遍历的行为,并要求所有的容器都必须提供对应的Iterator接口。 Iterator接口设计:1. hasNext() 接口定义:boolean?hasNext(); 接口描述:当前迭代器 是否存在下一个元素。 2. next() 接口定义:E next(); 接口描述:获得迭代器 迭代的下一个元素。 3. remove() 接口定义:void remove(); 接口描述:??移除迭代器指针当前指向的元素 个人认为迭代器之所以加上了remove接口,是因为很多时候迭代的操作都伴随着删除容器内部元素的需求。由于删除元素会导致内部数据结构的变化,导致无法简单的完成遍历,需要使用者熟悉容器内部实现原理,小心谨慎的实现遍历代码。 而Iterator接口的出现,将这一问题带来的复杂度交给了容器的设计者,降低了用户使用数据结构容器的难度。 向量Iterator实现:/** * 向量 迭代器内部类 * class Itr implements Iterator<E>{ * 迭代器下一个元素 指针下标 */ int nextIndex = 0 * 迭代器当前元素 指针下标 * int currentIndex = -1; @Override hasNext() { 如果"下一个元素指针下标" 小于 "当前线性表长度" ==> 说明迭代还未结束 this.nextIndex < ArrayList..size; } @Override @SuppressWarnings("unchecked") E next() { 当前元素指针下标 = 下一个元素指针下标 this.currentIndex = nextIndex; 下一个元素指针下标自增,指向下一元素 this.nextIndex++; 返回当前元素 return (E)ArrayList..currentIndex]; } @Override remove() { this.currentIndex == -1new IteratorStateErrorException("迭代器状态异常: 可能在一次迭代中进行了多次remove操作"); } 删除当前元素 ArrayList.this.remove(.currentIndex); 由于移除了数据,会导致下一元素被略过,因此nextIndex=currentIndex,将当前迭代器下标恢复 this.nextIndex = .currentIndex; 为了防止用户在一次迭代(next调用)中多次使用remove方法,将currentIndex设置为-1 this.currentIndex = -1; } } 5.向量总结5.1 向量的性能空间效率:向量中空间占比最大的就是一个随着存储数据规模增大而不断增大的内部数组。而数组是十分紧凑的,因此向量的空间效率非常高。 时间效率:评估一个数据结构容器的时间效率,可以从最常用的增删改查接口来进行衡量。 我们已经知道,向量的增加、删除操作的时间复杂度为O(n),效率较低;而向量的随机修改、查询操作效率则非常高,为常数的时间复杂度O(1)。对于有序向量,其查找特定元素的时间复杂度也能够被控制在O(logn)对数时间复杂度上。 因此向量在随机查询较多,而删除和增加较少的场景表现优异,但是并不适合频繁插入和删除的场景。 5.2 当前向量实现存在的缺陷到这里,我们已经完成了一个最基础的向量数据结构。限于个人水平,以及为了代码尽可能的简单和易于理解,所以并没有做进一步的改进。 下面是我认为当前实现版本的主要缺陷: 1.不支持并发java是一门支持多线程的语言,因此容器也必然会在多线程并发的环境下运行。 (编辑:ASP站长网) |