02: 연결리스트

01: 연결리스트

---

1. 연결리스트란?

연결 리스트(LinkedList)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조입니다.

데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당합니다.

 

Node는 LinkedList에 객체를 추가하거나 삭제하면 앞뒤 링크만 변경되고 나머지 링크는 변경되지 않습니다.

중간에 데이터를 추가나 삭제하더라도 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지는 일이 없기에 ArrayList에 비해서 데이터의 추가나 삭제가 용이하나, 인덱스가 없기에 특정 요소에 접근하기 위해서는 순차 탐색이 필요로 하여 탐색 속도가 떨어진다는 단점이 있습니다.

 

그러므로 탐색 또는 정렬을 자주 하는 경우엔 배열을 사용하고 데이터의 추가/삭제가 많은 경우 연결 리스트를 사용하는 것이 좋습니다.

 

2. 예제 문제(1)

 

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

1406번: 에디터

 

문제를 직관적으로 푼 처음 풀이는 다음과 같다. (시간초과 코드)

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

public class Main {

    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 str = br.readLine();
        int comLine = Integer.parseInt(br.readLine()); // 명령어의 횟수
        LinkedList<Character> links = new LinkedList<>();


        for (int i = 0; i < str.length(); i++) {
            links.addLast(str.charAt(i)); // 초기 커서 위치가 맨 오른쪽이므로 초기 문자열 전부 삽입
        }

        int cursor = links.size(); // 그리고 커서의 위치를 문자열 가장 오른쪽에 위치하게 함

        for (int i = 0; i < comLine; i++) {
            String command = br.readLine();
            char com = command.charAt(0); // 명령어 구분
            if (com == 'L' && cursor > 0) {
                cursor--;
            }
            else if (com == 'D' && cursor < links.size()) {
                cursor++;
            }
            else if (com == 'B' && cursor > 0) {
                links.remove(--cursor); // 삭제의 경우 커서가 왼쪽으로 이동되면서 리스트 길이가 감소하므로 먼저 cursor값을 하나 줄이고 처리함.
            }
            else if (com == 'P') {
                links.add(cursor, command.charAt(2)); // 삽입의 경우 커서가 오른쪽으로 이동되면서 리스트 길이가 증가하므로 추가 후에 cursor값을 하나 늘림.
                cursor++;
            }
        }
        for (Character s : links) {
            bw.write(s);
        }
        bw.flush();
        bw.close();
    }
}

값 삭제의 경우

cursor위치를 왼쪽으로 한 번 땡기고

해당 위치의 문자 삭제

값 추가의 경우

해당 위치에 값 삽입

cursor의 위치를 오른쪽으로 한 칸 옮김

 

그러나 cursor에 위치에 데이터를 넣거나 빼는 과정에서 O(N)이 걸리기 때문에 시간 초과가 발생하는듯 했다.

 

아래 코드에서 ListIterator 사용하여 코드를 개선했다. (성공한 코드)

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

public class Main {

    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 str = br.readLine();
        int comLine = Integer.parseInt(br.readLine());
        LinkedList<Character> links = new LinkedList<>();


        for (int i = 0; i < str.length(); i++) {
            links.addLast(str.charAt(i));
        }

        ListIterator<Character> iter = links.listIterator();
        while (iter.hasNext()) {
            iter.next();
        }

        for (int i = 0; i < comLine; i++) {
            String command = br.readLine();
            char com = command.charAt(0);
            if (com == 'L' && iter.hasPrevious()) { // 왼쪽에 값이 있는 경우에만 실행
                iter.previous();
            }
            else if (com == 'D' && iter.hasNext()) { // 오른쪽에 값이 있는 경우에만 실행
                iter.next();
            }
            else if (com == 'B' && iter.hasPrevious()) {
                iter.previous(); // 왼쪽으로 커서 땡겨놓고 지우기
                iter.remove();
                // iterator를 사용하는 경우 값을 삭제하면 자기가 알아서 위치를 조정함
            }
            else if (com == 'P') {
                char cVal = command.charAt(2); 
                iter.add(cVal); // 해당 커서 위치에 값 추가
                // iterator를 사용하는 경우 값을 삽입하면 자기가 알아서 위치를 조정함
            }
        }
        for (Character c : links) {
            bw.write(c);
        }
        bw.flush();
        bw.close();
    }
}

기존 코드에서 LinkedList의 문자 추가 부분은 입력 문자열 길이 N에 대해 O(N)의 시간이 소요된다.

루프에서 명령을 처리하는 부분은 명령 개수 M에 대해 O(M)의 시간이 소요된다.

전체적으로 시간 복잡도는 O(N+M)이 된다.

 

기존 코드에서는 cursor의 값을 변경시키고 cursor의 위치에서 생성과 삭제 메서드를 활용했으나,

개선된 코드에서는 iterator 객체 자체로 cursor의 역할을 하도록 했다.

 

첫번째 코드보다 두번째 코드가 더 빠른 이유

1. 문자 삽입의 효율성

links.add(cursor, comArr[1]);

위의 경우 cursor의 위치에 문자를 추가할 때 후속 요소들을 이동해야하므로 O(N)이 소요된다.

 

iter.add(cVal);

반면에 이렇게 값을 추가하는 경우에는 다른 요소를 이동시킬 필요 없이 현재 iterator에 위치에 문자를 효율적으로 추가하므로 시간 복잡도가 O(1)이 소요된다.

 

else if (com == 'B' && cursor > 0) {
    links.remove(--cursor);
}
else if (com == 'P') {
    links.add(cursor, command.charAt(2));
    cursor++;
}

else if (com == 'B' && iter.hasPrevious()) {
    iter.previous(); // 왼쪽으로 커서 땡겨놓고 지우기
    iter.remove();
    // iterator를 사용하는 경우 값을 삭제하면 자기가 알아서 위치를 조정함
}
else if (com == 'P') {
    char cVal = command.charAt(2); 
    iter.add(cVal); // 해당 커서 위치에 값 추가
    // iterator를 사용하는 경우 값을 삽입하면 자기가 알아서 위치를 조정함
}

2. ListIterator 자체의 최적화 기능

cursor를 인덱스로 사용하여 링크리스트를 돌아다니는 방식에 비해 ListIterator방식을 활용하는 경우 특별히 설계된 효율적인 순회 와 수정 작업 방법을 제공한다. 따라서 ListIterator방식을 활용하는 것이 코드 개선에 도움이 된다.