Deque구현체 LinkedList VS ArrayDeque 비교

💬서론

java에서 제공하는 java.util.Stack 클래스는 디자인이 잘못되어 사용을 지양하고 있습니다.

이유를 짧게 정리하자면 자바의 Stack 클래스는 상위 클래스로 Vector를 상속받는데, 여기서 문제가 발생합니다.

 

- Synchronized로 인한 성능 저하 발생

Vector는 모든 메서드에 synchronized를 사용하기 때문에 간단하게 조회만 하는 경우에도 동기화로 인해 성능 저하가 발생합니다. Stack에서 제공하는 메서드 역시 synchronized를 사용해서 동기화 처리하는데, 내부적으로 Vector가 제공하는 메서드를 사용함으로써 이중으로 동기화 처리가 발생하여 성능 저하가 발생합니다.

 

- 후입 선출 구조 위반

스택은 후입선출 구조이기 때문에 해당 구조의 규칙을 위반하는 접근은 불가능해야 합니다. 하지만 Stack은 Vector가 제공하는 add(int index, E element), removeElementAt(int indx)메서드를 통해 특정 인덱스에 데이터를 추가하거나 제거할 수 있습니다.

 

이러한 이유로 자바 공식 API에조차 더 안전하고 일관된 Deque 인터페이스와 그 구현체들을 사용하라고 명시되어있습니다. (이러한 Stack 구조는 자바의 하위 호환성을 위해서 상속관계를 계속 유지하고 있습니다.) 

자세한 내용이 궁금하신분은 다음글을 참고해보시면 좋을것 같습니다.

http:// https://velog.io/@jhl221123/%EC%9E%90%EB%B0%94%EC%9D%98-Stack%EC%9D%80-%EC%99%9C-%EC%82%AC%EC%9A%A9%ED%95%98%EC%A7%80-%EC%95%8A%EB%8A%94-%EA%B1%B8%EA%B9%8C

이번글에서는 그렇다면 Stack을 필요로 할때 Deque인터페이스의 구현체로 LinkedList와 ArrayDeque를 비교하기 위해 작성하였습니다.

 

---

 

📜스포❗

결론이 궁금하신분들을 위해 먼저 말씀드리자면 Stack, Deque로 사용하고자 한다면 ArrayDeque가 효율적입니다. 대부분의 경우에도 ArrayDeque가 효율적입니다.

 

LinkedList란?

LinkedList는 이중 연결 리스트 구조를 기반으로 구현된 클래스입니다. 각 노드가 데이터와 함께 이전 및 다음 노드의 참조를 포함합니다.

주요 특징

• 동적 크기: 데이터 크기에 따라 자동으로 크기가 조정됩니다.
• 삽입/삭제 성능: 양 끝에서의 삽입과 삭제뿐 아니라 중간에 요소를 추가하거나 삭제하는 경우에도 매우 빠릅니다(시간복잡도: O(1)).
• 접근 성능: 특정 인덱스에 접근하려면 노드를 순차적으로 탐색해야 하므로 느립니다(시간복잡도: O(n)).
• 메모리 소비: 각 노드가 다음/이전 노드를 가리키는 추가적인 참조(포인터)를 저장해야 하므로 메모리 사용량이 더 많습니다.

이러한 특징으로 인해 중간 위치에 삽입과 삭제가 빈번히 발생하거나 적합한 경우, 리스트의 크기가 유동적이고 특정 인덱스 접근이 필요하지 않은 경우에 유리합니다.

---

ArrayDeque

ArrayDeque는 동적 배열 구조를 기반으로 구현된 클래스입니다. 배열 크기를 초과하면 내부적으로 크기를 늘려 데이터를 재배열합니다.

ArrayDeque의 주요 특징

• 동적 크기: 데이터 크기가 현재 배열 크기를 초과하면 내부 배열 크기를 2배로 증가시킵니다. 반대로 데이터가 너무 적게 사용될 경우 크기를 줄일 수도 있습니다.
• 삽입/삭제 성능: 양 끝에서의 삽입과 삭제가 평균적으로 빠릅니다(시간복잡도: 평균 O(1), 크기 초과 시 O(n)).
• 랜덤 접근 성능: 배열 기반이므로 순차적 접근이 매우 빠릅니다(시간복잡도: O(1)).
• 메모리 소비: 연결 리스트보다 효율적입니다(추가적인 참조가 없기 때문).

이러한 특징으로 메모리 사용량을 줄이고 싶은 경우 중간 위치에 삽입/삭제가 빈번하지 않는경우, 데이터 크기의 유동성이 크지 않은 경우에 유리합니다.

 

---

