数据结构是算法的基石，如果没有扎实的数据结构基础，想要把算法学好甚至融会贯通是非常困难的，而优秀的算法又往往取决于你采用哪种数据结构。

所以，接下来两节课的主题是，在算法面试中经常会被用到的数据结构以及一些实用技巧。同时穿插一些经典的题目，加深理解。这节课主要讲：

数组、字符串（Array & String）

字符串转化

数组和字符串是最基本的数据结构，在很多编程语言中都有着十分相似的性质，而围绕着它们的算法面试题也是最多的。

很多时候，在分析字符串相关面试题的过程中，我们往往要针对字符串当中的每一个字符进行分析和处理，甚至有时候我们得先把给定的字符串转换成字符数组之后再进行分析和处理。

举例：翻转字符串“algorithm”。

解法：用两个指针，一个指向字符串的第一个字符 a，一个指向它的最后一个字符 m，然后互相交换。交换之后，两个指针向中央一步步地靠拢并相互交换字符，直到两个指针相遇。这是一种比较快速和直观的方法。

注意：由于无法直接修改字符串里的字符，所以必须先把字符串变换为数组，然后再运用这个算法。

数组的优缺点

要掌握一种数据结构，就必须要懂得分析它的优点和缺点。数组的优点在于：

而数组的缺点在于：

所以，当你在考虑是否应当采用数组去辅助你的算法时，请务必考虑它的优缺点，看看它的缺点是否会阻碍你的算法复杂度以及空间复杂度。

例题分析

LeetCode 第 242 题：给定两个字符串 s 和 t，编写一个函数来判断 t 是否是 s 的字母异位词。

说明：你可以假设字符串只包含小写字母。

示例1

输入: s = "anagram", t = "nagaram"

输出: true

示例 2

输入: s = "rat", t = "car"

输出: false

字母异位词，也就是两个字符串中的相同字符的数量要对应相等。例如，s 等于 “anagram”，t 等于 “nagaram”，s 和 t 就互为字母异位词。因为它们都包含有三个字符 a，一个字符 g，一个字符 m，一个字符 n，以及一个字符 r。而当 s 为 “rat”，t 为 “car”的时候，s 和 t 不互为字母异位词。

解题思路

一个重要的前提“假设两个字符串只包含小写字母”，小写字母一共也就 26 个，因此：

可以利用两个长度都为 26 的字符数组来统计每个字符串中小写字母出现的次数，然后再对比是否相等；

可以只利用一个长度为 26 的字符数组，将出现在字符串 s 里的字符个数加 1，而出现在字符串 t 里的字符个数减 1，最后判断每个小写字母的个数是否都为 0。

按上述操作，可得出结论：s 和 t 互为字母异位词。

建议：限于篇幅不对此题进行代码剖析，但是这道题非常经典，建议大家到 LeetCode 上试试。

链表（LinkedList）

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

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

链表的优缺点

链表的优点如下：