<> Basic data structure
1. Time complexity
Data structure search by index search by keyword insert delete
array (Array)O(1)O(n)O(n)O(n)
queue (queue)O(n)O(n)O(1)O(1)
Linked list (Linked list)O(n)O(n)O(1)O(1)
Binary tree (Binary Search Tree) Average O(log(n))O(log(n))O(log(n))
Binary tree (Binary Search Tree) worst O(n)O(n)O(n))
2. Spatial complexity
Data structure array queue list Binary Tree
Spatial complexity O(1)O(1)O(1)O(1)
<> Advanced data structure
What problems can be solved by the time complexity of data structure operation
heap (Heap)O(log(n)): push, pop; O(1):top Global dynamic search for maximum and minimum height
Hashtable (Hash table)O(1）: insert, find, delete Does the query element exist ,key-value Query question level
trie (Trip)O(1): insert, find, delete It's similar to hashing , Does the query element exist ,key-value Query questions
And check the collection (UnionFind)O(1): union, find Dynamically merge sets and determine whether two elements are in the same set
Balanced sort binary tree (Balanced BST)O(log(n)): insert, find, delete, max, min, lower, upper
Add, delete, check and modify dynamically, and support finding global maximum and minimum ; It can be used to find the minimum value larger than a certain number and the maximum value smaller than a certain number （ As close as possible ） Low high
Jump table (Skip List)O(log(n)): insert, find, delete, max, min, lower, upper and Balanced
BST The problem is the same , And can always maintain an ordered list low high
Tree array (Binary Indexed Tree)O(log(n)): insert, delete, range, sum At the same time of addition, deletion and modification , Solving the problem of interval summation
Segment tree (Segment Tree)O(log(n)): insert, find, delete, range max, range min, range
sum, lower, upper; O(1):global max, global min At the same time of addition, deletion and modification , Solving interval evaluation problem , max, min, sum
And so on can completely replace the low middle
2. Spatial complexity
Data structure heap hash table prefix tree and lookup set balanced sort binary tree jump table tree array segment tree
Spatial complexity O(1)O(1)O(1)O(1)O(1)O(1)O(log(n))O(1)
Technology