数据结构是计算机存储、组织数据的方式。

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择数据结构可以带来更高的运行或者存储效率。

image.png

  • 数据：描述客观事物的符号
  • 数据元素：组成数据的、有一定意义的基本单位
  • 数据项：一个数据元素可以由若干个数据项组成
  • 数据对象：性质相同的数据元素的组合，数据的子集
  • 数据结构：相互之间存在一种或多种特定关系的数据元素的集合
  1. 数据 => 数据对象 => 数据元素 => 数据项

八大常见的数据结构

  1.                                        <br />![](https://cdn.nlark.com/yuque/0/2019/png/103922/1557647945585-6d5bdc08-b170-4c45-93da-b5026fd681d1.png#align=left&display=inline&height=264&originHeight=529&originWidth=1041&status=done&style=none&width=520)<br />                                           <br />![](https://cdn.nlark.com/yuque/0/2019/png/103922/1557647980576-6cefb78b-38ba-448f-8b7a-c78b89bd183d.png#align=left&display=inline&height=282&originHeight=563&originWidth=958&status=done&style=none&width=479)
  1. 数组 Array
  2. 堆栈 Stack
  3. 队列 Queue => 优先队列 Priority Queue
  4. 链表 Linked List
  5. 树 Tree => 二叉树 Binary Search Tree
  6. 图 Graph
  7. 字典树 Trie
  8. 散列表（哈希表）Hash Table

在较高的层次上，基本上有三种类型的数据结构:

  • 堆栈和队列是类似于数组的结构，仅在项目的插入和删除方式上有所不同。
  • 链表，树，和图结构的节点是引用到其他节点。
  • 散列表依赖于散列函数来保存和定位数据。

在复杂性方面：

  • 堆栈和队列是最简单的，并且可以从中构建链表。
  • 树和图是最复杂的，因为它们扩展了链表的概念。
  • 散列表和字典树需要利用这些数据结构来可靠地执行。

就效率而已：

  • 链表是记录和存储数据的最佳选择。
  • 而哈希表和字典树在搜索和 检索数据方面效果最佳。

精通一个领域

  • Chunk it up（切入知识点）
  • Deliberate Practicing（刻意练习）
  • Feedback（反馈）
    • 即时反馈
    • 主动反馈（自己去找）
      • 主动去看比你高级的工程师的代码（Github、LeetCode）
      • 观看课程视频
    • 被动反馈（高手给你指点）
      • Code Review

练习算法和数据结构时候的做法。

切题（算法题）四件套

  • Clarification 分类
  • Possible Solutions 可能的解决方案
    • Compare（Time / Space）对比
    • Optimal（加强）
  • Coding（多写）
  • Test Cases 测试用例

算法大纲

  • Greedy
  • Recursion / Backtrace
  • Traversal
  • Breadth-first / Depth-first search
  • Divide and Conquer
  • Dynamic Programming 动态规划
  • Binary Search
  • Graph

Big O notation

  • 时间复杂度

  • 空间复杂度

  • O(1)：Constant Complexity：Constant 常数复杂度

  • O(log n)：Logarithmic Complexity：对数复杂度
  • O(n)：Linear Complexity：线性时间复杂度
  • O(n^2)：N square Comlexity 平方
  • O(n^3)：N square Comlexity 立方
  • O(2^n)：Exponential Growth 指数
  • O(n!)：Factorial 阶乘

注意：只看最高复杂度的运算。

Master Theorem

LeetCode

  • 做题
  • 时间复杂度

https://etianqq.gitbooks.io/javascript-data-structures/content/%E5%88%97%E8%A1%A8.html
https://segmentfault.com/a/1190000014141614#articleHeader5
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
http://www.cs.armstrong.edu/liang/animation/animation.html