数据结构与Big-Oh

文章目录

1. 1. 常见数据结构
2. 2. 常见操作
3. 3. All in one table

又是一篇关于算法的科普文章，如果你是初入行的newbie可以把这篇文章作为入门读物阅读，如果你是工作多年的老司机，可以把这篇文章作为cheatsheet备查。

常见数据结构

• 数组(array)

• 链表(LinkedList)

  单向列表(Singly-Linked List)
  双向列表(Doubly-Linked List)

• 队列(Queuen)

• 栈(Stack)

• 散列表(HashTable)

• 二叉树(Binary Tree)

• B Tree

• 红黑树(RedBlack Tree)

常见操作

• 访问某个位置的元素(Access)
• 查找某个元素(Search)
• 插入(Insertion)
• 删除(Deletion)

All in one table

Data Structure	访问	查找	插入	删除
Array	$O(1)$	$O(N)$	$O(N)$	$O(N)$
Singly-Linked List	$O(N)$	$O(N)$	$O(1)$	$O(1)$
Doubly-Linked List	$O(N)$	$O(N)$	$O(1)$	$O(1)$
Queue	$O(N)$	$O(N)$	$O(1)$	$O(1)$
Stack	$O(N)$	$O(N)$	$O(1)$	$O(1)$
HashTable	N/A	$O(1)$	$O(1)$	$O(1)$
Binary Tree	$O(log^N)$	$O(log^N)$	$O(log^N)$	$O(log^N)$
B Tree	$O(log^N)$	$O(log^N)$	$O(log^N)$	$O(log^N)$
RedBlack Tree	$O(log^N)$	$O(log^N)$	$O(log^N)$	$O(log^N)$