[ JAVA ] Iterator 분석 (feat. ArrayList)

Java

[ JAVA ] Iterator 분석 (feat. ArrayList)

자바니또 2021. 2. 2. 15:01

개요

요즘 코딩테스트 준비를 위해 알고리즘 문제들을 풀고있다. 그러던 중 옆에서 같이 공부하던 생각한대로 동작하지 않는다며 보여준 코드를 보고 이번 포스팅의 주제를 정했다.

public void method(){
  ArrayList<String> list = new ArrayList<>();
  list.add("first ");
  list.add("second ");
  list.add("third");

  while(true){
    //...
    Iterator<String> it = list.iterator();
    list.clear();
    while(it.hasNext()){
      System.out.print(it.next());
    }
  }
}

동생이 직면한 문제는 간단히 적어보았다. 동생이 말히기를 list의 내용을 복사하여 Iterator를 만들고 다음 루프때 새로운 요소들을 list에 담기위해 clear()를 했는데 왜 "first second third"가 출력이 되지 않냐는 것이었다. 동생은 Iterator가 List를 깊은복사(deep copy)한 것으로 알고 있었다. Iterator(반복자)에 대한 개념 부족으로 인한 문제였다. 이번 포스팅에서는 ArrayList의 Iterator를 통해 반복자의 원리를 알아보려 한다.

Iterator

Iterator(반복자)는 주로 이름 그대로 데이터들을 묶는 List나 Map, Set과 같은 Collection에서 사용된다. next()를 통해 데이터들을 중복없이 하나 씩 꺼낼 수 있게 해준다. 참고로 List와 같이 저장된 데이터의 순서가 있는 경우를 제외하고 next()는 데이터의 저장순서와 상관없이 무작위로 꺼낸다.

특이한 점이 있는데 Iterator 인스턴스는 new를 사용하지 않고 Collection 인스턴스의 iterator()를 통해 내부적으로 생성되어 리턴된다. Collection<E>은 Iterable<E>을 상속받고 있고 이것은 iterator()구현을 강제한다. ArrayList의 iterator()를 살펴보자.

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
  //..
  public Iterator<E> iterator() {
    return new Itr();
  }

  private class Itr implements Iterator<E> {
    int cursor;       // 리턴할 다음 index.
    int lastRet = -1; // 가장 마지막에 리턴한 요소의 index. 없을 경우 -1리턴
    int expectedModCount = modCount;  

    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];
    }
}

코드를 보면 알 수 있듯이 Iterator를 구현한 클래스인 Itr을 내부클래스로 가지고 있고 iterator()를 호출 시 Itr()를 생성하여 리턴한다. 내부 클래스이기 때문에 Itr은 저장되어 있는 데이터(elementData)에 접근 할 수 있다.

설명을 돕기위해 간단한 예제 코드와 그림을 같이 보도록 하자.

public void method(){
  List<String> list = new ArrayList<>();
  list.add("a");
  list.add("b");
  list.add("c");

  Iterator<String> it = list.iterator();
  while(it.hasNext()){
    String s = it.next();
    System.out.println(s);
  }
}

list.add()를 통해 내부 배열 elementData에 데이터가 저장된 모습이다. list이기 때문에 Iterator 인스턴스인 it의 cursor는 초기에 인덱스 0을 가리키고 있다. while(it.hasNext())로 cursor가 요소의 끝까지 갈 때까지 반복한다.

반복문에서 첫번째로 next()가 실행되면 cursor로 가리키고 있던 값을 lastRet으로 대신 가리키도록 하고 cursor는 다음 요소를 가리킨다. 그 후 lastRet이 가리키고 있던 값을 리턴한다. 간단히 표현하자면 next()는 cursor가 가리키는 요소를 출력하고 다음 요소를 가리키도록 한다.

console
-------
a

console
-------
a
b

console
-------
a
b
c

cursor가 size와 같은 인덱스 3을 가리키는 순간 hasNext()에서 false를 리턴하게 되고 while문을 종료한다.

ModCount와 ConcurrentException

앞에서 설명하지 않은 부분이 있다. 바로 modCount와 expectedModCount이다. modCount는 ArrayList의 멤버 변수이고 expectedModCount는 ArrayList의 내부클래스인 Itr의 멤버 변수 이다. 우리가 List에 add()나 remove()와 같은 데이터 수정 메서드를 호출 할 때 마다 List의 멤버변수인 modCount가 1씩 증가한다.

ArrayList.iterator()는 list의 modCount를 복사하여 Iterator인스턴스의 멤버변수인 expectedModCount에 저장하고 next()를 할 때마다 list의 modCount와 expectedModCount를 비교하여 중간에 데이터의 변화가 있었는지 체크한다. 만약 같지 않다면 데이터의 변화가 있었다고 생각하고 ConcurrentModificationException을 던진다.

public void method(){
  List<String> list = new ArrayList<>();
  list.add("a");
  list.add("b");
  list.add("c");

  Iterator<String> it = list.iterator();
  while(it.hasNext()){
    String s = it.next();
    System.out.println(s);
    list.remove(s);
  }
}

Iterator를 잘 모른다면 흔히 저지르기 쉬운 실수이다. next()를 통해 요소를 출력하고 출력한 요소를 삭제하려고 했지만 ConcurrentModificationException에 직면하게 된다. 정확히는 'a'를 출력하고 list에서 삭제하는 첫 번째 루프까지는 정상 작동한다. 하지만 두 번째 루프에서 next()가 호출되는 순간 예외가 발생하게 된다.

