안녕하세요~
최근 코딩테스트 공부를 다시 시작하며 Stack에 대해 공부하고 있던 도중 Java 공식문서에서 스택이 필요할 때 ArrayDeque 를 구현체로 한 Deque 인터페이스를 사용할 것을 권고하고 있는 내용을 확인했습니다.
이에 대해 자세히 알아보겠습니다.
Java와 Kotlin
Java와 Kotlin은 상호호환성을 가집니다. 때문에 Java에서 제공하는 다양한 클래스, 예를 들어 ArrayList, HashMap, Stack 같은 자료구조를 Kotlin에서도 그대로 사용할 수 있습니다.
Java와 Kotlin이 상호호환성을 가지는 근거로 Kotlin의 컬렉션 프레임워크나 .javaClass를 통해 확인할 수 있습니다.
public actual interface MutableList<E> : List<E>, MutableCollection<E>
@SinceKotlin("1.1")
@kotlin.internal.InlineOnly
public inline fun <T> mutableListOf(): MutableList<T> = ArrayList()
@SinceKotlin("1.1") public actual typealias ArrayList<E> = java.util.ArrayList<E>흔히 사용하는 MutableList 를 예시로 들어보겠습니다.
인터페이스는 Kotlin에서 만들어두고 실제 자료형은 java.util.ArrayList인 것을 확인할 수 있습니다.
즉, interface만 Kotlin에 만들어두고 실제 자료형은 Java의 자료형을 사용하는 방식
이거.. 내부 구현체를 확인하려면 Java코드를 까봐야 하네...? 왜 이런 방법을 선택했을가요?
- 자바의 표쥰 컬렉션을 이용하면 호환성이 높습니다.
- 자바와 코틀린 간에 호출이 일어날 때 서로 변환할 필요가 없습니다.
앞서 Java와 Kotlin은 상호호환성을 가진다고 했습니다.
범용적인 자바 표준을 이용해 호환성을 높이고, 자바와 코틀린 간에 서로 문제없이 호출하는 상호운용성을 위해 코틀린이 택한 방식입니다.
Stack
그럼 왜 Stack을 사용하지 말라는 걸까요?
Stack 소스 코드를 통해 확인할 수 있습니다.
public class Stack<E> extends Vector<E> {
public Stack() {
}
public E push(E item) {
addElement(item);
return item;
}
public synchronized E pop() {
...
removeElementAt(len - 1);
return obj;
}
public synchronized E peek() {
...
return elementAt(len - 1);
}
public synchronized int search(Object o) {
...
}
}여기서 확인할 수 있는 점으로
- Vector를 상속받고 있습니다.
- pop, peek, search에 synchronized를 사용하고 있습니다.
그럼 Vector의 코드를 확인해보겠습니다.
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
public synchronized void copyInto(Object[] anArray) {
System.arraycopy(elementData, 0, anArray, 0, elementCount);
}
public synchronized int capacity() {
return elementData.length;
}
...
public synchronized void addElement(E obj) {
modCount++;
add(obj, elementData, elementCount);
}
}Vector의 함수들 또한 앞에 synchronized 키워드가 사용되었습니다.
그럼 synchronized는 뭐하는 녀석일까요?
synchronized
synchronized는 자바에서 멀티스레드 환경에서 동시 접근을 막기 위한 동기화 키워드입니다.
즉, 메서드나 블록에 이 키워드가 붙으면, 한 번에 오직 한 번에 하나의 스레드만 접근할 수 있게 락 (Lock)을 겁니다.
해당 메서드를 여러 스레드가 동시에 호출하려고 할 때 하나의 차례로만 실행됩니다.
왜 synchronized를 붙였을가요?
Stack은 1995년에 설계된 Java 1.0의 자료구조 입니다.
당시 멀티스레드를 안전하게 다룰 방법이 제한적이였고, 당시 컴퓨터는 대부분 싱글코어 CPU였기 때문에 성능 저하가 치명적으로 드러나지 않았을 거라고 생각합니다.
정리하자면
- 락을 걸기 때문에, 오버헤드가 발생합니다.
- 스레드 충돌이 없는데도 락을 잡고 해제함 -> 낭비로 이어집니다.
- 코딩 테스트에서는 대부분 단일 스레드로 작동하기 때문에 락은 불필요한 비용입니다.
ArrayDeque
ArrayDeque는 Stack의 문제를 해결했을가요?
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable
{
private int newCapacity(int needed, int jump) {...}
public ArrayDeque() {
// 초기 용량, 후 grow 함수로 더블링
elements = new Object[16 + 1];
}
static final <E> E elementAt(Object[] es, int i) {...}
public void addFirst(E e) {...}
public void addLast(E e) {...}
...
public E removeLast() {...}
public void push(E e) {
addFirst(e);
}
public E peek() {
return peekFirst();
}
...
}ArrayDeque는 Deque 인터페이스를 구현한 클래스입니다.
Deque란?
"Double Ended Queue"의 줄임말로 양쪽 끝에서 삽입과 삭제가 가능한 큐입니다.
ArrayDeque는 Deque의 모든 메서드를 배열 기반으로 구현합니다.
public interface Deque<E> extends Queue<E>, SequencedCollection<E> {
void addFirst(E e);
void addLast(E e);
E removeFirst();
E removeLast();
void push(E e);
E pop();
...
}ArrayDeque는 순환 배열 기반으로 구현된 양방향 큐(Deque)입니다.
양쪽에서 삽입 / 삭제가 가능하므로 한쪽 끝에서 삽입하고 삭제를 하면 스택 처럼 사용할 수 있습니다.
즉, 스택, 큐 모두로 유연하게 사용 가능
Stack과 달리 synchronized를 사용하지도 않습니다.
때문에 락을 잡지 않고 불필요한 성능 손실 또한 없습니다.
때문에 Stack을 사용해야 한다면 ArrayDeque가 가장 추천되는 자료구조 입니다.
그럼 LinkedList는?
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
}LinkedList 또한 Deque 인터페이스를 구현하고 있고 Stack과 Queue 용도로 사용할 수 있습니다.
기능적으로 유사하지만, 내부 구조와 성능 측면에서 차이가 있습니다.
ArrayDeque는 배열 기반 / LinkedList는 이중 연결 리스트 기반
ArrayDeque는 배열 기반이기 때문에 데이터가 메모리에 연속으로 저장됩니다.
또한 배열 확장(더블링) 비용보다 LinkedList의 새 노드를 새로 생성하는 비용이 더 많이 들어가게 됩니다.
데이터 접근 또한 배열은 O(1)만에 가능하지만 LinkedList는 각 노드를 순회해야 합니다.
때문에 LinkedList 보다 ArrayDeque가 선호된다고 생각합니다.
