手机访问 | 设为首页 | 加入收藏 | 网站地图

当前位置:电脑中国 > 编程 > 移动开发 >

java数据结构与算法之改良顺序表与双链表类似ArrayList和LinkedL

2016-11-23 17:31|来源:未知 |作者:dnzg |点击:

理解Iterator接口

为什么需要迭代器(Iterator)

??在分析迭代器前,我们先来了解一下为什么需要迭代器,在以前的代码中,我们总是通过如下去循环获取某些集合中的元素:

?
1
2
3
4
5
List<string> list = new ArrayList<string>();
for(int i = 0 ; i < list.size() ;  i++){
     String str = list.get(i);
     //do something....
  }</string></string>

或者是

?
1
2
3
4
5
List<string> list = new LinkedList<string>();
for(int i = 0 ; i < list.size() ;  i++){
     String str = list.get(i);
     //do something....
  }</string></string>

??事实上以上的方式是完全没有问题的,但是大家有没想过为什么可以这样去获取值呢?其实很大原因是我们已了解了ArrayList和LinkedList集合的内部结构,因此我们知道可以通过list.get(i)可以获取到元素也可以通过list.remove()可以删除元素,什么意思?现在来假设一个集合(不属于Collection和Map),该集合是SquenceHashColl,请遍历该集合元素,此时大家会如何做呢,有人会说很简单啊,去查该集合的API啊,是的,没错,那去查API不就相当于去了解其结构了么?难道就没有其他方法可以在不查看API或了解内部结构的情况下去遍历SquenceHashColl集合的吗?到此先来屡屡问题出现的原因,然后再给出解决方案,上述在遍历SquenceHashColl集合时,之所以无法在不知道API或内部结构的时候获取元素,主要原因是访问代码和集合本身是紧密耦合的,无法将访问逻辑从集合类和客户端代码中分离出来,也就是说我们没有办法遍历集合的原因是访问集合元素的逻辑与集合本身耦合度太高了,从而必须在了解其API或者内部结构的基础上才能遍历该集合,那么现在只要把访问逻辑从集合本身的代码剥离出来问题也就迎刃而解了,但该如何剥离两者呢?这时迭代器就出场了,有了迭代器访问集合元素的逻辑和集合本身就很容易分离开来了,问题迭代器是什么啊?客官,别急,且听,慢慢道来…..

迭代器(Iterator)的分析

??关于迭代器,在这里我们可以简单地理解为遍历,是一个标准化遍历各类容器里面的所有对象的方法类,它是本身也是一种典型的设计模式。Iterator 模式是用于遍历集合类的标准访问方法。它可以把访问逻辑从不同类型的集合类中抽象出来,从而避免向客户端暴露集合的内部结构。由于迭代器总是用同一种逻辑来遍历集合,因此只要该集合内部实现了迭代器,就可以在不知道API或者集合内部结构的情况下通过迭代器遍历该集合的元素。下面我们先来对比一下使用迭代器和不使用迭代器的遍历方法:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
List<string> list = new LinkedList<string>();
//不使用迭代器
for(int i = 0 ; i < list.size() ;  i++){
     String str = list.get(i);
     //do something......
  }
 //使用迭代器
 //获取该集合的迭代器
 Iterator iterator = list.iterator();
 //判断是否有下一个元素
 while(iterator.hasNext()){
    //获取迭代器的值
    String string = iterator.next();
    //do something......
   }
 
//SquenceHashColl集合(虚构的集合,假设该集合内部实现Iterator)
SquenceHashColl shc=new SquenceHashColl();
//获取该集合的迭代器
 Iterator iterator = shc.iterator();
 //判断是否有下一个元素
 while(iterator.hasNext()){
    //获取迭代器的值
    String string = iterator.next();
    //do something......
   }</string></string>

??由上述代码可见,使用迭代器(Iterator)可以在不知道集合API和内部结构的情况下很容易的获取集合的元素。接下来我们引入Java JDK中为我们提供的Iterator接口,它提供了迭代了基本规则,在Java JDK 中他是这样定义的:对 collection 进行迭代的迭代器。其接口定义如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public interface Iterator<e> {
   /**
    * 判断是否还有下一个元素
    */
   boolean hasNext();
 
   /**
    * 返回元素的值
    */
   E next();
 
   /**
     * 移除元素
    */
   default void remove() {
       throw new UnsupportedOperationException("remove");
   }
 
   /**
    * 这是Java8为Iterator新增的默认方法,该方法可使用lambda表达式来遍历集合元素。
    * 本篇我们先不分析该方法
    * @since 1.8
    */
   default void forEachRemaining(Consumer<!--? super E--> action) {
       Objects.requireNonNull(action);
       while (hasNext())
           action.accept(next());
   }
}</e>

??在大多数情况下,我们一般只需使用 next()、hasNext() 两个方法即可完成元素迭代。

迭代器(Iterator)的简单实现

??ok~,在理解了迭代器后,我们来看看在顺序表中迭代器的实现(为了避免与Java中的ArrayList名字冲突,这里顺序表就命名为MyArrayList,关于MyArrayList的get方法和remove方法的实现与前两篇的实现基本一样,Itr为迭代器,是顺序表MyArrayList的内部类):

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
**
 * 迭代器-Itr
 * Blog : http://blog.csdn.net/javazejian
 */
private class Itr implements Iterator<t> {
    /**
     * 表示将要访问的下一个元素的下标
     * index of next element to return
     */
    int cursor;
 
    /**
     * 当前正在访问的元素下标,如果没有则返回-1
     * index of last element returned; -1 if no such
     */
    int lastRet = -1;
 
