[Java] ArrayList와 LinkedList 차이

오늘 백준으로 코딩테스트 문제를 풀다가 List를 이용해서 문제를 풀 일이 생겼었다.

백준 2164 [카드2]

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

문제가 궁금하다면 위 링크에서 보면된다.

Queue를 사용해서 푸는 방식도 있었지만 본인은 List를 사용하여 풀었는데

아래가 본인의 코드이다.

import java.util.LinkedList;
import java.util.Scanner;	// Scanner 클래스 호출

class card2 {
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);	// Scanner 객체 생성

        int N = in.nextInt(); 			// int 형 입력 및 리턴
        int a = 0;

        LinkedList List = new LinkedList();

        for(int i=1;i<=N;i++) {
            List.add(i);
        }

        while (List.size() != 1) {
            a = (int) List.get(1);
            List.remove(0);
            List.add(a);
            List.remove(0);
        }

        System.out.print(List.get(0));
    }

}

본인은 위 문제를 풀 때 LinkedList를 사용하였는데 저 코드에서 LinkedList를 ArrayList로 바꿔서 풀게되면 시간초과가 뜨게 된다.

어째서 똑같은 List를 사용하는데 ArrayList는 시간초과가 뜨고 LinkedList는 시간초과가 뜨지 않는 것일까?

이를 알아보려면 ArrayList와 LinkedList의 차이부터 알아봐야 한다.

ArrayList와 LinkedList

---

Java를 사용할 때 기본형(int, boolean, String, char)또는 인스턴스를 리스트로 저장할 때 보통 배열을 사용한다.

하지만 배열은 선언시에 크기를 정해줘야하기에 동적으로 요소의 추가나 삭제 등이 불가능한 단점이 있다.

만약 배열의 원소를 추가하거나 삭제하려면 직접 새로운 배열을 선언해주어서 카피하는 식으로 사용해야 한다.

그렇게 된다면 지속적으로 데이터를 변경해야되는 알고리즘 문제나 어떤 프로그램의 구현에서 배열은 꽤나 큰 불편함으로 다가오게된다.

이러한 불편함을 해소시켜주는 것이 List 인터페이스를 상속하여 구현된 ArrayList와 LinkedList 클래스이다.

이 둘은 모두 Collections 객체의 일종이다.

이 두가지 리스트는 동적으로 사용할 수 있기에 새로운 값의 추가나 제거가 유용하며 기본 배열의 단점을 커버해준다.

하지만 기본형을 내부 원소로 갖는 것이 아니라 Integer, Character등의 클래스형 원소를 가져야 하므로 메모리적인 부분에서 배열보다 더 공간을 차지할 것이라 생각된다.

일반배열과 List배열

//일반 배열
int[] Iarr = new int[10];
char[] Carr = new char[10];
String[] Sarr = new String[10];
boolean[] Barr = new boolean[10];

//List 배열
ArrayList<Integer> IarrL = new ArrayList<>();
ArrayList<Character> CarrL = new ArrayList<>();
LinkedList<String> SarrL = new LinkedList<>();
LinkedList<Boolean> BarrL = new LinkedList<>();

이 둘은 분명히 비슷하지만 다른 점을 가지고 있기에 상황에 따라 다르게 써야한다.

ArrayList

---

ArrayList는 메모리에서 내부적으로 데이터를 배열로 만들어 관리하며 데이터의 추가 및 삭제를 위해 데이터를 복사하는 방법을 사용하고 있다.

각 데이터를 추가 및 삭제 시 마다 배열을 새로 만들어 복사해주므로 기존 10의 데이터에 1개를 추가하면 총 10번의 복사가 요구되는 것이다. 따라서 O(n)의 시간복잡도가 추가 및 삭제 시에 요구된다.

반면 참조의 경우에는 데이터들이 배열의 형태로 저장해 있기 때문에 사용자가 원하는 인덱스의 데이터를 O(1)의 시간에 바로 꺼내올 수 있다.

따라서 ArrayList의 경우에는 추가 및 삭제 시에는 불리하고 참조에는 유리하다는 것을 볼 수 있다.

LinkedList

---

LinkedList는 데이터를 하나의 노드로 구성하며 각 노드는 자신의 이전 노드와 다음 노드만 알고 있다.

시작노드 또한 다음 노드만 가리키고 있을 뿐이다.

ArrayList가 전지적인 시점에서 보는 데이터 셋이라면 LinkedList는 1인칭 시점에서 보는 데이터 셋이라고 생각해볼 수 있다.

List에 들어있는 각각의 노드는 개별적으로 메모리에 저장되고 다음 노드의 위치를 가르키고 있으므로 데이터의 추가 및 삭제 시 나머지 데이터들의 복사가 필요하지 않다.

단지 새로운 데이터 노드를 만들고 그걸 끼워넣어주기만 하면 된다.

따라서 데이터의 추가 및 삭제에서 O(1)의 시간복잡도를 가질 수 있다.

반면에 데이터의 참조 부분에서는 해당 인덱스에 바로 접근했던 ArrayList와 다르게 원하는 인덱스까지 노드 하나하나를 통과해가며 다음 노드를 체크해야한다.

따라서 최대 O(n)의 시간복잡도가 발생할 수 있다.

그러므로 LinkedList의 경우에는 ArrayList와 반대로 추가 및 삭제 시에는 유리하고 참조에는 불리하다.

마무리

본인이 푼 코드에서 메인 연산은 삭제이다.

이때 ArrayList를 쓴다고 하면 ArrayList는 내부에 배열로 구현되어있기에 맨 앞에 있는 요소를 삭제하게 되면 Shift연산을 할 때 시간이 너무 오래 걸리게 된다.

따라서 삭제에 시간이 안드는 LinkedList로 구현해야한다.

이처럼 입력값에 따라 ArrayList를 쓸지 LinkedList를 쓸지 잘 판단하는 것이 중요하다는 것을 알 수 있었다.