Java Reference
In-Depth Information
Data
Structure
Access
Comments
O
( )
Stack
Most recent only,
pop
,
Very very fast
O
( )
Queue
Least recent only,
dequeue
,
Very very fast
O
(
N
)
List
Any item
O
(log
N
)
TreeSet
Any item by name or rank,
Average case easy to do; worst case requires effort
O
( )
HashSet
Any item by name,
Average case
O
( )
O
(log
N
)
O
( )
O
(log
N
)
Priority
Queue
findMin
,
,
insert
is
on average,
worst case
deleteMin
,
figure 6.43
A summary of some data structures
Arrays
Contains a set of static methods that operate on arrays. (246)
binary heap
Implements the priority queue in logarithmic time per operation
using an array. (275)
binary search tree
A data structure that supports insertion, removal, and
searching. We can also use it to access the
K
th smallest item. The cost is
logarithmic average-case time for a simple implementation and logarith-
mic worst-case time for a more careful implementation. (264)
Collection
An interface that represents a group of objects, known as its ele-
ments. (237)
Collections
A class that contains a set of static methods that operate on
Collection
objects. (242)
data structure
A representation of data and the operations allowed on that
data, permitting component reuse. (230)
factory method
A method that creates new concrete instances but returns them
using a reference to an abstract class. (235)
hashCode
A method used by
HashSet
that must be overridden for objects if the
object's
equals
method is overridden. (268)
HashMap
The Collections API implementation of a
Map
with unordered keys. (268)
HashSet
The Collections API implementation of an (unordered)
Set
. (264)
iterator
An object that allows access to elements in a container. (240)
Search WWH ::
Custom Search