Ch. 19 Big Oh Chart - Worst-case Big Oh time efficiencies of various methods
method
fixed array
ArrayList*
singly linked list
w/ no trailer node
java.util.LinkedList
(implemented as a doubly linked list
w/ header & trailer nodes)
stack
queue
java.util.List interface methods
add(Object)
O(n)
O(n)
O(1)
size
length is O(1)
O(1)
O(n)
O(n)
get
[ ] is O(1)
O(1)
O(n)
O(n)
set
[ ] is O(1)
O(1)
O(n)
O(n)
java.util.ArrayList methods
add(int, Object)
O(n)
remove
O(n)
LinkedList methods
addFirst
O(1)
O(1)
addLast
O(n)
O(1)
getFirst
O(1)
O(1)
getLast
O(n)
O(1)
removeFirst
O(1)
O(1)
removeLast
O(n)
O(1)
ap.Stack & ap.Queue interface methods
isEmpty
O(1)
O(1)
push
O(1)
pop
O(1)
peekTop
O(1)
enqueue
O(1)
dequeue
O(1)
peekFront
O(1)

* see the AP Exam Java Subset ArrayList for an explanation of the ArrayList methods. Since ArrayList is implemented as a "resizable" fixed array, it has some surprising Big Oh evaulations