Java collection API 中实现的表ADT:
collection<E>接口实现继承iterable<E>接口,实现iterable接口的类可以使用增强for循环,用于观察该类的所有项(带泛型的数组类型也是一样的原理),即可以在iterable类型的对象上使用增强for循环,编译器在遇到增强for循环时会使用一个迭代器来改写该for循环.
Iterator接口:
实现Iterator接口的集合必须实现iterator()方法,用于返回一个Iterator的实现类对象,同时将当前位置的概念记录在对象内部.该对象的三个方法:hasNext()/next()/remove(),特别的remove()方法用于移除next()方法返回的最新的项,并且在次之后不能使用remove方法,直到再次使用next方法之后.
并且建议使用迭代器的remove方法而不是collection的remove方法:
- collection的remove方法需要提前获取被删除项的位置(如果已经知道,确实collection的remove方法消耗时间更少)
- 在直接使用Iterator进行迭代时,需要避免在正在迭代的集合上修改集合的结构(插入/删除/clear()方法等),否则将会引发并发修改异常,特别的可以使用Iterator自己的remove()方法.
list(表)的两种实现:
ArrayList提供可变数组的实现,因为底层为数组(存在索引),因此getIndex与set(index,E)时间为常数,但是插入与删除(特别是前端的插入与删除操作)具有巨大的开销,具体的在前端插入元素的时间复杂度为O(N);
linkedList提供双链表实现,在插入与删除开销很小(位置是已知的),特别是在链表首尾进行操作,但是链表不容易做索引,因此get调用开销巨大(在链表的两端进行遍历),具体的单一的getIndex()调用的时间复杂度为O(N),但是如果使用增强for遍历全部,则获取全部元素的时间复杂度依然为O(N),因为迭代器将会有效的从前驱元推进至后继元;
针对g检索来说,这两种数据结构的时间复杂度均为O(N),例如contains()/remove(E).
ListIterator接口:
继承自Iterator接口,并添加了hasPrevious()/previous()/add()/set(),hasPrevious()返回当前位置是否有前驱元而previous()返回前驱元,与next()相对应,特别的add(E)将元E添加至当前位置,即添加至next()返回元素与previous()返回元素之间;set设置被迭代器所看到的最后一个元素.