Queue 인터페이스의 구현체 중 하나인 LinkedList와 ArrayDeque의 속도 차이는 얼마나 나고, 언제 써야 효율적일까? #5

olrlobt · 2023-09-10T14:49:03Z

👍 문제

Pg.63에서는 Queue 인터페이스와 구현체에 대해서 서술하고 있다. 하지만 내가 싸피 와서 배운 ArrayDeque는 다루고 있지 않아서 속상하다. ArrayDeque에 대한 설명과 LinkedList로 구현 한 Queue와의 속도 차이를 상황별로 비교해 주었으면 좋겠다.

ex)
어떤 경우에 LinkedList가 더 효율 적이고,
어떤 경우에는 ArrayDeque가 더 효율 적인지.

✈️ 선정 배경

일반적인 백준 문제에서는

Queue<Node> que = new LinkedList<>();

를 쓰는 것보다

Queue<Node> que = new ArrayDeque<>();

를 쓰는 것이 훨씬 빨라서 ArrayDeque를 자주 애용하고 있는데,
자문을 받았을 때는 문제의 성격에 따라 다르다고 한다.

왜 다른 지, 어떨 때 LinkedList를 쓰는게 더 빠른 지 의문이 생겼다.

📺 관련 챕터 및 레퍼런스

story.04 어디에 담아야 하는지
pg.63
pg 72~76

🐳 비고

난 Queue를 좋아한다.

The text was updated successfully, but these errors were encountered:

daminzzi · 2023-09-12T09:31:39Z

📔시작하기 전에

우리는 이 이슈에서 Queue 인터페이스 구현체 중 ArrayDeque와 LinkedList에 대해서 살펴보고자 한다. 사실 ArrayDeque와 LinkedList는 Queue의 구현체이기도 하지만 Deque의 구현체이기도 하다. Java에서 Deque 인터페이스는 Queue 인터페이스를 확장한 인터페이스로 “double ended queue”의 줄임말로 말 그대로 앞 뒤 모두에 삽입, 삭제가 가능하다는 특징이 있다. 이러한 특징을 기반으로 ArrayDeque와 LinkedList에 대해서 비교해보자.

📖ArrayDeque와 LinkedList의 차이점

먼저 ArrayDeque에 대해서 살펴보자. ArrayDeque는 이름에서 알 수 있듯이 배열을 기반으로 하는 Deque의 구현체이다. 공식 문서의 내용을 살펴보면 ArrayDeque의 특징은 다음과 같다.

크기를 미리 지정, 또 재설정할 수 있으며 그 크기에 제한이 없다.
null 요소는 저장되지 않는다.
외부 동기화가 되지 않는다(멀티 쓰레드에서 동시 접속 안됨, synchronized를 이용해서 가능하게 만들 수 있음).
stack을 구현할 때 Stack class보다 빠르고, 대기열과 같은 Queue를 구현할 때 LinkedList보다 빠르다.

아마도 마지막 문장 때문에 우리는 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를 처리할 수 있다. 구현이 신기해서 소스코드를 좀 자세히 살펴봤는데 재밌는 부분이 많았다!

특징적인 부분으로는
- 배열의 기본 초기사이즈를 설정하지 않는다면 16으로 초기화되고 이후에 삽입이 일어나면서 16보다 많은 수의 원소가 들어오면 현재 사이즈에 따라서 배열을 얼마나 확장할지를 grow라는 함수로 결정한다.
- add, poll, remove 등 기본적으로 queue의 기능을 하는 함수들은 O(1)에 끝날 수 있도록 구현되어 있다.
- 중간 삭제의 경우 index를 매개변수로 가지는 delete 함수를 사용하는데 이 경우 arraycopy를 부르기 때문에 O(n)의 시간 복잡도를 가질 수 있다.
- 그리고 object로 removeFirstOccurence를 부르면 배열 탐색에 한번, delete에서 한번 총 2번의 O(n) 함수가 호출된다.
- 그리고 공식문서를 열심히 읽어봤는데 중간 삽입을 할 수 있는 함수가 없는 것으로 보인다..
그렇다면 LinkedList는 어떨까? LinkedList는 ArrayDeque에 비해서 좀 더 코드가 읽기 쉬웠다. 실제로 구현을 많이 해보기도 해서 그런 것 같다.

LinkedList의 특징적인 부분으로는
- 삽입 시 객체 생성이 발생한다. 이 때문에 배열에 삽입하는 것보다 시간이 오래 걸린다.
- 삭제 시에는 unlink라는 함수를 사용하는데 이는 삭제하고자하는 노드의 앞뒤를 끊어서 list에서 쫓아내는 방식을 택하고 있다.
- 중간 삭제 시에는 for문을 돌면서 삭제하고 싶은 노드를 찾고 해당 노드를 unlink하는 방식을 사용한다.
그럼 이제 삽입 삭제 시에 어떤 일이 일어나는지 알았으니까 좀 더 자세히 분석해볼 수 있을 것 같다.
분명 LinkedList가 효율적인 상황이 생길 수 있다.

만약 내가 모든 원소들을 탐색하면서 큐 중간에 있는 원소를 삭제해야하는 경우가 있다고 생각해보자. 이미 탐색으로 인해 O(n)의 시간복잡도를 가지고 있는 상태에서
- ArrayDeque의 경우 index를 통해서 원소를 탐색하고 있었을테니까 delete(index) 함수를 불렀을 것이다. 이러면 배열 복제가 일어나므로 이럴 때는 O(n)의 시간복잡도를 가진다.
- LinkedList의 경우 각각의 node를 통해서 원소를 탐색하고 있었을테니까 unlink(node) 함수를 불러서 삭제를 했을 것이다. 이렇게 되면 O(1)의 시간복잡도로 노드를 삭제할 수 있다.
즉, Queue의 원래 용도인 FIFO 말고, 좀 더 확장성 있는 자료구조를 원한다면 ArrayDeque보다는 LinkedList를 이용하는 것이 더 빠른 속도를 만들어낼 수 있다는 것을 알 수 있다.
또한 구조적으로 LinkedList를 쓸 수 밖에 없는 경우가 생길 수 있다.

만약 queue 중간에 null이 오는 경우(가 있을수 있나 싶긴한데..)에도 ArrayDeque는 사용할 수 없다. 이는 ArrayDeque의 구조적인 한계점이다.

결론

상황을 종합해봤을 때 우리는 대부분의 경우에 ArrayDeque를 사용하는 것이 더 효율적임을 알 수 있었다. 하지만 Queue의 확장성(구조적 혹은 기능적)을 위해서는 LinkedList를 사용해야 한다고 이해할 수 있다. 오랜만에 소스코드를 뜯어봤는데 생각보다 배울점이 많았다. 여러분도 한번해보시길!