Data Structures Summary

last updated 4/30/07

Collections

The following are a list of collections we considered in this course

Collection Structure	Linear (orderable)	Access	Underlying Implementation Structures	Access Points	Restrictions
Arrays	linear	random	static bounded array	n	none
Stacks	linear	sequential	bounded array or linked list	1	none
Queues	linear	sequential	bounded circular array or linked list	2	none
Lists	linear	sequential	linked list (doubly, circular optional)	n	none
Binary Search Tree	hierarchical	by value	binary search tree	n	unique value
Hash Table	non-linear	by value	hash table (array)	n	unique value
Sets	non-linear	by value	hash table or bst	n	unique values
Bags	non-linear	by value	hash table or bst	n	none
Maps	non-linear	by key or value	hash table or bst	n	key is unique

These are the basic operations applied to a collection. Some may have special name depending on the structure.

type operationName(param)	aliases/ similar operations	comments
boolean add(Object item)	push, enqueue, insert, put	return value reports success in adding the item to the collection
boolean contains (Object item)	search, get	this represents the search operation
boolean remove (Object item)	pop, dequeue, delete	return value reports success in removing the item from the collection
Iterator iterator() boolean Iterator.hasNext() Object Iterator.next() void reset()		The iterator steps through the collection in a sequential order
void clear()		O(1) but garbage collection costs O(n)
int size()		O(1)
boolean isEmpty()		O(1)
String toString()		O(n) this represents the traverse operation

Place the mouse over the red ball to reveal the performance in big-Oh notation.