while문을 돌기전의 Iterator의 그림이다. add()가 3번 동작했기 때문에 modCount는 3이 되었고 그상태에서 iterator()를 호출하였기 때문에 expectedModCount도 3이다.

while문이 동작하고 처음으로 next가 동작하고 난 후의 모습이다. 아직 remove() 실행되지 않았기 때문에 modCount와 expectedModCount의 변화는 없다.

remove(s)가 실행되면 s에 담긴 'a'가 list내부에서 삭제작업이 진행되고 modCount를 1증가 시킨다. List의 elementData는 'a'가 제거된 후 배열이 재정비되어 b, c가 차례로 앞으로 당겨진다. Iterator는 List의 elementData를 가리키는 레퍼런스변수를 가지고 작업을 하기 때문에 결과적으로 그림과 같은 상황이 된다.

ArrayList.Itr클래스의 내부 코드를 좀더 살펴보면 다음과 같다.

private class Itr implements Iterator<E> {

  // 생략

  @SuppressWarnings("unchecked")
  public E next() {
      checkForComodification();
      // ...
  }

  // 중략

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

두 번째 루프가 진행되고 두 번째 next()가 호출되게 되면 checkForComodification()이 실행된다. 이 메서드에서 modCount와 expectedModCount를 비교하고 값이 만약 다르다면 ConcurrentModificationException을 던진다.

회피 방법

1. break로 반복문 강제 탈출

public void method(){
  List<String> list = new ArrayList<>();
  list.add("a");
  list.add("b");
  list.add("c");

  Iterator<String> it = list.iterator();
  while(it.hasNext()){
    String s = it.next();
    System.out.println(s);
    list.remove(s);
    break;
  }
}

  출력결과
  -------
  a

break를 통해 while문을 한 번의 루프만 돌고 탈출하는 방법이다. modCount와 expectedModCount가 서로 달라지지만 next()만 실행되지 않으면 예외는 발생하지 않는 다는 것을 이용한 것이다.

하지만 이 방법은 나머지 b와 c를 출력할 수 없기 때문에 사용성이 없어보인다.

2. Iterator.remove() 사용

public void method(){
  List<String> list = new ArrayList<>();
  list.add("a");
  list.add("b");
  list.add("c");

  Iterator<String> it = list.iterator();
  while(it.hasNext()){
    String s = it.next();
    System.out.println(s);
    it.remove();
  }
}

  출력결과
  -------
  a
  b
  c

list의 remove()가 아닌 Iterator의 remove()를 사용하는 것이다. Iterator의 remove()는 lastRet이 가리키는 요소를 list.remove()의 인자로 넣어서 호출한다. 그 후 lastRet이 가리키고 있던 위치로 cursor가 뒤로 이동하고 expectedModCount에 modCount를 다시 복사한다. 결과적으로 예외도 발생하지 않고 원하는 결과를 얻을 수 있다.

하지만 remove()가 아닌 add()의 경우 적용하지 못하고 멀티 쓰레드의 경우 문제가 발생 할 수 있다.

3. Iterator를 사용하지 않는다.

public void method(){
  List<String> list = new ArrayList<>();
  list.add("a");
  list.add("b");
  list.add("c");

  while(!list.isEmpty()) {
    String s = list.get(0);
    System.out.println(s);
    list.remove(s);
  }
}

출력결과
-------
a
b
c

동작을 보면 queue의 poll()과 비슷하다. Iterator를 사용하지 않기 때문에 ConcurrentModificationException이 발생할 위험도 없다. 하지만 list는 가변 배열과 같기 때문에 인덱스를 통해 데이터를 추출하는 get()과 remove()를 하나의 트랜잭션에서 같이 사용하면서 원하는 값을 추출하기 위해서는 주의하며 사용하여야 한다. 이 또한 멀티쓰레드에서는 안전성을 보장하지는 않는다.

4. CopyOnWriteArrayList 사용하기

public void method(){
  List<String> list = new CopyOnWriteArrayList<>();
  list.add("a");
  list.add("b");
  list.add("c");

  Iterator<String> it = list.iterator();
  while(it.hasNext()){
    String s = it.next();
    System.out.println(s);
    list.remove(s);
  }
}

출력결과
-------
a
b
c

자바에서 제공하는 수정메서드에 대해 Thread-safe를 보장하는 List이다. CopyOnWriteArrayList의 iterator()가 호출되면 현재 list의 데이터 배열을 참조하여 저장하고 이를 Snapshot이라 부른다. add()나 remove()와 같은 동작은 새로운 배열을 복사(shallow copy)하여 작업하기 때문에 life-time동안 snapshot은 변경되지 않으며 이는 ConcurrentModificationException을 발생하지 않는 것을 보장한다. 또한 수정메서드들은 synchronized가 되어 있기 때문에 Thread-safe하다.

여러 스레드가 순회문을 통해 자주 list를 읽는 경우에 아주 유용하다. 하지만 수정작업이 많은 경우 새로운 배열을 자주 생성해야 하기 때문에 성능이 매우 떨어진다.

결론

각각의 회피방법은 멀티스레드인지 싱글스레드인지에 따라 좋은 방법이 될 수도 있고 나쁜 방법이 될 수도 있다.
중요한 것은 내부 동작 원리를 아는 상태에서 상황에 따라 적절한 방법을 적용할 수 있어야 하고, 필요에 따라서 자신이 직접 만들 수 있어야 한다.

저작자표시