[Java] ArrayDeque 가 LinkedList 보다 빠른 이유

ArrayDeque VS  LinkedList

백준에서 독특한 계산기 문제를 풀던 중 이상한 점을 발견했다. 제시된 조건을 만족하기 위해 선형 자료구조를 사용하여 맨 앞과 맨 뒤에서 자료를 넣고, 빼는 연산을 사용해야 했다. ArrayList는 데이터를 삭제한다면 모든 데이터들을 앞으로 당기는 작업이 필요하기 때문에 Deque을 사용하기로 했고  구현체 중 하나인 LinkedList를 사용하였다. 하지만 결과는 시간초과였다. 

LinkedList 를 사용한 결과

 

시간을 더 단축할 아이디어가 없어서 도움을 요청한 결과 코드에서 LinkedList를 ArrayDeque으로 바꿨더니 통과 된다는 이야기를 들었다. 내 생각으로는 ArrayDeque와 LinkedList 모두 제거 연산을 할 때 O(1)로 동작할 텐데라고 생각하며 구현체만 ArrayDeque로 바꿔서 제출해 봤다.

ArrayDeque로 바꾼 결과

문제의 시간 제한인 1초에 아슬아슬하지만 통과하였다. 

 

이전에 cpp 에서 deque을 공부했을 때에는 chunk 단위로 배열과 LinkedList 두 가지 방식이 섞여있는 형태로 되어 있기 때문에 삭제할 때 두 가지 자료구조의 시간복잡도는 차이가 없을 텐데 이해가 안 갔다. 

 

처음에는 LinkedList 가 removeLast() 명령을 수행할때 데이터의 끝까지 탐색해서 그런가?라고 생각했다. LinkedList의 코드를 찾아봤다. 

/**
 * Pointer to first node.
 */
 	transient Node<E> first;

/**
 * Pointer to last node.
 */
	transient Node<E> last;

처음 노드와 끝 노드를 모두 관리하고 있어 그 이유는 아니라는 것을 알았다. 

 

두 구현체가 명령을 수행하는데 걸리는 시간을 좀 더 확실하게 보고 싶어 테스트를 만들었다. 

 

public void test(){
        long beforeTime, afterTime;
        list = new LinkedList<>();
        dq = new ArrayDeque<>();
        System.out.println("데이터 입력 시간");
        System.out.println("------LinkedList-----");
        beforeTime = System.currentTimeMillis();
        for (int i = 0; i < N; i++){
            list.add(i);
        }
        afterTime = System.currentTimeMillis();
        System.out.println("실행 시간 : " + (afterTime - beforeTime) + "ms");
        System.out.println("------ArrayDeque-----");
        beforeTime = System.currentTimeMillis();
        for (int i = 0; i < N; i++){
            dq.add(i);
        }
        afterTime = System.currentTimeMillis();
        System.out.println("실행 시간 : " + (afterTime - beforeTime) + "ms");
        System.out.println("@@@@@@@@@@@@@@@@@@@@@@");

        System.out.println("데이터 제거 시간");
        System.out.println("------LinkedList-----");
        beforeTime = System.currentTimeMillis();
        for (int i = 0; i < N; i++){
            if (i % 2 == 0)
                list.removeFirst();
            else
                list.removeLast();
        }
        afterTime = System.currentTimeMillis();
        System.out.println("실행 시간 : " + (afterTime - beforeTime) + "ms");
        System.out.println("------ArrayDeque-----");
        beforeTime = System.currentTimeMillis();
        for (int i = 0; i < N; i++){
            if (i % 2 == 0)
                dq.removeFirst();
            else
                dq.removeLast();
        }
        afterTime = System.currentTimeMillis();
        System.out.println("실행 시간 : " + (afterTime - beforeTime) + "ms");
    }
}

 

1000만 개의 데이터를 삽입, 삭제하는 데 걸리는 시간을 LinkedList와 ArrayDeque 각각 실험해 보았다. 

 

테스트 결과

