课程第一章 实用的数据结构

数组、字符串

优点：
构建一个数组非常简单
能让我们在O(1)的时间里根据数组的下标(index)查询某个元素

缺点：
构建时必须分配一段连续的空间
查询某个元素是否存在时需要遍历整个数组，耗费O(n)的时间(其中n是元素的个数)
删除和添加某元素时 同样需要耗费O(n)的时间

链表

优点：
灵活地分配内存空间 能在O(1)时间内删除或者添加元素

缺点：
查询元素需要O(n)时间

栈

特点：
先进后出(LIFO)

算法的基本思想：
可以用一个单链表来实现
只关心上一次的操作
处理完上一次的操作后，能在O(1)时间内查找到更前一次的操作

队列

特点：
先进先出(FIFO)

常用的场景：
广度优先搜索

树

树的共性：
结构直观
通过树问题来考察 递归算法 掌握的熟练程度

面试中常考的树的形状有：
普通二叉树
平衡二叉树
完全二叉树
二叉搜索树
四叉树
多叉树
特殊的树 红黑树、自平衡二叉搜索树

遍历：
前序遍历 中序遍历 后序遍历