Circular Deque의 두 가지 구현

❒ Description

---

[LeetCode#641] Design Circular Deque에서 Array와 Doubly-Linked list를 통해서 Circular-DQ를 

구현해봤다. 하지만 Doubly-Linked list를 통한 구현은 원형 큐의 이점을 잘 살리지 못한다고 했다.

여기서는 왜 이점을 살리지 못하는지 정리해본다.

 

 

 

❒ 동작원리

---

1. insertFront

Front 앞에 새로운 데이터를 삽입한다.

Front가 현재 0번 째 index를 가리키고 있다면, Front는 마지막 index를 가리키도록 변경된다.

 

2. insertLast

Rear 뒤에 새로운 데이터를 삽입한다.

Rear가 현재 마지막 index를 가리키고 있다면, Rear는 첫 번째 index를 가리키도록 변경된다.

 

 

 

❒ Why?

---

1. Memory 낭비

Doubly-Linked list를 통한 구현은 prev, next 라는 필드를 가지고 있는데 각각 다음 또는 이전 노드를 가리킨다.

하지만 Array를 통한 구현은 이런 필드를 가지고 있지 않기 때문에 상대적으로 메모리 효율이 좋다.

 

2. 연산의 복잡성 증가

Doubly-Linked list를 통한 구현은 next와 prev 포인터를 갱신하는 작업은 여전히 필요하다.
삽입 및 삭제 연산의 시간 복잡도는 O(1)이지만, 원형 구조를 유지하기 위한 추가적인 포인터 갱신 작업이 필요하다.

하지만 Array를 통한 구현은 인덱스만 조작하여 앞뒤로 삽입과 삭제를 쉽게 수행할 수 있습니다.
연산이 단순하며, 인덱스가 배열 크기를 초과할 때 모듈(나머지)로 연산을 사용하여 순환 구조를 쉽게 유지할 수 있다.

 

3. 순환 구조의 자연스러운 처리

Doubly-Linked list를 통한 구현은 리스트의 양 끝을 연결하여 원형 구조를 만들 수 있지만, 리스트의 순환성을 활용하려면
추가적인 논리가 필요하다. 예를 들어, next가 null일 때 head로 돌아가는 논리를 구현해야 한다.

하지만 Array를 통한 구현은 인덱스를 이용해 자연스럽게 순환 구조를 유지할 수 있다.
예를 들어, front나 rear 인덱스가 배열의 끝에 도달하면 0으로 다시 설정하여 순환을 쉽게 관리할 수 있다.