Data Structures/Tradeoffs

From

Revision as of 09:51, 25 June 2006 by Jguk (Talk)
(diff) ← Older revision | Current revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Data Structures
Introduction - Asymptotic Notation - Arrays - List Structures & Iterators
Stacks & Queues - Trees - Min & Max Heaps - Graphs
Hash Tables - Sets - Tradeoffs

Tradeoffs

Hashtables use a lot of memory but can be very fast searches, in linear time.

In general you should use the data structure that best fits what you want to do, rather then trying to find the most efficient way.

 [TODO:]
 Use asymptotic behaviour to decide, most importantly seeing how the
 structure will be used: an infrequent operation does not need to be
 fast if it means everything else will be much faster


 [TODO:]
 Can use a table like this one to compare the asymptotic behaviour of every
 structure for every operation on it.

Sequences (aka lists):

Dynamic Array Array Deque Singly Linked List Double Linked List
Push (Front) O(n) O(1) O(1) O(1)
Pop (Front) O(n) O(1) O(1) O(1)
Push (Back) O(1) O(1) O(n), maybe O(1)* O(1)
Pop (Back) O(1) O(1) O(n) O(1)
Insert before (given iterator) O(n) O(n) O(n) O(1)
Delete (given iterator) O(n) O(n) O(n) O(1)
Insert after (given iterator) O(n) O(n) O(1) O(1)
Delete after (given iterator) O(n) O(n) O(1) O(1)
Get nth element (random access) O(1) O(1) O(n) O(n)
Good for implementing stacks yes (back is top) yes yes (front is top) yes
Good for implementing queues no yes maybe* yes
C++ STL std::vector std::deque - std::list
Java Collections java.util.ArrayList java.util.ArrayDeque - java.util.LinkedList
* singly-linked lists can push to the back in O(1) with the modification that you keep a pointer to the last node

Associative containers (sets, associative arrays):

Sorted Array Sorted Linked List Self-balancing Binary Search Tree Hash Table
Find key O(log n) O(n) O(log n) O(1) average O(n) worst
Insert element O(n) O(n) O(log n) O(1) average O(n) worst
Erase key O(n) O(n) O(log n) O(1) average O(n) worst
Erase element (given iterator) O(n) O(1) O(1) O(1)
Can traverse in sorted order? yes yes yes no
Needs comparison function comparison function comparison function hash function
C++ STL - - std::set

std::map
std::multiset
std::multimap

__gnu_cxx::hash_set

__gnu_cxx::hash_map
__gnu_cxx::hash_multiset
__gnu_cxx::hash_multimap

Java Collections - - java.util.TreeSet

java.util.TreeMap

java.util.HashSet

java.util.HashMap


 [TODO:]
 Can also add a table that specifies the best structure for some specific need
 e.g. For queues, double linked. For stacks, single linked. For sets, hash tables. etc...
 [TODO:]
 Could also contain table with space complexity information (there is a significative cost
 in using hashtables or lists implemented via arrays, for example).



Data Structures
Introduction - Asymptotic Notation - Arrays - List Structures & Iterators
Stacks & Queues - Trees - Min & Max Heaps - Graphs
Hash Tables - Sets - Tradeoffs

Edit this chapter

Personal tools
MediaWiki Appliance - Powered by TurnKey Linux