Java Deque / ArrayDeque, LinkedListDeque, ConcurrentLinkedDeque, LinkedBlockingDeque 특징

서론

---

Deque를 사용하면서 아무생각 없이 ArrayDeque를 사용하고 있었는데 다른 코드에서 LinkedList 로 Deque를 구현한것을 보았고 또 Deque 구현체가 꽤 많은것을 알게되었다.

Deque 구현체들에 대해 간단히 조사하고 정리하고,

ArrayDeque와 LinkedListDeque 사이에 차이가 있고 무엇이 더 효율적일지 찾아보면서 이 글을 작성하게 되었다.

본론

---

Deque 란?

참고: https://haenny.tistory.com/365

간단하게 Deque에 대해 설명하자면

1. 원소의 추가와 삭제를 양쪽 끝부분에서 지원하는 자료구조이다.
2. Deque는 사용자가 입구로만 나오고 삭제하게 하면 stack으로
3. 입구로만 들어가고 출구로만 나오면 queue 로 사용할 수 있다.

Java 에서 Deque

---

 

참고: https://www.happycoders.eu/de/algorithmen/java-deque/

자바에서 Deque는 인터페이스로 되어져 있고 이를 구현한 다양한 클래스들이 있다.

• ArrayDeque
• LinkedList
• ConcurrentLinkedDeque
• LinkedBlockingDeque

등등이 있다.

ConcurrentLinkedDeque, LinkedBlockingDeque

---

멀티 스레드 환경에서는 스레드 세이프한 Deque를 사용해야한다.

 

둘의 공통점은

1. Deque 를 구현한 구현체이다
2. 스레드 세이프 하다.
3. linked node를 사용한다.

둘의 차이점은

• ConcurrentLinkedDeque
  • 잠금 메커니즘을 사용하여 한 번에 단일 스레드에서만 데이터를 작동할 수 있도록 할 때 사용한다.
  • 상대적으로 high overhead 이나 확장성이 좋다.
  • non - blockig queue 이다.
• LinkedBlockingDeque
  • 각각의 스레드가 공유 데이터에 액세스 할 수 있도록 할 때 사용한다
  • 스탠다드한 blocking deque 클래스이다. 상대적으로 low overhead 이나 확장성이 좋지 않다.
  • optionally-bounded blocking queue 이다.

ArrayDeque vs LinkedDeque

---

Array vs LinkedList

• 특정 원소에 접근
  • Array O(1) 이 걸린다.
  • LinkedList O(n) 이 걸린다.
• 원소 삽입이나 삭제
  • Array는 size를 바꿀 수 없다. 항상 데이터를 copy 해줘야 한다. O(n)
  • LinkedList 에서는 원하는 위치에 원소 삽입이나 삭제를 O(1) 으로 할 수 있다.
• 메모리
  • int 를 기준으로
  • Array는 4bytes
  • LinkedList Node는 24bytes (header, data, pad, pointer)
• 메모리 효율성
  • ArrayList 는 새로운 element를 위해 공간을 미리 (필요한 크기 보다 더) 예약한다.
  • LinkedList 는 새로운 element 를 위한 공간 하나만 할당해준다
• GC
  • Array 상대적으로 처리하기 쉬움
  • LinkedList 상대적으로 처리하기 어려움

 

여러 블로그와 문서들을 찾아봤다.

결론은 상황에 따라 다르지만 웬만하면 ArrayDeque가 효율적일것이다 였다.

 

참고 블로그

https://www.happycoders.eu/algorithms/array-vs-linked-list/

https://www.happycoders.eu/de/algorithmen/java-deque/

https://tech-monster.tistory.com/159