[Java] 자바 List 탐색/순회 (for문, 향상된for문, ListIterator)

 

자바는 List 인터페이스를 구현한 ArrayList, LinkedList, Vector, Stack 클래스 등을 제공한다.

따라서 List의 탐색, 순회 방법을 이용하여 이러한 클래스들의 탐색, 순회가 가능하다.

 

자바의 버전이 올라가며 for문에서 향상된 for문, Iterator, ListIterator 등이 추가되었다.

새로운 기능이 추가되었다는 것은 기존의 방법에 문제가 있었다는 것이기에

특정 상황별로 자바가 제시하는 탐색, 순회 방법이 존재한다.

 

이번 글에서는 각각의 탐색, 순회 방법을 알아보고 자바가 장려하는 상황별 적절한 탐색, 순회 방법을 알아본다.    

 

예시의 List는 다음과 같이 변수를 선언하고 초기화하였다.

        List<Integer> list = new LinkedList<>();
        for(int i = 0; i < 10; i++)
            list.add(i);

 

 

for문

        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }

장점: 가장 간단하다.

단점: 비효율적이다.

사용 상황: 사용하지 말자!!

 

위의 간단한 구문만 해도 시간복잡도가 O(N^2)에 해당한다.  

n-1번째 요소에 접근한 후 n번째 요소에 접근할 때 n-1번째 요소에서 시작하는 것이 아니라

다시 1번째 요소에서부터 순차적으로 n번 접근하여 n번째 요소에 접근한다. 

 

이는 단순히 for문뿐만 아니라 while문 등의 기본 반복문 모두이에 해당된다.

 

 

향상된 for문

        for (Integer e : list) {
            System.out.print(e);
        }

장점: 간단하며 속도도 빠르다.

단점: List 요소를 수정할 수 없다(단,mutable한 타입인 경우 수정 가능). 요소의 수정을 원한다면 아래의 ListIterator를 사용해야 한다.

사용 상황: List 요소를 수정하지 않고 읽어들이기만 하는 경우

 

Java 8부터 추가된 기능으로 향상된 for문 또는 forEach문 등으로 불린다.

list에 있는 요소들을 하나씩 e에 저장하며 주어진 for문 연산을 수행한다.

 

내부적으로 Iterator를 사용하여 n-1번째 요소에 접근한 후 n번째 요소에 접근 시도 시 1번째 요소가 아닌 n-1번째 요소에서부터 접근하여 속도가 빠르다.

 

하지만 향상된 for문은 list의 요소를 하나씩 꺼내 다른 변수에 임시 저장하여 사용하기에 list의 요소를 수정할 수 없다. 따라서 단순히 요소를 수정하지 않고 읽는 연산만 필요한 경우 사용해야 한다.(immutable한 타입인 경우에만 해당되는 설명)

배열 및 컬랙션의 요소가 참조타입 중 mutable한 경우 경우 수정 가능
배열 및 컬랙션의 요소가 기본타입 or 참조타입 중 immutable한 경우 수정 불가

immutable한 참조타입에는 Wrapper클래스(Integer, Double, Long ...), String 이 있고
이외는 모두 mutable한 타입이다.

 

ListIterator

        ListIterator<Integer> iterator = list.listIterator();
        //정방향 출력
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }
        //역방향 출력
        while(iterator.hasPrevious()){
        	System.out.println(iterator.previous());
        }

장점: List의 요소 읽기, 쓰기뿐만 아니라 다양한 기능을 제공하며 속도가 빠르다. 

단점: ListIterator 인터페이스를 구현한 변수를 선언해야 한다. 

사용 상황: List 요소의 수정이 필요한 경우 

 

Iterator 인터페이스를 List에 맞게 기능들이 추가된 것이 ListIterator인터페이스이다.

추가된 기능으로는 요소 추가(add), 요소 대체(set), 역방향 접근(hasPrevious, previous),

앞/뒤 요소 인덱스 확인(previousIndex, nextIndex) 등이 있다.

 

위에서 언급했 듯 n-1번째 요소 접근 후 n번째 요소에 접근 시도 시 1번째 요소부터 접근이 아닌 n-1번째 요소부터 접근하여 속도가 빠르다. 

 

