[Java] LinkedList와 ListIterator에 대한 고찰

💡 문제 배경 : 백준 1406번 - 에디터

바킹독 연결리스트 강의의 연습문제다. 연결리스트 강의였으니 자연스럽게 연결리스트로 풀어야겠다고 생각했다.

야매 연결리스트를 만들 수도 있었지만, 일단 라이브러리 함수를 사용해서 풀어보고 그 후에 직접 구현하기로 했다.

 

초기 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] input = br.readLine().toCharArray();
        List<Character> list = new LinkedList<>();
        list.add(null);
        for (int i = 0; i < input.length; i++) {
            list.add(input[i]);
        }
        int cursor = list.size() - 1;
        int M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String cm = st.nextToken();
            switch (cm) {
                case "L":
                    if (cursor != 0)
                        cursor--;
                    break;
                case "D":
                    if (cursor != list.size() - 1)
                        cursor++;
                    break;
                case "B":
                    if (cursor != 0) {
                        list.remove(cursor);
                        cursor--;
                    }
                    break;
                case "P":
                    char add = st.nextToken().charAt(0);
                    list.add(++cursor, add);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < list.size(); i++) {
            sb.append(list.get(i));
        }
        System.out.print(sb);
    }
}

 

결과는 시간 초과였다.

질문 게시판을 뒤적이다가, `ListIterator`를 사용해서 푸신 분의 블로그를 볼 수 있었다.

 

🔍 그래서 LinkedList와 ListIterator가 뭔데?

✅ LinkedList란?

이중 연결 리스트의 구현체다.

각 노드는 이전과 다음 노드의 참조를 가지고 있고, 위치만 알면 O(1)의 시간에 삽입/삭제를 할수 있다(편의상 노드라고 칭함).

단, 접근 속도는 O(n)으로 비효율적이다(타고타고 가야하기 때문).

 

여기서 문제가 있다.

'위치만 알면' 이라는 표현은 인덱스를 말하는 게 아니다.

위치가 인덱스 값으로 주어지면 그 노드를 찾는 데까지 O(n)의 시간이 걸리고, 삽입/삭제 연산 자체는 O(1)의 시간이 걸린다.

여기서의 '위치'란 노드 참조를 말한다.

 

`ListIterator` 같은 객체가 그 노드 참조 역할을 한다.

✅ ListIterator란?

`ListIterator`를 설명하려면 우선 `Iterator`를 알고 있어야 한다.

`Iterator`는 `Collection`의 요소들을 단방향으로 하나씩 꺼내는 도구이다.

단방향이라 뒤로 돌아갈 수 없고, 요소의 추가나 수정이 불가능하다.

 

실제 커서처럼 앞뒤로 왔다갔다 해야 하고, 추가/수정도 필요하기 때문에 `Iterator`는 적절치 않다.

그래서 이 문제에서는 양방향 반복자인 `ListIterator`를 사용해야 한다.

`List` 전용이라는 걸 명심해야 한다.

 

🧠 코드 수정, 그러나...

`ListIterator`를 사용해 수정한 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] input = br.readLine().toCharArray();
        List<Character> list = new LinkedList<>();
        for (int i = 0; i < input.length; i++) {
            list.add(input[i]);
        }
        ListIterator<Character> cursor = list.listIterator();
        while (cursor.hasNext()) {
            cursor.next();
        }

        int M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String cm = st.nextToken();
            switch (cm) {
                case "L":
                    if (cursor.hasPrevious())
                        cursor.previous();
                    break;
                case "D":
                    if (cursor.hasNext())
                        cursor.next();
                    break;
                case "B":
                    if (cursor.hasPrevious()) {
                        cursor.previous();
                        cursor.remove();    // remove()는 next()나 previous()로 반환된 최근 요소를 제거
                    }
                    break;
                case "P":
                    char add = st.nextToken().charAt(0);
                    cursor.add(add);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < list.size(); i++) {
            sb.append(list.get(i));
        }
        System.out.print(sb);
    }
}

 

또 시간 초과다.

이렇게 되면 입출력 방식을 바꿔야겠다고 생각했다.

 

`StringBuilder`와 `System.out.print`를 사용하지 않고, `BufferedWriter`로 변경했다.

 

드디어 맞았다~!

야호 야호

 

앞으로도 출력은 `BufferedWriter`로 간다!!!

 

 

오스-!