LinkedList로 Deque를 구현할 때 알아야 할 것

Deque는 양쪽 끝에서 삽입과 삭제가 가능한 자료구조다. 이름 그대로 double-ended queue이며, 스택과 큐의 성질을 모두 표현할 수 있다.

Deque가 필요한 이유

한쪽 끝만 쓰는 큐나 스택으로는 표현이 애매한 경우가 있다.

• 앞뒤에서 모두 원소를 넣고 빼야 할 때
• 슬라이딩 윈도우처럼 양 끝 갱신이 필요한 경우
• BFS 변형이나 캐시 시뮬레이션처럼 양방향 조작이 필요한 경우

이럴 때 Deque가 자연스럽다.

LinkedList 기반 구현이 쉬운 이유

양 끝 삽입과 삭제가 빠르려면 앞과 뒤에 대한 접근이 모두 쉬워야 한다. 이중 연결 리스트 구조를 사용하면:

• 앞에서 삽입/삭제 O(1)
• 뒤에서 삽입/삭제 O(1)

형태로 구현하기 좋다.

반대로 배열 기반 Deque는 원형 버퍼 같은 별도 관리가 필요해진다.

핵심 연산

Deque는 보통 다음 연산을 가진다.

• addFirst
• addLast
• removeFirst
• removeLast
• peekFirst
• peekLast

이 이름만 보면 단순하지만, 구현에서는 비어 있는 경우와 원소가 1개인 경우를 특히 조심해야 한다.

구현에서 주의할 점

head와 tail 갱신

앞과 뒤 포인터를 모두 유지한다면 삽입/삭제 후 두 포인터가 어떻게 바뀌는지 항상 같이 봐야 한다. 특히 마지막 원소를 제거했을 때는 head와 tail이 모두 null로 정리되어야 한다.

노드 연결 끊기

삭제된 노드의 참조를 남겨두면 가비지 컬렉션 관점에서는 큰 문제는 아니더라도, 디버깅이나 구현 명확성 측면에서 좋지 않다. 제거 후 이전/다음 링크를 정리하는 편이 안전하다.

크기 관리

자료구조 기본 구현에서는 size를 별도 필드로 두는 경우가 많다. 이 값은 삽입과 삭제 지점에서 정확히 갱신되어야 한다.

왜 Java 표준 라이브러리에서는 ArrayDeque를 많이 쓰나

직접 구현을 공부할 때는 LinkedList가 이해하기 쉽지만, 실제 Java 표준 라이브러리 사용에서는 ArrayDeque가 더 권장되는 경우가 많다.

이유는 다음과 같다.

• 객체 노드 오버헤드가 적다
• 캐시 친화적이다
• 일반적인 스택/큐 용도에서 더 빠른 경우가 많다

즉, 자료구조 학습용 구현과 실무 기본 선택은 다를 수 있다.

정리

Deque는 양 끝 삽입/삭제가 가능한 자료구조이고, LinkedList는 이를 구현하기 쉬운 구조다.

다만 실무에서는 “직접 구현할 수 있는가”보다:

• 어떤 연산이 필요한가
• 배열 기반이 더 적합한가
• 표준 라이브러리로 충분한가

를 먼저 판단하는 편이 낫다.