ArrayList와 LinkedList의 차이점 그리고 ListIterator

자바에는 ArrayList와 LinkedList가 내장 클래스로 모두 구현이 되어 있습니다.

언제 ArrayList를 사용하고 언제 LinkedList를 사용해야 할 지 헷갈릴 때가 많아 오래도록 기억하고자 포스팅하게 되었습니다.

 

백준 알고리즘 1406번 에디터 문제입니다. 정답률이 26%밖에 되지 않는 아주 어려운 문제였습니다.

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

1406번: 에디터

저는 이 문제를 보고 ArrayList를 사용할지 LinkedList를 사용할지 고민했습니다.

ArrayList는 삽입 삭제가 빈번한 경우에는 사용을 지양해야 합니다.

내부적으로 삽입이 일어날때 ArrayCopy가 일어나기 때문에 최악의 경우 시간 복잡도가 O(n2)이 됩니다. 하지만 인덱스 기반의 자료구조이기 때문에, 자료의 검색은 속도가 LinkedList에 비해 빠릅니다.

 

반면 LinkedList는 자료의 삽입과 삭제가 잦은 경우에 사용하면 좋은 자료구조입니다. 각 노드가 서로 연결되어 있는 형태이기 때문입니다.

삽입을 할 때 이전 노드가 가리키는 다음노드를 자기 자신으로 설정하고 자기 자신이 다음 노드를 가리키게 삽입하면 끝나기 때문에 시간 복잡도가 O(n)입니다.

 

그래서 삽입과 삭제가 잦은 이 문제에서는 LinkedList를 사용하는 것이 좋은 접근입니다.

package BOJ.DataStructure;

import java.io.*;
import java.util.LinkedList;


public class boj1406{
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String c= "cursur";

        LinkedList<String> ll = new LinkedList<>()

        String str = br.readLine();

        //linked list에 입력받은 각 원소들을 입력
        for(int i = 0; i<str.length();i++){
            ll.add(str.substring(i,i+1));
        }
        ll.add(c);

        int tc = Integer.parseInt(br.readLine());
        for(int  i = 0 ;i<tc;i++){
            String input = br.readLine();
            //입력받은 문자가 P로 시작할때의 로직
            if (input.startsWith("P ")){
                String x =input.substring(2);
                ll.add(ll.indexOf(c),x);

            }
            //그 외 L, D, B 가 입력으로 들어왔을 때의 로직
            else {

                switch (input) {
                    case "L":
                        if (!(ll.indexOf(c)==0)){
                            String tmp = ll.get(ll.indexOf(c)-1);
                            ll.remove(ll.get(ll.indexOf(c)-1));
                            ll.add(ll.indexOf(c)+1,tmp);
                            tmp = null;
                        }
                        else break;
                        break;
                    case "D":
                        if (!(ll.indexOf(c) == ll.size()-1)){

                            String tmp = ll.get(ll.indexOf(c)+1);
                            ll.remove(ll.get(ll.indexOf(c)+1));
                            ll.add(ll.indexOf(c), tmp);
                        }
                        else break;
                        break;
                    case "B":
                        if (!(ll.indexOf(c)==0)){
                            //String tmp = ll.get(ll.indexOf(c));
                            ll.remove(ll.get(ll.indexOf(c)-1));
                        }
                        else break;
                        break;
                }
            }
        }
        ll.remove(c);
        for(var l : ll){
            bw.write(l);
        }

        bw.flush();
        bw.close();
    }
}

제가 처음으로 작성한 코드입니다.

시간초과가 난 코드인데 아무리 고민해도 이유를 몰라서 구글에 검색을 해보았습니다.

그 이유는 ListIterator를 사용하지 않았기 때문입니다. 

 

package BOJ.DataStructure;

import java.io.*;
import java.util.LinkedList;
import java.util.ListIterator;


public class boj1406_second {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        LinkedList<String> ll = new LinkedList<>();
        String str = br.readLine();

        //linked list에 입력받은 각 원소들을 입력
        for(int i = 0; i<str.length();i++){
            ll.add(str.substring(i,i+1));
        }
        ListIterator<String >iter = ll.listIterator(); // 커서 역할을 하는 Iterator
        while(iter.hasNext()){
            iter.next();
        }

        int tc = Integer.parseInt(br.readLine());
        for(int  i = 0 ;i<tc;i++){
            String input = br.readLine();
            char command  = input.charAt(0);

            switch (command){
                case 'L':
                    if(iter.hasPrevious()){
                        iter.previous();
                    }
                    break;
                case 'D':
                    if (iter.hasNext()){
                        iter.next();
                    }
                    break;
                case 'B':
                    if (iter.hasPrevious()){
                        //ll.remove(iter.previousIndex());
                        iter.previous();
                        iter.remove();
                    }
                    break;
                case 'P':
                    String x = input.substring(2);
                    //System.out.println("x = " + x);
                    iter.add(x);
                    break;
                default:
                    break;
            }
        }

        for(var l : ll){
            bw.write(l);
        }

        bw.flush();
        bw.close();
    }
}

http://www.tcpschool.com/java/java_collectionFramework_iterator

코딩교육 티씨피스쿨

ListIterator에 설명한 자료에 따르면 

자바의 컬렉션 프레임워크는 컬렉션에 저장된 요소를 읽어오는 방법을 Iterator 인터페이스로 표준화 하고 있다고 합니다.

ListIterator 인터페이스는 컬렉션 요소의 대체, 추가 그리고 인덱스 검색 등을 위한 작업에서 양방향으로 이동하는것을 지원합니다.

 

에디터 문제 자체가 ListIterator를 모르면 풀 수 없는 문제였습니다.

ListIterator를 꼭 기억해서 유사한 문제가 나왔을 때 당황하지 않도록 해야겠습니다.