Java의 큐 구현

Question

큐의 구현을 위해 링크 된 목록을 arraylist보다 사용하는 것이 더 좋습니까? dequeue하면 좋아하는 목록 구현의 경우 과부하가 적습니까?

Answer 1

LinkedList 시작 부분에서 요소를 큐 해제하는 데 걸리는 시간이 ArrayList보다 적습니다.

이것은 ArrayList가 배열을 기반으로하고 있기 때문에 첫 번째 요소가 제거되면 대기열을 제외한 모든 요소는 한 위치 왼쪽으로 시프트되어야합니다. ArrayList에있는 요소의 수가 많을수록 더 길어집니다.

LinkedList의 경우 목록의 크기와 상관없이 첫 번째 요소를 대기열에서 제외하기 위해 업데이트해야하는 일정한 개수의 참조 만 있습니다.

물론 ArrayList의 끝에서 요소를 큐에서 제거 할 수 있으며 일정 시간 (대부분의 경우)이 소요되지만 새 요소를 추가하는 것부터 시작하여 모든 요소를 ​​한 위치로 이동해야합니다. 권리.

Answer 2

Java에서 이미 LikedList 대기열 구현이 있습니다. 나는 코드를 분석하지 않았지만, LinkedList가 ArrayList보다 빠르면 엔트리를 큐에서 빼낼 수있을 것이라고 추측 할 수 있습니다.