Open olrlobt opened 1 year ago
우리는 이 이슈에서 Queue 인터페이스 구현체 중 ArrayDeque와 LinkedList에 대해서 살펴보고자 한다. 사실 ArrayDeque와 LinkedList는 Queue의 구현체이기도 하지만 Deque의 구현체이기도 하다. Java에서 Deque 인터페이스는 Queue 인터페이스를 확장한 인터페이스로 “double ended queue”의 줄임말로 말 그대로 앞 뒤 모두에 삽입, 삭제가 가능하다는 특징이 있다. 이러한 특징을 기반으로 ArrayDeque와 LinkedList에 대해서 비교해보자.
먼저 ArrayDeque에 대해서 살펴보자. ArrayDeque는 이름에서 알 수 있듯이 배열을 기반으로 하는 Deque의 구현체이다. 공식 문서의 내용을 살펴보면 ArrayDeque의 특징은 다음과 같다.
아마도 마지막 문장 때문에 우리는 Queue를 구현할 때 무의식중에 ArrayDeque를 쓰고 있지 않을까 생각이 든다. 이 외에도 배열을 기반으로 구현되어 있기 때문에 인덱스를 기반으로 데이터에 접근할 때 O(1)의 시간 복잡도를 가지며 Queue형태에서 데이터를 삽입, 삭제하는 경우 O(1)의 시간복잡도를 가진는 특징이 있다.
LinkedList는 list의 구현체로 ArrayDeque와 달리 null 요소를 추가할 수 있다. 또한 배열로 데이터를 다루는 ArrayDeque와 달리 Node를 기반으로 하여 데이터 간의 연결을 하기 때문에 이와 관련하여 더 많은 메모리를 소모할 수 있다. LinkedList의 경우에는 데이터를 삽입, 삭제하는 경우 O(1)의 시간복잡도를 가지지만 중앙에 있는 데이터에 접근하는 경우에는 O(n)의 시간복잡도를 가지게 된다.
대부분의 경우 ArrayDeque가 더욱 효과적이다.
다음은 ArrayDeque와 LinkedList의 성능을 비교하기 위해서 삽입과 삭제 300,000번을 반복적으로 수행하는 코드를 작성해보았다.
작성 코드
import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;
public class 성능테스트 {
public static void main(String[] args) {
// TODO Auto-generated method stub
Queue<Integer> q1 = new LinkedList<Integer>();
Queue<Integer> q2 = new ArrayDeque<Integer>();
long startTime, endTime;
double elapsedTime;
startTime = System.nanoTime();
for (int i = 0; i < 300000; i++)
q1.offer(i);
endTime=System.nanoTime();
elapsedTime=(endTime-startTime)/1000000.0;
System.out.println("linkedlist 삽입 "+elapsedTime+"ms");
startTime = System.nanoTime();
for (int i = 0; i < 300000; i++)
q1.poll();
endTime=System.nanoTime();
elapsedTime=(endTime-startTime)/1000000.0;
System.out.println("linkedlist 삭제 "+elapsedTime+"ms");
startTime = System.nanoTime();
for (int i = 0; i < 300000; i++)
q2.offer(i);
endTime=System.nanoTime();
elapsedTime=(endTime-startTime)/1000000.0;
System.out.println("arraydeque 삽입 "+elapsedTime+"ms");
startTime = System.nanoTime();
for (int i = 0; i < 300000; i++)
q2.poll();
endTime=System.nanoTime();
elapsedTime=(endTime-startTime)/1000000.0;
System.out.println("arraydeque 삭제 "+elapsedTime+"ms");
}
}
위의 작성 코드를 실행해보면 다음과 같은 결과를 얻을 수 있다.
💡 linkedlist 삽입 8.4454ms linkedlist 삭제 2.2033ms arraydeque 삽입 4.1884ms arraydeque 삭제 2.8768ms
삭제 속도는 크게 다르지 않으나 삽입에서 linkedlist가 arraydeque보다 훨씬 오래 걸렸다. 이는 linkedlist의 구조적 특징 때문으로 각각의 데이터 노드는 link로 연결되어 있기 때문에 노드를 생성하고 link로 이를 연결하는 과정에서 오버헤드가 발생한다. 그래서 ArrayDeque를 사용하는 것이 더 빠른 속도로 반복을 수행할 수 있었다. 시간적인 측면 뿐만 아니라 공간적인 측면에서도 LinkedList의 구조(node의 연결)에 의해서 어쩔 수 없는 메모리의 사용이 추가적으로 발생하게 된다. 이러한 요인들로 인해 Oracle에서도 LinkedList가 아닌 ArrayDeque를 사용하는 것을 추천하고 있다.
좀 더 자세히 살펴보기 위해서 삽입과 삭제에서 무슨일이 일어나는지 좀 더 자세히 살펴보고자 했다. 왜냐하면 ArrayDeque의 poll이나 remove가 O(n)이 아니라는 것을 알았기 때문이다.. 원래는 삭제 시에 배열의 맨 앞 요소를 지우면 앞으로 요소들을 하나씩 옮겨야한다고 생각했는데 그게 아니였다..! ArrayDeque가 원형리스트의 형태로 구현되어 있기 때문이다.. 실제로는 배열을 관리하지만 나머지 연산을 통해서 원형 리스트이 형태로 접근할 수 있는 것이였다. 그래서 맨 앞 요소를 지운다면 해당 요소를 null로 만들고 head를 뒤로 밀어서 O(1)에 remove를 처리할 수 있다. 구현이 신기해서 소스코드를 좀 자세히 살펴봤는데 재밌는 부분이 많았다!
특징적인 부분으로는
그렇다면 LinkedList는 어떨까? LinkedList는 ArrayDeque에 비해서 좀 더 코드가 읽기 쉬웠다. 실제로 구현을 많이 해보기도 해서 그런 것 같다.
LinkedList의 특징적인 부분으로는
그럼 이제 삽입 삭제 시에 어떤 일이 일어나는지 알았으니까 좀 더 자세히 분석해볼 수 있을 것 같다.
분명 LinkedList가 효율적인 상황이 생길 수 있다.
만약 내가 모든 원소들을 탐색하면서 큐 중간에 있는 원소를 삭제해야하는 경우가 있다고 생각해보자. 이미 탐색으로 인해 O(n)의 시간복잡도를 가지고 있는 상태에서
즉, Queue의 원래 용도인 FIFO 말고, 좀 더 확장성 있는 자료구조를 원한다면 ArrayDeque보다는 LinkedList를 이용하는 것이 더 빠른 속도를 만들어낼 수 있다는 것을 알 수 있다.
또한 구조적으로 LinkedList를 쓸 수 밖에 없는 경우가 생길 수 있다.
만약 queue 중간에 null이 오는 경우(가 있을수 있나 싶긴한데..)에도 ArrayDeque는 사용할 수 없다. 이는 ArrayDeque의 구조적인 한계점이다.
상황을 종합해봤을 때 우리는 대부분의 경우에 ArrayDeque를 사용하는 것이 더 효율적임을 알 수 있었다. 하지만 Queue의 확장성(구조적 혹은 기능적)을 위해서는 LinkedList를 사용해야 한다고 이해할 수 있다. 오랜만에 소스코드를 뜯어봤는데 생각보다 배울점이 많았다. 여러분도 한번해보시길!
https://docs.oracle.com/javase/tutorial/collections/implementations/deque.html
https://yjacket.tistory.com/m/48
https://docs.oracle.com/javase/8/docs/api/java/util/ArrayDeque.html
https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html
https://tecoble.techcourse.co.kr/post/2021-05-10-stack-vs-deque/
👍 문제
Pg.63에서는 Queue 인터페이스와 구현체에 대해서 서술하고 있다. 하지만 내가 싸피 와서 배운
ArrayDeque
는 다루고 있지 않아서 속상하다.ArrayDeque
에 대한 설명과LinkedList로 구현 한 Queue
와의 속도 차이를 상황별로 비교해 주었으면 좋겠다.ex) 어떤 경우에 LinkedList가 더 효율 적이고, 어떤 경우에는 ArrayDeque가 더 효율 적인지.
✈️ 선정 배경
일반적인 백준 문제에서는
를 쓰는 것보다
를 쓰는 것이 훨씬 빨라서 ArrayDeque를 자주 애용하고 있는데, 자문을 받았을 때는 문제의 성격에 따라 다르다고 한다.
왜 다른 지, 어떨 때 LinkedList를 쓰는게 더 빠른 지 의문이 생겼다.
📺 관련 챕터 및 레퍼런스
story.04 어디에 담아야 하는지 pg.63 pg 72~76
🐳 비고
난 Queue를 좋아한다.