    /**
     * 先判断是否还有下一个元素
     * @return
     */
    public boolean hasNext() {
        return cursor != size;
    }
 
    @SuppressWarnings("unchecked")
    public T next() {
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        //获取顺序表中的数组集合,然后操作该数组元素
        Object[] elementData = MyArrayList.this.elementData;
 
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
 
        cursor = i + 1;//加一,移动到下一个要访问的下标
 
        return (T) elementData[lastRet = i];
    }
 
    /**
     * 使用迭代器的方法移除元素
     */
    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        try {
            //移除当前操作的元素
            MyArrayList.this.remove(lastRet);
            //修改当前下标指向
            cursor = lastRet;
            //复原
            lastRet = -1;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}</t>

??从代码可以知道,cursor表示还未被访问的下一个元素下标,lastRet表示的是正在被访问的元素下标,hasNext()方法实现中可知,通过判断还未被访问的下一个元素的下标来判断是否还有可访问元素。

?
1
2
3
public boolean hasNext() {
      return cursor != size;
  }

??而在next()方法实现中,可看出在执行next时,cursor可访问的下标元素会赋值i变量,最终i会赋值给lastRet变量,此时lastRet下标就代表着正在被访问元素的下标,而cursor则执行加1操作,继而指向下一个未被访问的元素(此时并不知道还有没下一个元素,需要通过hasNext()方法判断),还有一点需要特别注意的是,在next方法中使用的元素数组是来自顺序表MyArrayList.this.elementData,实际上迭代器是顺序表MyArrayList的内部类Itr。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@SuppressWarnings("unchecked")
public T next() {
    int i = cursor;
    if (i >= size)
        throw new NoSuchElementException();
    //获取当前集合
    Object[] elementData = MyArrayList.this.elementData;
 
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
 
    cursor = i + 1;//加一,移动到下一个要访问的下标
 
    return (T) elementData[lastRet = i];
}

??在remove方法中,通过在next()方法访问时记录的当前正在访问的元素下标lastRet,然后调用顺序表的MyArrayList.this.remove(lastRet)移除元素,此时由于移除了元素,lastRet所代表下标的元素即为删除元素后移动到该位置的新元素,因此该元素是未被访问的元素即修改cursor的值为lastRet,同时lastRet的值复原为-1。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void remove() {
   if (lastRet < 0)
       throw new IllegalStateException();
   try {
       //移除当前操作的元素
       MyArrayList.this.remove(lastRet);
       //修改当前下标指向
       cursor = lastRet;
       //复原
       lastRet = -1;
   } catch (IndexOutOfBoundsException ex) {
       throw new ConcurrentModificationException();
   }
}

到此迭代器的3个方法分析完成,可以小结出以下几点:
1、迭代器Iterator内部最终操作的也是顺序表MyArrayList的数组和方法
2、hasNext()通过cursor判断将要被访问的元素是否存在
3、next()返回的正在被访问的元素,同时会保存该元素的下标指向lastRet,而cursor会指向下一个未被访问的元素。
4、remove()移除后数组元素需要移动,同时cursor指向需要更新为lastRet,因为lastRet此时代表着往前移动的元素。移除过程可以简单理解为下图:
\
顺序表有了迭代器,我们就可以通过以下方式访问顺序表MyArrayList的元素了,简易代码如下:

?
1
2
3
4
5
6
7
8
9
10
11
MyArrayList<integer> myArrayList=new MyArrayList<>();
myArrayList.add(2);
myArrayList.add(10);
myArrayList.add(1);
myArrayList.add(9);
 
//通过迭代器方法
Iterator iterator=myArrayList.iterator();
while (iterator.hasNext()){
    System.out.println("iterator.next->"+iterator.next());
}</integer>

迭代器(Iterator)与集合间存在的问题

??虽然上述过程中我们已在顺序表MyArrayList集合中实现了迭代器,但是MyArrayList集合与迭代器间却还存在着一个严重的问题,那就是数据一致性,为什么会出现这个问题呢?现在假设我们通过myArrayList的迭代器遍历元素,此时会调用next方法,其内部会进行一个操作:

?
1
2
//获取当前MyArrayList的数组集合
Object[] elementData = MyArrayList.this.elementData;

??迭代器会先获取整个数组对象,然后进行取值操作,但是在使用iterator的同时,假设我们又去操作调用了myArrayList本身的方法比如MyArrayList.remove(index),那么此时elementData数组的元素就会发生变化,而迭代器此时刚好也通过了hasNext方法判断,正在调用next方法,但最后获取到的值却已被之前修改过了,不是期望值,从而也就造成了数据不一致的问题。举个简单的例子如下,假如集合中存放了10号、20号、30号、40号的球衣,我们可以通过两种方式取出球衣,一种是通过MyArrayList集合本身的方法remove()(在迭代过程中调用,迭代器并不知情),另一种则是通过迭代器本身的remove方法,过程如下所示(这里我们简单把remove理解为获取球衣):

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
MyArrayList<integer> myArrayList=new MyArrayList<>();
myArrayList.add(10);
myArrayList.add(20);
myArrayList.add(30);
myArrayList.add(40);
System.out.println("-------------iterator--------------");
//迭代前获取到的集合有4件球衣
boolean flag=true;
Iterator<integer> it = myArrayList.iterator();
while (it.hasNext()) {
    //调用集合myArrayList的remove
    //在迭代器不知情的情况下移除了20,剩余3个球衣
    if(flag){
      flag=false;
      myArrayList.remove(new Integer(20));
    }
    //结果只拿到3件球衣
    it.remove();//迭代器本身的方法
}</integer></integer>
(责任编辑:dnzg)