Transcript Data Structures for Midterm 2

Data Structures for Midterm 2
C++ Data Structure Runtimes
Data Structure
Insert
Find
Delete
vector
O(n)
O(1) amortized
O(n)
O(1) if index is known
O(n)
sorted vector
O(n)
O(log(n))
O(n)
linked list
O(1)
*Given an Iterator
O(n)
O(1)
*Given an Iterator
balanced binary tree
O(log(n))
O(log(n))
O(log(n))
hash table
O(1)
O(1)
O(1)
vector
•
•
•
•
•
•
Continuous memory
Requires resize when capacity is exceeded
Can push_back in O(1)
General insert is O(n) due to shifting data
O(1) lookup if index is known
O(n) find
– O(log(n)) if sorted using binary search
Linked List
• Non-continuous memory
– Each data element contains a pointer to the memory
location of the next element
• Used for stack and queue
– O(1) for push, pop, top, queue, dequeue, front, back
• O(n) time to find even if the “index” is known
– Don’t know where in memory the next the element is
• Can insert and delete in O(1) with pointer
manipulation given an iterator to the proper
location
– stack and queue only use the ends of the list to get
O(1) operations
Balanced Binary Tree
• Used for set and map
• Uses (key, value) with elements sorted by key
– For set: key = value
• Searching a binary tree takes O(h) time
– if the tree is balanced: h = O(log(n))
• Insert and delete in O(1) with pointer
manipulation, but must find the location first in
O(log(n))
– Also takes O(log(n)) to balance the tree
• multiset and multimap retain duplicates
Hash Table
• Takes more time to adjust parameters
– Hash function
– Size of table
– Implementation of bins
• Once set up, O(1) insert, find, and delete are
achievable
• *Theoretically these operations are all O(n)
– Practically they are O(1)
– We will consider them to be O(1) in this class