Thursday, February 16, 2017

Steve Skiena and Mobiletainment : Data Structure Tradeoffs

Fn \ Struct
Unsorted
Array
Value-Indexed
Array
Sorted
Array
Unsorted Singly
  Linked-List
Sorted Singly
 Linked-List
Unsorted Doubly
 Linked-List
Sorted Doubly
 Linked-List
Balanced
 Binary Tree
Heap
Hash Table
Search
O(n)
O(1)
O(log n)
O(n)
O(n)
O(n)
O(n)
O(log n)
O(n)
O(1)
Insert
O(1)
O(1)
O(n)
O(1)
O(n)
O(1)
O(n)
O(log n)
O(log n)
O(1)
Delete
O(1)
O(1)
O(n)
O(n)*
O(n)*
O(1)
O(1)
O(log n)
O(n)
O(1)
Successor
O(n)
O(n)
O(n)
O(1)
Predecessor
O(n)
O(n)*
O(n)
O(1)
Min
O(n)
O(n)
O(n)
O(1)
Max
O(n)
O(1)*
O(n)
O(1)
Space Usage
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)




Posted by at
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)