[알고리즘] ArrayDeque

특징: stack으로 사용하고자 할때 Stack보다 빠르고 queue로 사용하고자 할때 LinkedList보다 빠르다. remove나 contains를 제외하고는 모든 오퍼레이션을 상수 시간에 할 수 있다.

 

 

size(): O(1)

isEmpty(): O(1)

getFirst(): O(1)

getLast(): O(1)

set(): O(n)

iterator(): O(1)

listIterator(): O(1)

add(E e): O(1) (amortized time)

add(int index, E e): O( index 오른쪽 배열 크기) (amortized time)

remove(): O(n)

removeFirst(): O(1)

removeLast(): O(1)

peek(): O(1)

element(): O(1)

peekFirst(): O(1)
peekLast(): O(1)

pollFirst(): O(1)

pollLast(): O(1)

pop(): O(1)
push(): O(1)

contains(): O(n)

addAll(E e): O(m) (넣는 배열 크기)

addAll(int index, E e): O(n + m)

clear(): O(n)