LinkedList는 ArrayDeque 보다 메모리를 많이 사용한다.

 

문제 : https://www.acmicpc.net/problem/2346 

메모리 초과 코드 : https://ideone.com/TxRwHV

 

 

Deque 자료구조

 

위 문제를 Deque 자료 구조를 사용하여 풀 수 있되, 구현체로 LinkedList를 사용하면 메모리 초과가 발생한다.

반대로 ArrayDeque 구현체를 사용하면 메모리 초과가 발생하지 않는다.

 

LinkedList의 특징으로는 연속적인 메모리 공간을 사용하지 않고, 참조(Reference) 필드를 사용하여 다음 노드를 가리킨다. 반면에 ArrayDeque는 배열 기반의 구현체이므로 연속적인 메모리 공간을 사용한다.

 

 

Deque 구현체로 LinkedList를 사용하면 큐에 값이 저장될 때마다 새로운 노드가 생성된다. 이 노드에서는 이전 노드를 가리키는 참조 포인터, 데이터, 다음 노드를 가리키는 참조 포인터가 저장된다. 각 노드들은 이전 노드와 다음 노드를 가리키는 참조 필드를 가지고 있기 때문에 참조 필드로 인한 메모리 사용량이 크다.

class Node<E> {
    E item;         // 데이터 (노드에 저장되는 값)
    Node<E> next;   // 다음 노드를 가리키는 참조
    Node<E> prev;   // 이전 노드를 가리키는 참조
}

class LinkedListDeque<E> {
    Node<E> head;   // 첫 번째 노드 (맨 앞)
    Node<E> tail;   // 마지막 노드 (맨 뒤)
    int size;       // 현재 노드 개수
}

DoublyLinkedList

 

 

반면에 Deque 구현체로 ArrayDeque를 사용하면 이미 생성되어 있는 배열에 값을 저장하면 된다. 참조 필드가 없더라도 인덱스를 통해 이전 값과 다음 값에 접근할 수 있다. 

class ArrayDeque<E> {
    Object[] elements;  // 요소를 저장하는 배열
    int head;           // 첫 번째 요소의 인덱스
    int tail;           // 마지막 요소의 인덱스 (삽입 위치)
    int size;           // 현재 요소 개수
    int capacity;       // 배열 크기
}

 

ArrayDeque를 생성할 때 명시적으로 크기를 지정하지 않으면 기본적으로 16개의 슬롯을 갖는다. 요소를 추가하다가 배열이 꽉 차면 배열 크기를 2배로 확장한다. 이때, 기존 배열의 2배 크기를 갖는 새로운 배열을 생성하여 기존 배열의 값을 복사한다. 이 과정에서 발생하는 시간 복잡도는 O(N)이다.

Deque<Integer> dq = new ArrayDeque<>();

 

 

 

결론적으로

• LinkedList : 각 노드가 참조 필드를 갖기 때문에 메모리 사용량이 높다
• ArrayDeque : 미리 생성된 배열에 값을 저장하기 때문에 상대적으로 메모리 사용량이 낮다.

또한, 두 구현체 모두 head 및 tail에 값을 삽입할 때 발생하는 시간 복잡도는 O(1)이다. 단, ArrayDeque에서 배열의 크기가 꽉 차면 배열 복사가 발생하기 때문에 이 경우에는 O(N)이 소모된다.