[MEJ-013] 자바 Collections로 Iterator 더 깊게 살펴보기

[glenn-syj]

based on: #215 by @yngbao97

들어가며

Java에서 반복문을 이용할 때 for문, for-each문, while문은 익숙할 만큼 자주 사용하게 됩니다. 그러나 @yngbao97 님의 글에서도 언급되었듯이 Iterator 자체가 익숙하지는 않습니다. 사실 Iterator 및 Iterable 인터페이스가 Java Collections에서 중요한 역할을 담당하고 있음에도 말입니다. 따라서 이번 글에서는, Java Collection에서 Iterator를 어떻게 지원하는지 ArrayList 클래스를 통해 살펴보겠습니다.

ArrayList가 Iterator를 지원하는 방식

ArrayList는 AbstractList 추상 클래스를 상속받으며, AbstractList에 이미 존재하는 Iterator 인터페이스 구현 클래스 Itr이나 ListItr를 이용하지 않습니다. ArrayList 자체적으로 내부 클래스 Itr 또는 ListItr를 만들어서 이용하는데요.

Iterator 구현체 Itr

private class Itr implements Iterator<E> {
      int cursor;       // index of next element to return
      int lastRet = -1; // index of last element returned; -1 if no such
      int expectedModCount = modCount;

      // prevent creating a synthetic constructor
      Itr() {}

      public boolean hasNext() {
          return cursor != size;
      }

      @SuppressWarnings("unchecked")
      public E next() {
          checkForComodification();
          int i = cursor;
          if (i >= size)
              throw new NoSuchElementException();
          Object[] elementData = ArrayList.this.elementData;
          if (i >= elementData.length)
              throw new ConcurrentModificationException();
          cursor = i + 1;
          return (E) elementData[lastRet = i];
      }

      public void remove() {
          if (lastRet < 0)
              throw new IllegalStateException();
          checkForComodification();

          try {
              ArrayList.this.remove(lastRet);
              cursor = lastRet;
              lastRet = -1;
              expectedModCount = modCount;
          } catch (IndexOutOfBoundsException ex) {
              throw new ConcurrentModificationException();
          }
      }

      @Override
      public void forEachRemaining(Consumer<? super E> action) {
          Objects.requireNonNull(action);
          final int size = ArrayList.this.size;
          int i = cursor;
          if (i < size) {
              final Object[] es = elementData;
              if (i >= es.length)
                  throw new ConcurrentModificationException();
              for (; i < size && modCount == expectedModCount; i++)
                  action.accept(elementAt(es, i));
              // update once at end to reduce heap write traffic
              cursor = i;
              lastRet = i - 1;
              checkForComodification();
          }
      }

      final void checkForComodification() {
          if (modCount != expectedModCount)
              throw new ConcurrentModificationException();
      }
  }

Itr 클래스는 단방향(인덱스가 적은 곳에서 큰 곳으로)으로의 순회를 지원합니다. 즉, 순차적으로 탐색할 때 이용됩니다. 그런데 코드에서도 볼 수 있듯이, 삭제는 가능하지만 수정은 불가능합니다. 양방향 탐색도 불가능합니다.

특히, 삭제를 담당하는 remove() 메서드는 현재 커서가 있는 곳이 아니라 이전 lastRet 위치의 요소를 삭제하고, 커서를 lastRet 인덱스에 둡니다. 이러한 방식으로 안전하게 요소를 삭제할 수 있습니다. 동시성에서 비롯되는 예외처리를 한 것도 인상적입니다. checkForModification()은 modCount를 이용해 외부에서 수정이 일어났는지 확인하는 메서드입니다.

ListIterator 구현체 ListItr

/**
     * An optimized version of AbstractList.ListItr
     */
    private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            super();
            cursor = index;
        }

        public boolean hasPrevious() {
            return cursor != 0;
        }

        public int nextIndex() {
            return cursor;
        }

        public int previousIndex() {
            return cursor - 1;
        }

        @SuppressWarnings("unchecked")
        public E previous() {
            checkForComodification();
            int i = cursor - 1;
            if (i < 0)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i;
            return (E) elementData[lastRet = i];
        }

        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.set(lastRet, e);
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                ArrayList.this.add(i, e);
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }

ListItr은 ListIterator의 구현체입니다. 여기에서는 양방향 탐색과 함께 요소의 수정, 추가, 삭제가 모두 지원됩니다. 게다가 이전 인덱스 역시 조회할 수 있습니다.

AbstractList 내부 Iterator와의 차이

AbstractList 내부의 Itr 클래스는 get() 메서드를 이용해 요소를 반환하는 반면, ArrayList 내부의 Itr 클래스는 배열에 직접 접근해 요소를 반환합니다. 이는 당연하게도, ArrayList 클래스의 특성 상 배열로 참조해 더 빠르게 접근할 수 있는 까닭입니다. 따라서 O(1)의 시간 복잡도로 접근할 수 있습니다.

[yngbao97]

ArrayList가 내부에 별도로 Itr, ListItr을 구현해서 사용하고 있는줄은 몰랐는데, 생각지 못한 부분을 언급해주셔서 덕분에 공부가 되었습니다!
확인해보니 말씀해주신것처럼 AbstractList 내부의 Iterator에서는 next()나 previous()를 사용할때 get() 메서드를 사용해 요소에 접근하는 것을 확인했습니다.

public E next() {
            checkForComodification();
            try {
                int i = cursor;
                E next = get(i);    // get()으로 가져옵니다!
                lastRet = i;
                cursor = i + 1;
                return next;
            } catch (IndexOutOfBoundsException e) {
                checkForComodification();
                throw new NoSuchElementException(e);
            }
        }

사실 get()메서드가 추상메서드이기 때문에 어떻게 구현하느냐에 따라 속도는 차이가 있겠지만, ArrayList는 데이터가 배열 형태로 저장되어있어 배열에 직접 접근하는 형태이기 때문에 당연히 속도가 빠르다는 점이 이해가 되었습니다.
Iterator라는 개념은 아직 낯설지만 용도에 따라 유용하게 사용해볼 수 있을 것 같네요! 감사합니다!