LinkedListDeque 학습

 

 

 

 

 

 

 

 

 

 

 

 

이전 포스팅 ArrayDeque의 번외 편입니다.

 

queue는 단방향의 흐름을 가지지만 Deque는 양방향의 흐름을 가집니다.

Linked list를 사용하여 구현하며 단방향보다는 양방향이 좀 더 어울리므로 doubly linked list를 사용합니다.

head와 tail을 가지며 두 변수를 참조하여 양쪽에서 enque, deque연산을 수행합니다.

Deque 자체의 설명은 이전 포스팅 ArrayDeque편을 참고하시길 바랍니다.

 

이전 Deque구현에서는 배열을 이용하여 구현하였으며 이번 편은 Linked List 즉 Node를 통해서

Deque의 opration을 구현해 보겠습니다.

 

 

 

 

 

 

 

 

 

Node

연결 리스트를 사용할 때 꼭 필요한 Node입니다.

doubly linked list을 사용하여 구현하므로 next와 prev 모두 사용합니다.

 

 

 

 

 

 

 

 

 

LinkedListDeque

Deque의 양방향 삭제, 삽입 연산을 효율적으로 하기 위해 head와 tail을 정의합니다.

이름처럼 head는 list의 머리, tail은 꼬리를 참조합니다.

 

 

 

 

 

 

 

 

생성자

head와 tail을 null로 초기화합니다.

 

 

 

 

 

 

 

 

 

offerFrist

Deque의 머리에 데이터를 넣어줍니다.

head의 prev를 새로운 head를 넣어주는 것만 주의해 주면 됩니다.

새로운 노드의 next에 head를 넣어줄 때는 head가 null인 것은 신경 쓰지 않아도 됩니다.

다음 노드가 존재한다면 다음노드를 넣을 것이고

없다면 null을 넣어줍니다.

 

 

 

 

 

 

 

 

offerLast

리스트의 끝에 넣어주며 size가 0일 때는 offerFirst를 사용합니다.

여러 api가 같은 케이스를 동일하게 지원해 주면 관리하기가 힘듭니다.

 

메서드 처음에 size가 0인 예외케이스를 처리하였으니 고려해야 할 점이 없습니다.

마지막 부분에 넣을 때 고려 할 것은 "size == 0 or size >= 1"입니다.

1개라도 노드가 존재한다면 그 이상은 동일한 로직이 들어갑니다.

 

너무 많은 데이터가 들어가면 메모리에 공간이 부족할 수도 있지만 넘어가겠습니다.

 

 

 

 

 

 

pollFirst

이제부터 Deque 연산입니다.

우선 size 0은 예외처리를 해주며 연산을 쉽게 할 수 있게 head의 nextNode를 잠시 빼줍니다.

이제부터 size 최소 1개가 보장되니 무조건 head의 data, head의 next를 null로 초기화합니다.

 

nextNode를 이제 head에 넣어줍니다.

size == 1 or size > 1은 고려 안 해도 됩니다. size가 1 이상이면 Node가 들어가고 1이면은 null이 들어갑니다.

head 처리도 완료되었습니다.

 

size가 2개 이상이면 nextNode의 prev를 제거해 줍니다.

 

마지막으로 결과가 emptyList면 tail을 null로 초기화합니다.

tail 처리도 완료되었습니다.

 

 

 

 

 

 

pollLast

반대편 poll입니다.

size 0은 미리 처리해 줍니다. 이제 최소 1개의 노드가 있다는 것이 보장됩니다.

tail의 존재를 없애버리기 때문에 tail의 prev node는 미리 따로 보관합니다.

간단하게 tail의 인스턴스 변수는 모두 null로 초기화합니다.

 

따로 보관된 prev node가 있다면 prev의 next를 null로 초기화합니다.

 

이제 tail에 prev를 할당합니다. prev가 null이라면 queue의 size가 0개를 뜻합니다.

null이 아니라면 삭제 이후 최소 1개는 있다는 것을 뜻합니다.

null, 노드 2가지의 경우 모두 정상적인 케이스입니다.

 

마지막으로 queue의 size가 0이라면 head도 null로 초기화합니다.

 

 

 

 

 

peek

offer, poll와 다르게 head와 tail의 데이터를 확인만 합니다.

size가 0이 아니라면 data, 0이라면 null을 반환합니다.

 

 

 

 

 

 

 

 

size & isEmpty

설명은 생략합니다.

 

 

 

 

 

 

clear

deque의 list를 순회하면서 모든 데이터를 날려줍니다.

간단하게 아래 흐름을 반복합니다.

 

1. current가 존재하는가?

2. current next 임시보관

3. current안의 모든 인스턴스 변수 null로 초기화

3. current에 임시보관 노드 할당

 

마지막으로 size, head, tail 정리를 합니다.

 

 

 

 

 

 

 

contains

clear()와 비슷한 알고리즘입니다.

계속 current null 체크를 해주며 순회합니다.

eqauls()를 사용하여 true가 나오면 true를 반환하고 종료하며

끝까지 true를 반환하지 못한다면 false를 반환합니다.

 

 

 

 

 

 

 

 

toArray

Deque의 모든 요소를 배열에 담아 반환합니다.

얕은 복사라서 사용에 주의가 필요합니다.