ListIterator 제공하는 메서드 관련 자세한 설명은 진리의 Java 공식 document에서 확인할 수 있다.

 

 

 

List에서 for문을 사용하면 안 되는 이유

 

배열이 그림과 같이 0번째 주소값에서 index크기만큼 더하기 연산으로 접근하기에 접근 연산이 O(1)인 반면

연결리스트는 그림과 같이 노드의 순서에 따라 하나씩 이동을 하여 접근한다.

 

배열은 크기가 고정되어 값들을 연속적인 주소값으로 저장이 가능하지만 

연결 리스트는 크기가 고정되어 있지 않기에 선행 노드와 후행 노드의 주소값이 불연속적이다.

 

따라서 연결리스트는 배열처럼 단순히 index크기만큼 값을 더하여 접근하는 연산이 불가능하다.

 

int sum = 0;

for(int i = 0; i < 10000000 ; i++){
	sum += linkedList.get(i)
}

따라서 위와 같이 반복문을 이용하여 노드에 접근하려는 연산은 시간복잡도 O(n^2)으로 최악의 연산속도를 갖는다.

linkedList.get(0)은 1번

linkedList.get(1)은 2번

linkedList.get(2)은 3번

....

linkedList.get(n)은 n+1번의 접근 연산을 갖기에 전체 연산은 O(n^2)의 시간 복잡도를 갖게 된다.

 

 

 

알고리즘 문제에서 for문 vs ListIterator 차이 확인

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

1406번: 에디터

문제에서 명시적으로 List를 사용하라고 하지는 않았지만 수정 연산이 최대 500,000번, 요소는 최대 600,000개가 주어지기에 배열, StringBuilder, for문을 사용한 List 등을 사용할 경우 시간 초과가 발생한다. 

 

사실 코드를 모두 이해할 필요는 없다.

단순히 List에서의 탐색, 순회 연산이 많아지는 경우 for문과 ListIterator의 성능 차이가 크게 차이 난다는 예시 정도로 보고 넘어가면 된다. 

 

 

for문을 이용한 코드 

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

public class Main {
    static int addStringToList(LinkedList<Character> list, String str, int cursor){
        for(int i = 0; i < str.length(); i++)
            list.add(cursor++, str.charAt(i));

        return cursor;
    }

    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<Character> list = new LinkedList<>();
        
        String str = br.readLine();
        int cursor = addStringToList(list, str, 0);
        int commandCnt = Integer.parseInt(br.readLine());
        String command;

        for (int i = 0; i < commandCnt; i++) {
            command = br.readLine();

            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) list.remove(--cursor);
            } else if(command.startsWith("P")){
                String[] arr = command.split(" ");
                cursor = addStringToList(list, arr[1], cursor);
            }
        }

        bw.write(list.toString()
                .replaceAll(" ","")
                .replaceAll(",","")
                .replaceAll("\\[","")
                .replaceAll("\\]",""));
        bw.flush();
        bw.close();
    }
}

결과

 

 

ListIterator를 사용한 코드

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

public class Main {
    static void addCharWithIterator(ListIterator<Character> iterator, String input) {
        for (int i = 0; i < input.length(); i++)
            iterator.add(input.charAt(i));
    }

    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<Character> list = new LinkedList<>();
        ListIterator<Character> iterator= list.listIterator();
        //첫 번재 문자열 저장
        String input = br.readLine();
        addCharWithIterator(iterator, input);
        //명령어 개수 저장
        int commandCnt = Integer.parseInt(br.readLine());
        String command;
        for (int i = 0; i < commandCnt; i++) {
            command = br.readLine();
        //명렁어 대로 실행
            if (command.equals("L")) {
                if (iterator.previousIndex() != -1) iterator.previous();
            } else if (command.equals("D")) {
                if (iterator.nextIndex() != list.size()) iterator.next();
            } else if (command.equals("B")) {
                if (iterator.previousIndex() != -1){
                    iterator.previous();
                    iterator.remove();
                }
            } else if(command.startsWith("P")){
                String[] arr = command.split(" ");
                addCharWithIterator(iterator, arr[1]);
            }
        }

        bw.write(list.toString()
                .replaceAll(" ","")
                .replaceAll(",","")
                .replaceAll("\\[","")
                .replaceAll("\\]",""));
        bw.flush();
        bw.close();
    }
}

결과