queue는 왜 LinkedList로 구현하는가

queue를 구성할 수 있는 방법은 여러 가지가 있다. 일반 ArrayList로도 선형 큐, 원형 큐가 가능하다. 그러나 예제를 보면 십중팔구 LinkedList로 구현한다.
그렇다면 ArrayList 방법과 LinkedList 방법의 차이가 있다는 뜻인데, 어떠한 점에서 LinkedList가 우수하기에 많이 쓰이는 걸까?

queue란

선입선출, 먼저 들어온 데이터가 먼저 빠져나가는 구조다.
마치 줄을 서서 놀이공원을 즐기는 것과 같다.
먼저 줄을 선 사람이, 놀이기구를 먼저 맛본다.

ArrayList로 구현

상당히 쉽다. 배열의 맨 앞을 가르키는 head, 맨 뒤를 가르키는 rear를 선언하고 값이 추가될 경우 ++rear의 위치에 넣는다.

값이 빠질 경우 역시 head++을 반환하면 된다.

장점

구현과 이해가 매우 쉽다.

단점

데이터가 계속해서 추가, 삭제되는 형태라 해보자. 그럼 ArrayList는 계속해서 늘어날 거고, 메모리를 그만큼 잡아먹는다.
이러한 상태를 벗어나기 위해 원형 큐나 이동 큐 등등이 나왔으나 근본적인 해결은 쉽지 않았다.

LinkedList로 구현

이 역시 간단하다. head와 rear를 선언하고, 값 추가 시 새 List를 만들어 값을 추가, 기존 rear의 next에 새 List ref를 선언하고 rear를 새 List로 옮긴다.

값이 빠질 경우 head 값을 반환하고 next가 위치하는 곳으로 옮긴다.
메모리를 최적화할 경우, 삭제하는 과정을 포함한다.

그림 설명이 뭔가 다른 것 같지만 다시 만들기 귀찮아서 그런 거니까 느낌만 보세요. 워낙 예전에 만든 자료라..

장점

맨 앞쪽에 값을 추가하는 방법도 구현할 수 있고(deque를 쓰자), 데이터가 계속해서 추가, 삭제되는 형태일 때 메모리를 아낄 수 있다.

단점

직접 구현하는 경우 코드짜기 귀찮다.

정리

..아무튼 이런 형태로 인해 LinkedList가 월등히 많이 쓰인다. 자바로 알고리즘 풀다가 문득 예전에 공부한 게 생각나서 적어봤다.
자료구조 다시 공부할 겸 종종 적어야겠다.

외전) queue 명령어 정리

값 추가

add

큐가 꽉 차서 값 추가에 실패할 경우 IllegalStateException 에러

offer

큐가 꽉 차서 값 추가에 실패할 경우 false 반환

값 반환

remove

큐가 비어있어서 삭제하지 못 할 경우 NoSuchElementException 에러

poll

큐가 비어있어서 삭제하지 못 할 경우 null 반환

head값 확인

element

큐가 비어있는 경우 NoSuchElementException 에러

peek

큐가 비어있는 경우 null 반환