[JAVA] Deque + 왜 LinkedList보다 ArrayDeque로 구현하는 것이 더 좋을까?

안녕하세요.

오늘은 자바의 Deque 인터페이스에 대해 설명하겠습니다.

그리고 왜 ArrayDeque로 Queue/Stack/Deque를 구현하는 것이 LinkedList 구현보다 더 유리한지 알아보겠습니다.

 

[ 목차 ]

 

 

Deque란?

FIFO와 LIFO 두 방식으로 데이터 처리가 가능한 자료구조입니다.

양방향 삽입 및 삭제가 가능합니다.

 

Queue 인터페이스를 확장한 인터페이스입니다.

ArrayDeque, LinkedList, PriorityDeque로 구현할 수 있습니다.

자바의 컬렉션 프레임워크에 속합니다.

 

자바의 컬렉션 프레임워크란?

컬렉션 : 다수의 데이터

프레임워크 : 표준화된 프로그래밍 방식

-> 데이터 그룹을 저장하는 클래스들을 표준화한 설계 입니다.

 

컬렉션 프레임워크 사용시, 객체지향적이고 재사용성이 높은 코드를 작성할 수 있습니다.

컬렉션 프레임워크의 주요 인터페이스로는 List/Set/Map이 있습니다.

 

 

 

 

Deque를 구현할 수 있는 클래스들

1. ArrayDeque : 배열을 기반으로 합니다. 성능이 우수하여 가장 자주 사용됩니다.

2. LinkedList : 연결리스트를 기반으로 합니다. 빠른 삽입과 삭제를 제공합니다.

3. PriorityDeque : 표준 라이브러리에는 없는 커스텀 구현체입니다. 우선순위를 기반으로 합니다.

 

 

 

왜 ArrayDeque가 LinkedList보다 더 유리할까

코딩테스트를 위한 코드를 짠다면, Queue와 Stack은 ArrayDeque로 구현하는 것이 압도적으로 유리합니다.

배열 기반이라 전/후 노드 노드 참조가 필요 없어 메모리 사용이 적기 때문입니다.

 

더 적은 메모리를 사용한다.

ArrayDeque는 배열 기반 자료구조 입니다.

따라서 연속적인 메모리 공간에 데이터를 저장하므로, 추가적인 참조 비용(이전 노드, 다음 노드)이 필요하지 않습니다.

 

하지만 LinkedList는 이중 연결 리스트 기반 자료구조입니다.

따라서 각 요소는 담 노드와 이전 노드에 대한 참조를 저장하기 위해 추가적인 메모리가 필요합니다.

 

더 높은 효율을 갖는다.

LinkedList로 구현하게 된다면, 각 노드는 힙 메모리의 흩어진 위치에 저장된다.

메모리 할당이 분산되어 있기 때문에 캐시 효율이 떨어지게 된다.

 

그럼에도 LinkedList가 필요한 경우

1. 중간에 빈번한 삽입/삭제가 발생한다면 LinkedList가 더 유리합니다. (= 중간 연결 데이터 자주 조작해야할 때)

2. 데이터의 양이 매우 크고 배열의 확장이 비효율적이라면 LinkedList가 더 유리합니다.

 

 

 

 

 

예외를 발생시키지 않는 건(안전한 조회) 오 폴 픽 !

 

Deque의 삽입 메서드 (offer / add)

1. addFirst : 덱의 맨 앞에 요소를 삽입 합니다. 실패 시 IllegalStateException을 발생시킵니다.

2. addLast : 덱의 맨 뒤에 요소를 삽입 합니다 . 실패 시 IllegalStateException을 발생시킵니다.

3. offerFirst(E e) : 덱의 맨 앞에 요소를 삽입 합니다 . 성공 시 true, 실패 시 false 반환합니다.

4. offerLast(E e) : 덱의 맨 뒤에 요소를 삽입 합니다 . 성공 시 true, 실패 시 false 반환합니다.

 

 

 

Deque의 삭제 메서드 (poll / remove)

pollFirst() / pollLast() / removeFirst() / removeLast() 가 있다.

 

 

 

Deque의 요소 반환 메서드 (peek / element)

peekFirst() / peekLast() / elementFirst() / elementLast() 가 있다.

 

 

 

 

 

 

 

기억하세요...

예외를 발생시키지 않는 건(안전한 조회) 오 폴 픽 ! (offer poll peek)