《Comparing Data Structures.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、Comparing Data StructuresExamples Data Structures Efficiency Get‐by‐Data Structure Add Find Delete index Array (T[])O(n)O(n) O(n) O(1) Linked list O(1)O(n) O(n) O(n) (LinkedList) Resizable array list O(1)O(n) O(n) O(1) (List)Stack (Stack)O(1)‐ O(1) ‐ Queue (Queue)O(1)‐ O(1) ‐
2、 2 Data Structures Efficiency (2)Get‐by‐Data Structure Add Find Delete index Hash table O(1)O(1)O(1)‐ (Dictionary)Tree‐based dic@onary (Sorted O(logn)O(logn)O(logn)‐ Dictionary)Hash table based set O(1)O(1) O(1) ‐ (HashSet) Tree based set O(logn)O(logn)O(logn)‐ (SortedSet
3、) 3 Choosing Data Structure •Arrays (T[]) –Use when fixed number of elements should be processed by index •Resizable array lists (List) –Use when elements should be added and processed by index •Linked lists (LinkedList) –Use when elements should be added at the both sides of the
4、list –Otherwise use resizable array list (List) 4 Choosing Data Structure (2) •Stacks (Stack) –Use to implement LIFO (last‐in‐first‐out) behavior –List could also work well•Queues (Queue) –Use to implement FIFO (first‐in‐first‐out) behavior –LinkedList could also work well
5、•Hash table based dicOonary (Dictionary) –Use when key‐value pairs should be added fast and searched fast by key –Elements in a hash table have no parOcular order 5 Choosing Data Structure (3) •Balanced search tree based dicOonary (SortedDictionary) –Use when key‐value pairs
6、should be added fast, searched fast by key and enumerated sorted by key •Hash table based set (HashSet) –Use to keep a group of unique values, to add and check belonging to the set fast –Elements are in no parOcular order •Search tree based set (SortedSet) –Use to keep a group of
7、 ordered unique values 6 Summary•Algorithm complexity is rough esOmaOon of the number of steps performed by given computaOon –Complexity can be logarithmic, linear, n log n, square, cubic, exponenOal, etc. –Allows to esOmaOng the speed of given code before its execuOon •Different data