그 결과 LinkedList 보다 ArrayDeque의 수행시간이 유의미할 정도로 빠르다는 것을 알았다. 왜 이런 결과가 나왔을까 

 

LinkedList 보다 ArrayDeque의  동작 방식

이 차이를 알기 위해서는 각각의 구현체가 어떻게 이루어져 있는지 알 필요가 있다.

먼저 LinkedList 의 경우 first와 last Node를 관리하고 있는 것을 확인했다. 그렇다면 이 Node는 어떤 정보를 담고 있을까? 

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

 

 

양방향 연결리스트를 구현해 볼때 배우듯이 Node는 data를 담는 부분, 이전 노드의 참조, 다음 노드에 대한 참조로 이루어져 있다. 그렇다면 ArrayDeque는 어떨까? 

 

transient Object[] elements;

/**
 * The index of the element at the head of the deque (which is the
 * element that would be removed by remove() or pop()); or an
 * arbitrary number 0 <= head < elements.length equal to tail if
 * the deque is empty.
 */
transient int head;

/**
 * The index at which the next element would be added to the tail
 * of the deque (via addLast(E), add(E), or push(E));
 * elements[tail] is always null.
 */
transient int tail;

public ArrayDeque() {
        elements = new Object[16 + 1];
    }

 

 

먼저 ArrayDeque 는 가장 앞 원소를 가리킬 포인터, 가장 뒤 원소를 가리킬 포인터를 가지고 있고, 각 데이터들은 elements라는 배열에 저장되어 있다는 것을 알 수 있다. chunk들이 list처럼 이어져 있을 것이라고 생각했는데 그냥 배열처럼 동작하고 있었다. 

 

배열을 기본 크기 (16 + 1)  만큼 할당한 후  -> 1 은 항상 tail 을 null로 관리하기 때문에 저렇게 표현한 것 같다.  

capacity  가 가득 차면 늘려주고 복사하는 방식으로 동작하였고 remove 가 일어나면 해당 칸을 null로 만들어주고 head 나 tail의 포인터를 이동하는 방식으로 되어있었다. 

 

구현 코드를 살펴보니 차이는 있었지만 결국 시간 복잡도는 O(1)로 동일하다는 것은 변함 없었다. 그렇다면 속도의 차이는 어디서 온 걸까?

 

속도 차이의 이유

두 구현체의 속도 차이의 원인을 검색해 본 결과 한 글을 찾게 되었다. 

글을 읽고 내가 생각하지 못한 부분을 알게 되었다. 바로 캐싱이다. 

 

LinkedList는 기본적으로 선형 자료구조이지만 저장된 데이터들이 선형적으로 있는 것이 아니다. 따라서 메모리의 공간 지역성을 활용하는 CPU의 동작에서의 이점을 전혀 볼 수 없다. 그 반면에 ArrayDeque은 배열로 되어있고, 이는 CPU 의 메모리 캐싱의 이점을 최대한 활용할 수 있는 형태이다. 

 

각각의 자료구조가 명령을 수행하기 위해 한 번의 메모리 접근이 필요하다고 하더라도 1, 2, 3을 차례로 접근하는 것과 1, 10000, 1000을 차례로 접근하는 데에 걸리는 시간은 차이가 있고 이것이 누적된다면 결과적으로는 큰 차이가 발생한다. 

 

ArrayDeque를 Java API 문서에서 찾아보면 다음과 같은 문장이 있다. 

This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.

 ArrayDeque는 Stack과 LinkedList와 동일한 동작을 지원하더라도 속도적으로 더 빠를 수 있다는 것을 인지해야겠다. 

 

결론

- ArrayDeque는 LinkedList와 비교했을 때 데이터의 양이 많아질수록 연산에서 유의미하게 빠른 동작을 지원한다.

- 이 차이는 ArrayDeque는 배열 기반 동작, LinkedList는 참조 기반 동작을 한다는 점에서 생겨난다.

- 자료구조를 사용할 때에는 단순하게 시간복잡도만 생각하지 말고 해당 자료구조의 구체적인 동작 방식을 고려하여 최적의 자료구조를 선택하자.