实用的数据结构

点击关注上方“知了小巷”，

设为“置顶或星标”，第一时间送达干货。

实用数据结构

• 数组和字符串 Array & String
• 链表 LinkedList
• 栈 Stack
• 队列 Queue
• 双端队列 Deque
• 树 Tree

数组

「数组的优点」

• 构建一个数组是非常简单的
• 数组能在O(1)时间里根据数组下标index查询某个元素

「数组的缺点」

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

如果要在算法中使用数组，需要考虑数组的缺点是否会增加算法的时间复杂度和空间复杂度。

链表

「单链表」

链表中的每个元素实际上是一个单独的对象，而所有对象都通过每个元素中的引用字段链在一起。

「双链表」

与单链表不同的是，双链表的每个结点中都含有两个引用字段。

「链表的优点」

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

「链表的缺点」

• 查询元素需要O(n)时间 list.next.next

遇到数据元素个数不确定、而且经常需要添加和删除的算法场景时，使用链表是比较合适的。

涉及链表的算法题一般解题技巧：

• 利用快、慢指针（有时候需要用到三个指针）
• 构建一个虚假的链表头

栈

「栈的特点：后进先出(LIFO)」

• 所有操作都是在栈的顶部完成的
• 只能够查看栈顶的元素
• 只能够向栈的顶部压入数据和弹出数据

栈本身可以用一个单链表来实现；
使用场景：只关心上一次的操作，处理完上一次的操作之后，能在O(1)时间内查找到更前一次的操作。

队列

「队列的特点：先进先出(FIFO)」

• 只允许在队尾查看和添加数据；在队头查看和删除数据。

一般可使用双链表实现队列。

双端队列

「基本实现」

可以利用一个双链表，队列的头尾两端能在O(1)时间内进行数据的查看、添加和删除。

「常用场景」：实现一个长度动态变化的窗口或者连续区间。

树

「树的共性：结构直观，与递归有关」

「常见的树」

• 普通二叉树
• 平衡二叉树
• 完全二叉树
• 二叉搜索树
• 四叉树
• 多叉树

「特殊的树」

• 红黑树
• 自平衡二叉搜索树

「树的遍历和序列化」

• 前序遍历（Preorder Traversal） 根-左-右
• 中序遍历（Inorder Traversal） 左-根-右 二叉搜索树
• 后序遍历（Postorder Traversal） 左-右-根

遍历方法：根节点和左右子树调整先后顺序，并从左子树、右子树分别递归下去。