그렇다면 Stack으로 사용 시 ArrayDeque가 더 적합한 이유는?

Stack은 중간 삽입/삭제가 없으므로 LinkedList의 추가적인 이점(중간 삽입/삭제)은 활용되지 않습니다. 하지만 메모리 효율성 측면에서 LinkedList는 각 이전/다음 노드의 참조를 저장하므로 메모리 사용량이 많습니다. 그러므로 메모리 효율성 측면에서 ArrayDeque가 이점이 있습니다.

또한 ArrayDeque는 구현이 배열로 되어있기 때문에 객체의 구성요소들이 서로 밀접한 메모리 위치에 있습니다. 하지만 LinkedList는 각각의 요소가 객체로 따로 관리되기 때문에 밀접한 위치에 있지 않을 수 있습니다. 그래서 맨 뒤의 값을 꺼내면서 탐색하는 Stack의 특징대로 탐색을 하면 배열 기반의 ArrayDeque가 연결 리스트기반의 LinkedList보다 더 빠릅니다! 

 

여기서 저는 한가지 걱정이 들었습니다.

 

ArrayDeque는 배열 기반 구조이기 때문에 데이터 크기가 현재 배열 크기를 초과하면 다음과 같은 과정이 발생합니다:

1. 새 배열 생성: 기존 배열 크기의 2배 크기를 가진 새로운 배열을 생성합니다.
2. 데이터 복사: 기존 배열에 저장된 데이터를 새로운 배열로 복사합니다. 이 작업은 O(n)의 시간복잡도를 가집니다.
3. 참조 변경: 내부적으로 새로운 배열을 사용하도록 참조를 변경합니다.

데이터가 많아지고 배열 확장이 빈번하게 발생할 경우, 복사 작업이 성능 저하를 유발할 수 있습니다. 특히 다음과 같은 상황에서 문제가 더욱 커질 것입니다.

• 초기에 매우 작은 크기의 배열로 시작하여 잦은 크기 확장이 필요한 경우.
• 삽입 작업이 빈번히 발생하며, 배열의 크기를 자주 초과하는 경우.

하지만 확장 작업의 빈도는 낮기때문에 대부분의 코딩테스트/실제 사용 사례에서는 크게 문제되지 않는다고 판단하였습니다. ArrayDeque는 배열 크기를 2배씩 증가시키므로, 데이터 크기가 기하급수적으로 증가할 때만 확장이 필요합니다. 예를 들어, 배열의 초기 크기가 8이라고 가정하면, 8 → 16 → 32 → 64와 같이 크기가 증가합니다. 즉, 데이터 삽입이 많더라도 확장 작업은 점점 드물게 발생합니다.

 

---

실제 성능 테스트

이러한 생각을 검증하기 위해 성능 테스트를 진행하였습니다.

1억개의 데이터를 삽입하고 다시 1억개의 데이터를 삭제하는 과정입니다.

package barkingDog.stack;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

public class StackTest {
    static int N = 100_000_000;
    public static void main(String[] args) throws Exception {
        long start = System.currentTimeMillis();
        Deque<Integer> stack = new ArrayDeque<>();
//        Deque<Integer> deque = new LinkedList<>();

        int count = 0;

        while(count++ <N){
            stack.addLast(1);
        }

        while(count++ <N){
            stack.pollLast();
        }

        long end = System.currentTimeMillis();

        System.out.println("===== ArrayDeque =====");
//      System.out.println("===== LinkedList =====");
        System.out.println("걸린 시간 : " + (end - start)+"ms");
    }
}

 

먼저 ArrayDeque를 5번 실행한 결과 평균 2501ms가 소요되었습니다.

 

 

다음으로 LinkedList로 5번 실행한 결과 평균 10114ms가 소요되었습니다. 

 

약 4배정도의 시간이 차이난다는것을 알수있었습니다.

 

결론

결론적으로 Stack으로서 ArrayDeque가 LinkedList보다 효율적이라는 것을 알게되었습니다. 이글을 읽으시는 분들 모두 알고리즘 문제풀이 하실 때  Deque의 구현체로 ArrayDeque를 사용하셔서 시간초과 문제가 발생하시지 않으셨으면 좋겠습니다! 😊

 

 

참고

https://khnemu.tistory.com/10

https://kmularise.tistory.com/entry/javautilStack-%EC%8B%A4%EC%A0%9C%EB%A1%9C%EB%8A%94-%EC%9E%98-%EC%82%AC%EC%9A%A9%ED%95%98%EC%A7%80-%EC%95%8A%EB%8A%94-%EC%9D%B4%EC%9C%A0%EB%8A%94