ListIterator 인터페이스 활용하기 :: 마이구미

이번 글은 자바에서 활용할 수 있는 ListIterator 인터페이스를 다룰 것이다.

처음보거나 사용해본 적이 없다면 굉장히 유용하게 사용할 수 있다.

백준 알고리즘 사이트 1406번 문제 '에디터'를 접근하면서 알아보겠다.

위 문제를 간략히 살펴보면, 인덱스를 임의대로 이동하면서 삽입 및 수정 등을 처리하는 문제이다.

단순히 생각해보자. ArrayList를 쓸까?  LinkedList를 쓸까?

삽입과 수정을 자유자재로 한다? 이렇게 해석이 가능했다면, 아마 LinkedList를 떠올렸을 거라 생각한다.

잠깐 ArrayList와 LinkedList에 대해 짚고 넘어가자.

ArrayList의 경우는 데이터 삽입/삭제 시 임시 배열을 생성하여 데이터를 복사하는 방식으로 구현된다.

그렇기에 데이터가 많을수록 성능이 저하된다.

하지만 내부적으로 Array 기반이기 때문에 각 데이터에 인덱스를 가지기 때문에 검색에는 인덱스를 통해 접근하기 때문에 유리하다.

LinkedList의 경우는 각 요소는 이전과 다음 요소의 정보를 가지고 있다는 점이 ArrayList와의 가장 큰 차이점이다.

ArrayList와 같이 임시 배열을 생성할 필요 없이 이전과 다음 요소의 정보를 활용하여 삽입 및 삭제를 처리할 수 있기에 삽입/삭제가 유리하다.

하지만 검색시에는 인덱스를 통해 접근하는 것이 아니기에 최악의 경우는 모든 요소를 다 살펴봐야하기 때문에 불리하다,

문제의 경우는 데이터 삽입/삭제가 주요 기능이다.

그렇기에 LinkedList를 통해 커서의 위치를 하나의 변수를 만들어 관리한다면 쉽게 풀 수 있다.

예를 한번 보자.

if (command.equals("L")) {
    if(cursor != 0) {
        cursor--;
    }
} else if (command.equals("D")) {
    if(cursor != list.size()) {
        cursor++;
    }
} else if (command.equals("B")) {
    if (cursor == 0) {
        continue;
    }
    list.remove(--cursor);
} else {
    list.add(cursor,sc.next().charAt(0));
    cursor++;
}

위와 같은 방법으로 위치 인덱스를 하나의 변수를 통해 관리하면 된다.

사실 상 LinkedList만을 활용해도 충분히 문제를 해결하는데는 어려움이 없다.

하지만 여기서 단점이 존재한다. 무엇일까?

그것은 위에서 언급한 LinkedList의 특징에 있다.

삽입/삭제 시 이전 요소와 다음 요소의 정보를 가지고 있는 것이 유리한점으로 언급했었다.

하지만 결국 ArrayList와 상대적으로 유리한 것이다.

결국 삽입/삭제 시 그 인덱스에 바로 접근하는 것이 아니다.

head와 tail을 제외하고는 하나하나 살펴보면서 찾아가 처리하기 때문에 완전히 효율적이라고는 볼 수 없다.

그렇다면 여기서 무엇이 있었으면 좋겠는가?

위치를 찾아가지 말고 문제의 커서처럼 해당하는 위치에 있으면서 삽입/삭제를 처리할 수 있기만 하면 된다.

이때 활용할 수 있는 것이 ListIterator가 되겠다.

ListIterator는 Iterator를 상속한 인터페이스다.

Iterator의 단방향 탐색과 달리 양방향 탐색이 가능하다.

그렇기에 이 문제처럼 양방향으로 이동하면서 수정하기에 효율적이다.

메소드명만 보아도 이해하기 쉽다.

LinkedList<Character> list = new LinkedList<>();
ListIterator iterator = list.listIterator(list.size());

크게 어려울 게 없으니 바로 문제를 풀어보면서 이해하는 것이 좋을 것이다.

그 후 ListIterator를 이용하여 아래 문제 또한 풀어보아라.

전체 소스는 Github URL을 통해 확인하길바란다.

백준 알고리즘 문제 1406번 에디터 전체 소스

https://github.com/hotehrud/acmicpc/blob/master/list/1406.java

백준 알고리즘 문제 5397번 키로거

https://www.acmicpc.net/problem/5397