Java ArrayDeque 써야하는 이유
안녕하세요
안드로이드 개발자가 되기 위해 노력하는 서경원입니다.
이해가 안되는 내용이나 제가 잘못 적은 부분이 있다면 꼭 댓글 남겨주세요.
ArrayDeque
먼저 ArrayDeque의 특징에 대해 알아보겠습니다.
- 더블 엔드 큐: 큐(Queue)의 선입선출(FIFO)과 스택(Stack)의 후입선출(LIFO)을 모두 지원하는 자료 구조입니다. 큐의 앞과 뒤에서 원소를 추가하거나 제거할 수 있습니다.
- 내부 배열 기반:
ArrayDeque는 내부적으로 동적 배열(dynamic array)을 사용하여 구현됩니다. 배열은 연속된 메모리 공간에 요소를 저장하므로 인덱스를 이용한 빠른 접근이 가능합니다. - 동적 크기 조절: 배열 기반이지만 내부적으로 배열의 크기를 동적으로 조절할 수 있습니다. 크기를 확장하거나 축소할 때 메모리 할당 및 해제 작업이 발생하지만, 효율적으로 처리됩니다.
- 빠른 연산: 큐의 앞과 뒤에서의 추가와 제거 연산은 O(1)의 시간 복잡도를 가집니다. 배열 기반이므로 인덱스를 이용한 빠른 접근이 가능합니다.
- 스레드 안전하지 않음:
ArrayDeque는 기본적으로 스레드 안전하지 않습니다. 멀티스레드 환경에서는 동기화가 필요합니다. - NULL 요소 허용:
ArrayDeque는 NULL 값을 원소로 가질 수 있습니다.
ArrayDeque는 Stack과 Queue의 기능을 모두 할 수 있는 것을 알 수 있습니다.
ArrayDeque에 대해 자세히 더 알아보기 위해 공식 문서를 들여다봤습니다.
https://docs.oracle.com/javase/8/docs/api/java/util/ArrayDeque.html
Resizable-array implementation of the Deque interface. Array deques have no capacity restrictions; they grow as necessary to support usage. They are not thread-safe; in the absence of external synchronization, they do not support concurrent access by multiple threads. Null elements are prohibited. This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.
Most ArrayDeque operations run in amortized constant time. Exceptions include remove, removeFirstOccurrence, removeLastOccurrence, contains, iterator.remove(), and the bulk operations, all of which run in linear time.
The iterators returned by this class's iterator method are fail-fast: If the deque is modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will generally throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.
This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces.
This class is a member of the Java Collections Framework.
Deque 인터페이스의 크기를 조정할 수 있는 배열 구현. ArrayDeque는 용량 제한이 없으며 사용을 지원하기 위해 필요에 따라 증가합니다. 이들은 스레드 안전하지 않습니다. 외부 동기화가 없으면 여러 스레드에 의한 동시 액세스를 지원하지 않습니다. Null 요소는 금지됩니다. 이 클래스는 Stack으로 사용할 때 Stack보다 빠르며 Queue로 사용할 때는 LinkedList보다 빠릅니다.
대부분의 ArrayDeque 작업은 상각된 일정 시간으로 실행됩니다. 예외에는 remove, removeFirstOccurrence, removeLastOccurrence, contains, iterator.remove() 및 대량 작업이 포함되며 모두 선형 시간으로 실행됩니다.
이 클래스의 iterator 메서드에 의해 반환되는 iterator는 오류가 발생하지 않습니다. iterator 가 생성된 후 언제든지 Deque가 수정되면 iterator는 일반적으로 ConcurrentModificationException를 사용합니다. 따라서 동시 수정에 직면하면 iterator는 나중에 결정되지 않은 시간에 임의의 비결정적인 동작을 감수하지 않고 신속하고 깨끗하게 실패합니다.
반복기의 실패-빠른 동작은 일반적으로 동기화되지 않은 동시 수정이 있을 때 어떤 hard guarantees도 할 수 없기 때문에 보장될 수 없다는 것에 유의하십시오. 실패-빠른 반복기는 최선의 노력을 바탕으로 ConcurrentModificationException 를 사용합니다. 따라서 반복기의 실패-빠른 동작은 버그를 탐지하는 데만 사용되어야 한다는 점에서 이 예외에 의존하는 프로그램을 작성하는 것은 잘못된 것입니다.
이 클래스와 해당 반복기는 수집 및 반복기 인터페이스의 모든 선택적 방법을 구현합니다.
이 클래스는 Java Collections Framework의 구성원입니다.
위와 같이 공식 문서에는 ArrayDeque에 대한 자세한 설명이 적혀있습니다. 그 중,
“이 클래스는 Stack으로 사용할 때 Stack보다 빠르며 Queue로 사용할 때는 LinkedList보다 빠릅니다.”
ArrayDeque는 Stack으로 사용할 때 Stack보다 빠르고 Queue로 사용할 때 LinkedList보다 빠르다고 적혀있습니다.
ArraDeque의 코드와 함께 ArrayDeque에 대해 살펴보면서
왜 ArrayDeque가 Stack과 Queue로 사용할 때 더 빠른 지 알아보려고 합니다.
public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable {
transient Object[] elements;
transient int head;
transient int tail;
public ArrayDeque() {
this.elements = new Object[16];
}
public void addFirst(E e) {
if (e == null) {
throw new NullPointerException();
} else {
Object[] es = this.elements;
es[this.head = dec(this.head, es.length)] = e;
if (this.head == this.tail) {
this.grow(1);
}
}
}
public void addLast(E e) {
if (e == null) {
throw new NullPointerException();
} else {
Object[] es = this.elements;
es[this.tail] = e;
if (this.head == (this.tail = inc(this.tail, es.length))) {
this.grow(1);
}
}
}
public boolean offerFirst(E e) {
this.addFirst(e);
return true;
}
public boolean offerLast(E e) {
this.addLast(e);
return true;
}
public E pollFirst() {
Object[] es;
int h;
E e = elementAt(es = this.elements, h = this.head);
if (e != null) {
es[h] = null;
this.head = inc(h, es.length);
}
return e;
}
public E pollLast() {
Object[] es;
int t;
E e = elementAt(es = this.elements, t = dec(this.tail, es.length));
if (e != null) {
es[this.tail = t] = null;
}
return e;
}
public E peekFirst() {
return elementAt(this.elements, this.head);
}
public E peekLast() {
Object[] es;
return elementAt(es = this.elements, dec(this.tail, es.length));
}
public boolean add(E e) {
this.addLast(e);
return true;
}
public boolean offer(E e) {
return this.offerLast(e);
}
public E remove() {
return this.removeFirst();
}
public E poll() {
return this.pollFirst();
}
public E element() {
return this.getFirst();
}
public E peek() {
return this.peekFirst();
}
public void push(E e) {
this.addFirst(e);
}
public E pop() {
return this.removeFirst();
}
}
ArrayDeque의 코드 입니다. 필요한 부분만 가져와서 설명드리겠습니다.
public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable {
transient Object[] elements;
transient int head;
transient int tail;
public ArrayDeque() {
this.elements = new Object[16];
}
}ArrayDeque 내부에는 elements 배열이 존재 합니다.
elements 배열에 값을 저장합니다.
기본 생성자의 경우 길이 16의 배열을 생성합니다.
그리고 미리 설명드리자면 ArrayDeque는 원형 큐 구조로 되어있기 때문에 head와 tail로 원형 큐를 관리합니다.
public void addFirst(E e) {
if (e == null) {
throw new NullPointerException();
} else {
Object[] es = this.elements;
es[this.head = dec(this.head, es.length)] = e;
if (this.head == this.tail) {
this.grow(1);
}
}
}
public void addLast(E e) {
if (e == null) {
throw new NullPointerException();
} else {
Object[] es = this.elements;
es[this.tail] = e;
if (this.head == (this.tail = inc(this.tail, es.length))) {
this.grow(1);
}
}
}
public boolean offerFirst(E e) {
this.addFirst(e);
return true;
}
public boolean offerLast(E e) {
this.addLast(e);
return true;
}
public boolean add(E e) {
this.addLast(e);
return true;
}
public boolean offer(E e) {
return this.offerLast(e);
}
public void push(E e) {
this.addFirst(e);
}ArrayDeque의 배열에 값을 추가하는 메서드들을 살펴보겠습니다.
ArrayDeque가 Stack과 Queue를 대신할 수 있다는 설명처럼 add, offer, push가 모두 구현되어있는 것을 볼 수 있습니다.
이들 모두 addFirst 또는 addLast를 최종적으로 사용하기 때문에 addFirst와 addLast 함수에 대해 설명하겠습니다.
public void addFirst(E e) {
if (e == null) {
throw new NullPointerException();
} else {
Object[] es = this.elements;
es[this.head = dec(this.head, es.length)] = e;
if (this.head == this.tail) {
this.grow(1);
}
}
}
static final int dec(int i, int modulus) {
--i;
if (i < 0) {
i = modulus - 1;
}
return i;
}dec(this.head, es.length)를 실행하는 것을 볼 수 있습니다.
dec 메서드를 살펴보면 head를 -1 하고 0보다 작아진 경우, 배열의 마지막 인덱스를 가리키도록 하는 것을 알 수 있습니다.
배열의 head에 e를 삽입하고 head가 tail과 같은지 확인합니다.
head와 tail이 같아졌다는 의미는 배열이 꽉 찼다는 의미입니다.
배열이 꽉 찼다면 현재 배열의 크기가 64보다 작은 경우는
(새로운 배열의 크기 = 현재 배열의 크기 * 2 + 2 )가 되고
배열의 크기가 64보다 큰 경우는
(새로운 배열의 크기 = 현재 배열의 크기 + (현재 배열의 크기 / 2) 가 됩니다
public void addLast(E e) {
if (e == null) {
throw new NullPointerException();
} else {
Object[] es = this.elements;
es[this.tail] = e;
if (this.head == (this.tail = inc(this.tail, es.length))) {
this.grow(1);
}
}
}
static final int inc(int i, int modulus) {
++i;
if (i >= modulus) {
i = 0;
}
return i;
}addLast는 addFirst와 로직이 같지만 tail에 값을 넣은 뒤 tail을 +1 해줍니다
그러면 ArrayDeque가 Stack과 LinkedList보다 빠른 이유는 뭘까?
- 배열을 기반으로 되어 있어 인덱스로 빠른 접근이 가능하기 때문입니다. (메모리 지역성으로 인해 메모리를 더 효과적으로 접근할 수 있다는 점이 있습니다.)
- Stack은 내부적으로 Vector를 사용하는 데, Vector는 동기화가 구현되어 있어 동기화 오버헤드와 락으로 인해 느릴 수 있지만 ArrayDeque는 동기화가 구현되어 있지 않기 때문입니다.
- LinkedList는 삽입,삭제할 때마다 포인터에 대한 조작이 필요합니다. ArrayDeque는 인덱스를 통해 삽입,삭제만 하면 되기 때문에 더 빠릅니다.
- LinkedList는 각 노드가 포인터를 가지고 있지만 ArrayDeque는 배열을 통해 관리하므로 메모리를 더 효율적으로 사용 가능합니다.
ArrayDeque는 remove(Object) 처럼 배열을 모두 탐색해야 하는 경우 외에는 빠른 연산 속도를 가지고 있고 Stack과 LinkedList를 사용하는 것보다 효과적인 것을 알 수 있었습니다.
'자바' 카테고리의 다른 글
| 자바의 HashSet, HashMap 코드와 함께 더 알아보기 (0) | 2023.08.26 |
|---|
