哈希映射/哈希表/词典/哈希集合 哈希表（Hash tables）是编程时的瑞士军刀，很多不同类型的问题（检查存在、计算频率、排序，等等）都能用哈希表来完美解决。它几乎肯定会出现在你的面试中，而你应该理解它的原理（哈希功能的角色、冲突如何解决、什么时候要调整大小、为什么）以及如何运用它们。
链表链表问题在C和C++的面试中最常见，因为它们是弄清楚应聘者是否理解指针的一种简单的办法。不过这个点太初级、太基础了，所以不管用哪种语言，你都应该知道该如何从零做起应用它们。而且由于大部分链表问题不过是与人所周知的遍历还有删除和插入相关的问题的变体，所以链表问题准备起来很容易，你没有理由拿不到这部分分数。
许多链表问题中都会用到一个小技巧，那就是慢速/快速指针技术。它的简单版含义如下：使用两个指针迭代生成一个列表，其中一个指针在另一个指针的前面。快速模式下的指针可能会是一个位于前面的固定数值（它有助于确定列表有无循环，或者找到列表中的第k个元素），或者也可能会跳过慢速指针经过的多个结点（打个比方，如果快速指针的速度是慢速指针的两倍，那么当它到达列表末尾时，慢速指针将会位于列表的中间）。
请注意，当面试官谈到链表时，他们常常指的是单链表，但你无论如何都应该问清楚。
栈/队列栈和队列一般会是你用来解题的数据结构的一部分。你应该知道如何用链表和数组两种方式来实现它们。
加练两道题：利用两个队列实现一个栈，以及利用两个栈来实现一个队列。
树/二叉树/二叉搜索树（BST）/字典树/堆你可能不会每天都见到树和图，但你很可能会在面试时遇到它们，所以你要彻底地看一下这些数据结构。
树最一般的定义，是和其他结点没有或者有一个以上关系的结点的集合，但在实践中，当面试官说“树”的时候，他们指的是一种叫二叉树的东西。二叉树是一种树的类型，它的每个结点都至多有两个子树，一般被称为左子树和右子树。
你不应该把二叉树和二叉搜索树混淆起来，后者是一种特殊的二叉树，它的左子树结点上的值都比父结点小，而右子树结点上的值都比父结点大或者相等。二叉搜索树的优点是，如果树的结构相对平衡（向面试官问清楚这个问题），那么查找、插入和删除就可以在O(log n)的时间里完成。二叉搜索树的其他重要属性，就是你跟着所有的左子树走，就能得到这个树上最小的元素，而跟着所有的右子树走，就能得到这个树上最大的元素。
请注意，是有办法让树一直保持平衡的，最常用的办法就是红黑树和AVL树。我不会去弄清楚它具体实现的细节，只要知道有这些数据结构就行。
不过你绝对必须知道遍历树（tree traversal）算法：广度优先搜索（breadth-first-search）、深度优先搜索（depth-first-search），以及中序遍历、后序遍历和前序遍历之间的差别。
以下是在Java实现中序遍历的例子，它可以打印出一个树的所有值（前序遍历和后序遍历几乎和这个一样）：
void inOrderTraversal(Node root) { if (root == null) return; inOrderTraversal(root.getLeft()); // System.out.println(root.getValue()); inOrderTraversal(root.getRight()); }字典树（trie，读“tree”）常常被用在字符串问题里，它是一个n元树，除了根结点以外的每个结点都代表一个字符或者部分或完整的单词，而且沿着树的每一条路径都代表一个单词。实际上它真的没有听起来那么复杂，只要读一下维基百科上的页面、了解该如何构建一个字典树以及如何查询其中的数值就行。请注意，你可以通过前序遍历输出字典树中的所有键。作为一个练习，你可以想一想自己会如何利用字典树实现自动完成功能。
最后是堆（heaps），它也被称为优先队列，是你应该了解的最后一种数据结构。它们通常都是满足堆属性的二叉树：每个结点的子树的值都比结点本身的值小，或者与它相等。所以根结点的值总是最大的，也就是说你总能找到最大值，但代价就是寻找其他任何一个值所需的时间都是O(n)。插入和删除所需的时间依然是O(logn)。
有向图/无向图/加权图