[Java] BOJ 18258: LinkedList vs ArrayDeque

---

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

---

 BOJ에서 제공하는 큐 문제다. LinkedList와 ArrayDeque 모두 큐 자료구조를 구현할 수 있는 클래스다. 하지만 각각의 구조와 성능 측면에서 명확한 차이가 존재한다. 참고로 결론부터 말하자면, 위와 같은 큐 문제에서는 ArrayDeque을 선택하는 편이 합리적이다.

---

LinkedList, ArrayDeque 차이점은?

---

메모리 효율 측면

ㅁ LinkedList

 LinkedList는 노드 기반의 연결리스트이다. 각 노드는 앞뒤로 연결되어 있기 때문에 노드를 추가하거나 삭제하는 연산이 빠르지만 메모리효율성 측면에서는 불리할 수 있다. 각 노드가 단순히 데이터를 저장하는 것 이외에도 두 개의 포인터를 저장하기 때문이다.

 

ㅁ ArrayDeque

 ArrayDeque은 배열 기반의 동적 큐이다. 배열을 사용해 큐의 앞과 뒤에서 삽입 또는 삭제를 처리한다. 데이터가 연속적인 메모리공간에 저장되므로 메모리 접근속도가 상대적으로 빠르다.

---

크기 조정 측면

ㅁ LinkedList

 노드를 연결하는 방식으로 크기가 변한다. 새로운 노드를 추가하거나 삭제하는 방식으로 크기가 조정되며, null 값도 포함할 수 있다.

 

ㅁ ArrayDeque

 배열 기반으로 데이터를 저장하기 때문에, 배열이 가득 차면 새로운 배열을 생성하고 기존 데이터를 복사하는 방식으로 리사이징 한다. 즉, 배열 복사가 발생해 빈번한 삽입/삭제 시 불리할 수 있다.

---

 

ArrayDeqeue: 빠른 데이터접근, 캐시효율성

LinkedList: 빈번한 삽입과 삭제

---

멀티스레드 환경에서는 어떨까?

 

 그전에 Thread-Safety에 대해 설명하자면, 이는 여러 스레스가 동시에 동일한 객체나 데이터를 접근할 때, 데이터의 일관성이나 정확성이 보장되는 특성을 의미한다. 간단히 말해, 여러 스레드가 동시에 특정 객체를 수정하거나 읽는 작업을 하더라도 결과가 예상대로 나오는지를 보장하는 것이다.

 

 ArrayDeque은 내부적으로 배열을 사용하여 데이터를 저장하며, 이를 동기화하지 않는다. 그렇기 때문에 여러 스레드가 동시에 한 ArrayDeque 객체에 접근해서 데이터를 수정하는 등 어떠한 작업을 한다면 데이터가 손상될 위험이 존재한다. 즉, 스레드에 안전하지 않다.

 

 조금 더 와닿을 수 있게 설명을 추가하자면, 예를 들어 스레드 A가 데이터를 추가하려고 하는데 충분한 메모리공간이 없어 리사이징이 발생한다고 하자. 동시에 스레드 B는 데이터를 삭제하려고 한다. 이때 ArrayDeque의 배열 상태가 불안정해질 수 있다는 말이다.

 

 멀티스레드 환경에서 ArrayDeque을 안전하게 사용하기 위해, 여러 스레드가 동시에 접근할 수 없도록 동기화를 통해 조정할 수 있다. 특정 작업을 하나의 스레드만 수행하도록 보장하는 방법이다. 자바에서는 주로 synchronized 키워드를 사용하거나 ReentrantLock과 같은 명시적인 락을 사용해 구현한다. 

Queue<Integer> queue = new ArrayDeque<>();

public synchronized void enqueue(Integer value) {
    queue.add(value);
}

public synchronized Integer dequeue() {
    return queue.poll();
}

 

 이렇게 하면 동시에 두 스레드가 enqueue 또는 dequeue 작업을 수행할 때, 한 스레드가 끝날 때까지 다른 스레드는 대기하게 되어 데이터 손상을 방지할 수 있다.

 

 근데 이건 무슨 말인가. 동기화를 추가한다는 건 결국 성능에 영향을 미친다는 뜻이다. 서비스운영관리에서 배웠듯이, 동시성이 줄어든다는 건 그만큼 병목현상을 야기할 수 있다. 자세한 이야기는 다음에 이어가도록 하겠다.

---