数据结构
数据结构是在计算机中组织和存储数据的一种特殊方式，使得数据可以高效地被访问和修改。更确切地说，数据结构是数据值的集合，表示数据之间的关系，也包括了作用在数据上的函数或操作。
链表
在计算机科学中, 一个 链表 是数据元素的线性集合, 元素的线性顺序不是由它们在内存中的物理位置给出的。 相反, 每个元素指向下一个元素。它是由一组节点组成的数据结构,这些节点一起,表示序列。
在最简单的形式下，每个节点由数据和到序列中下一个节点的引用(换句话说，链接)组成。这种结构允许在迭代期间有效地从序列中的任何位置插入或删除元素。
更复杂的变体添加额外的链接，允许有效地插入或删除任意元素引用。链表的一个缺点是访问时间是线性的(而且难以管道化)。
更快的访问，如随机访问，是不可行的。与链表相比，数组具有更好的缓存位置。
INFO
在js中，落实到代码层面的链表节点可以用如下代码表示：
class ListNode {
constructor(val) {
this.val = val;
this.next = null;
}
}
let node1 = new ListNode(1);
let node2 = new ListNode(2);
let node3 = new ListNode(3);
node1.next = node2;
node2.next = node3;
这些本该分散的数据通过索引在数据(而并非物理存储上)形成联系构成链表.
双向链表
在计算机科学中, 一个 双向链表(doubly linked list) 是由一组称为节点的顺序链接记录组成的链接数据结构。每个节点包含两个字段，称为链接，它们是对节点序列中上一个节点和下一个节点的引用。开始节点和结束节点的上一个链接和下一个链接分别指向某种终止节点，通常是前哨节点或null，以方便遍历列表。如果只有一个前哨节点，则列表通过前哨节点循环链接。它可以被概念化为两个由相同数据项组成的单链表，但顺序相反。
两个节点链接允许在任一方向上遍历列表。
在双向链表中进行添加或者删除节点时,需做的链接更改要比单向链表复杂得多。这种操作在单向链表中更简单高效,因为不需要关注一个节点（除第一个和最后一个节点以外的节点）的两个链接,而只需要关注一个链接即可。
INFO
从代码层面上来看，双向链表中的节点会记录上一个节点和下一个节点，这使得链表可以正向或反向迭代：
class ListNode {
constructor(val) {
this.val = val;
this.pre = null;
this.next = null;
}
}
“开发中双向链表的应用场景我遇到过几次，除开常见的undo/redo功能，其中有两次都是通过链表用来处理文本语义较为有趣。第一次在永中weboffice4.x中，公司的架构师设计这种链表结构来处理文本数据；第二次是我独立给公司开发个类问卷星的表单编辑器，这个编辑器通过输入中文文本来自动生成问卷问题。”
队列
在计算机科学中, 一个 队列(queue) 是一种特殊类型的抽象数据类型或集合。集合中的实体按顺序保存。
队列基本操作有两种：入队和出队。从队列的后端位置添加实体，称为入队；从队列的前端位置移除实体，称为出队。
队列中元素先进先出 FIFO (first in, first out)的示意
const queue = [];
queue.push('任务A');
queue.push('任务B');
const first = queue.shift();
栈
在计算机科学中, 一个 栈(stack) 是一种抽象数据类型,用作表示元素的集合,具有两种主要操作:
- push, 添加元素到栈的顶端(末尾);
- pop, 移除栈最顶端(末尾)的元素.
以上两种操作可以简单概括为“后进先出(LIFO = last in, first out)”。
此外,应有一个 peek 操作用于访问栈当前顶端(末尾)的元素。
"栈"这个名称,可类比于一组物体的堆叠(一摞书,一摞盘子之类的)。
栈的 push 和 pop 操作的示意
INFO
javascript中的数组可以通过api实现栈的出入操作，例如操作栈尾的push和pop，操作栈首的shift和unshift。
哈希表
在计算中, 一个 哈希表(hash table 或hash map) 是一种实现 关联数组(associative array) 的抽象数据类型, 该结构可以将 键映射到值。
哈希表使用 哈希函数/散列函数 来计算一个值在数组或桶(buckets)中或槽(slots)中对应的索引,可使用该索引找到所需的值。
理想情况下,散列函数将为每个键分配给一个唯一的桶(bucket),但是大多数哈希表设计采用不完美的散列函数,这可能会导致"哈希冲突(hash collisions)",也就是散列函数为多个键(key)生成了相同的索引,这种碰撞必须 以某种方式进行处理。
INFO
哈希表的本质是高效的键值映射，在javascript中，哈希表的实现有Object和Map。
堆(数据结构)
在计算机科学中, 一个 堆(heap) 是一种特殊的基于树的数据结构，它满足下面描述的堆属性。
在一个 最小堆(min heap) 中, 如果 P 是 C 的一个父级节点, 那么 P 的key(或value)应小于或等于 C 的对应值。
在一个 最大堆(max heap) 中, P 的key(或value)大于 C 的对应值。
在堆“顶部”的没有父级节点的节点,被称之为根节点。
INFO
堆(heap)即是一种为高效获取最值而生的完全二叉树，下图展示了一个最大堆：
flowchart TD
%% 堆的树形结构（最大堆示例）
A["10 (idx:0)"] --> B["8 (idx:1)"]
A --> C["9 (idx:2)"]
B --> D["5 (idx:3)"]
B --> E["3 (idx:4)"]
C --> F["7 (idx:5)"]
C --> G["6 (idx:6)"]
%% 样式：让节点更清晰
classDef heapNode fill:#e6f7ff,stroke:#1890ff,stroke-width:2px;
class A,B,C,D,E,F,G heapNode
%% 添加数组表示说明（用注释或子图）
subgraph ArrayRepresentation["数组表示: [10, 8, 9, 5, 3, 7, 6]"]
end
其中：
- 父节点索引：
parent(i) = Math.floor((i - 1) / 2)
- 左子节点：
left(i) = 2 * i + 1
- 右子节点：
right(i) = 2 * i + 2
一个最小堆可以是下面这样：
flowchart TD
A["1 (idx:0)"] --> B["3 (idx:1)"]
A --> C["2 (idx:2)"]
B --> D["5 (idx:3)"]
B --> E["4 (idx:4)"]
C --> F["6 (idx:5)"]
C --> G["7 (idx:6)"]
classDef minHeapNode fill:#f6ffed,stroke:#52c41a,stroke-width:2px;
class A,B,C,D,E,F,G minHeapNode
subgraph ArrayRep["数组: [1, 3, 2, 5, 4, 6, 7]"]
end
如何维护堆(heap)
插入（Push）→ 向上调整（Sift Up）
- 新元素放数组末尾
- 与父节点比较，若违反堆序（如大根堆中子 > 父），则交换
- 重复直到满足堆序或到达根
function siftUp(arr, idx) {
while (idx > 0) {
const parent = Math.floor((idx - 1) / 2);
if (arr[idx] <= arr[parent]) break;
[arr[idx], arr[parent]] = [arr[parent], arr[idx]];
idx = parent;
}
}
删除堆顶（Pop）→ 向下调整（Sift Down）
- 将最后一个元素移到堆顶
- 与左右子中更优者（大根堆选较大，小根堆选较小）比较
- 若违反堆序，交换并继续下沉
function siftDown(arr, idx, size) {
while (true) {
let max = idx;
const left = 2 * idx + 1;
const right = 2 * idx + 2;
if (left < size && arr[left] > arr[max]) max = left;
if (right < size && arr[right] > arr[max]) max = right;
if (max === idx) break;
[arr[idx], arr[max]] = [arr[max], arr[idx]];
idx = max;
}
}
优先队列
在计算机科学中, 优先级队列(priority queue) 是一种抽象数据类型, 它类似于常规的队列或栈, 但每个元素都有与之关联的“优先级”。
在优先队列中, 低优先级的元素之前前面应该是高优先级的元素。 如果两个元素具有相同的优先级, 则根据它们在队列中的顺序是它们的出现顺序即可。
优先队列虽通常用堆来实现,但它在概念上与堆不同。优先队列是一个抽象概念，就像“列表”或“图”这样的抽象概念一样;
正如列表可以用链表或数组实现一样，优先队列可以用堆或各种其他方法实现,例如无序数组。
字典树
在计算机科学中, 字典树(trie,中文又被称为”单词查找树“或 ”键树“), 也称为数字树,有时候也被称为基数树或前缀树（因为它们可以通过前缀搜索）,它是一种搜索树--一种已排序的数据结构,通常用于存储动态集或键为字符串的关联数组。
与二叉搜索树不同, 树上没有节点存储与该节点关联的键; 相反,节点在树上的位置定义了与之关联的键。一个节点的全部后代节点都有一个与该节点关联的通用的字符串前缀, 与根节点关联的是空字符串。
值对于字典树中关联的节点来说,不是必需的,相反,值往往和相关的叶子相关,以及与一些键相关的内部节点相关。
有关字典树的空间优化示意,请参阅紧凑前缀树
INFO
字典树适用于实现文本的高效搜索，树的结构基于输入的文本构建，一个字典树的示例如下：
root
|
a
/|\
c p l
/ \ \
t p i
/ \ \
i l n
/ \ \
o e g
/ |
n y
/ |
n (action) (apply)
|
(act)
|
e (apple)
|
g (aling)
上图所示的字典树由apple、apply、action、act、aling这五个单词构成。
一个字典树的javascript实现如下：
class TrieNode {
constructor() {
this.children = new Map();
this.isEnd = false;
this.word = null;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let node = this.root;
for (const char of word) {
if (!node.children.has(char)) {
node.children.set(char, new TrieNode());
}
node = node.children.get(char);
}
node.isEnd = true;
node.word = word;
}
search(word) {
let node = this.root;
for (const char of word) {
if (!node.children.has(char)) return false;
node = node.children.get(char);
}
return node.isEnd;
}
startsWith(prefix) {
let node = this.root;
for (const char of prefix) {
if (!node.children.has(char)) return false;
node = node.children.get(char);
}
return true;
}
getWordsWithPrefix(prefix) {
const result = [];
let node = this.root;
for (const char of prefix) {
if (!node.children.has(char)) return result;
node = node.children.get(char);
}
this._dfs(node, result);
return result;
}
_dfs(node, result) {
if (node.isEnd) result.push(node.word);
for (const child of node.children.values()) {
this._dfs(child, result);
}
}
}
基础算法
基础算法是前端面试中最常考察的内容，主要包括排序算法和交换算法，这些算法能够有效考察应聘者的逻辑思维能力和代码实现能力。
冒泡排序
冒泡排序是最基础的排序算法，时间复杂度为O(n²)，在最坏情况下需要进行n(n-1)/2次比较。其核心思想是相邻元素两两比较，如果顺序不对则交换位置，每一轮扫描后将当前最大的元素"冒泡"到末尾。冒泡排序是稳定的，因为它不会改变相等元素的相对顺序。JavaScript实现如下：
function bubbleSort(arr) {
for (let i = 0, l = arr.length; i < l - 1; i++) {
for (let j = 0; j < l - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
快速排序
快速排序是基于分治策略的高效排序算法，平均时间复杂度为O(n log n)，最坏情况下为O(n²)。其核心思想是选取基准元素，将数组分为小于基准和大于基准的两部分，然后递归排序子数组。快速排序是不稳定的，但在实际应用中效率极高。JavaScript实现如下：
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[0];
const left = arr.filter(item => item < pivot);
const middle = arr.filter(item => item === pivot);
const right = arr.filter(item => item > pivot);
return [...quickSort(left), ...middle, ...quickSort(right)];
}
插入排序
插入排序也是一种基础排序算法，时间复杂度为O(n²)，但在数据基本有序时效率较高。其核心思想是将未排序的元素插入到已排序的正确位置。JavaScript实现如下：
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
return arr;
}
希尔排序
希尔排序是插入排序的一种优化，通过分组插入排序减少元素的移动次数。其时间复杂度取决于增量序列的选择，通常为O(n log n)到O(n²)之间。希尔排序的核心是选择合适的增量序列，将数组分为多个子组进行插入排序，然后逐渐减小增量直到为1。JavaScript实现如下：
function shellSort(arr) {
let len = arr.length;
let gap = Math.floor(len / 2);
while (gap > 0) {
for (let i = gap; i < len; i++) {
let temp = arr[i];
let j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
gap = Math.floor(gap / 2);
}
return arr;
}
归并排序
归并排序是一种分治算法，将数组递归地分成小数组，然后合并这些已排序的小数组。其时间复杂度为O(n log n)，空间复杂度为O(n)，是稳定的排序算法。JavaScript实现如下：
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const middle = Math.floor(arr.length / 2);
const left = arr.slice(0, middle);
const right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
const result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
while (i < left.length) result.push(left[i++]);
while (j < right.length) result.push(right[j++]);
return result;
}
数组操作算法
数组去重
数组去重是前端面试中最基础且高频的算法题，有多种实现方法：
function uniqueWithSet(arr) {
return [...new Set(arr)];
}
function uniqueWithMap(arr) {
const map = new Map();
return arr.filter(item => {
if (!map.has(item)) {
map.set(item, true);
return true;
}
return false;
});
}
function uniqueWithTwoPointers(arr) {
if (arr.length === 0) return arr;
let i = 0;
for (let j = 1; j < arr.length; j++) {
if (arr[j] !== arr[i]) {
i++;
arr[i] = arr[j];
}
}
return arr.slice(0, i + 1);
}
两数之和
两数之和是LeetCode中的经典问题，考察哈希表的使用和空间换时间的优化思路：
function twoSum(nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (map.has(complement)) {
return [map.get(complement), i];
}
map.set(nums[i], i);
}
return [];
}
三数之和
三数之和是两数之和的扩展，考察双指针法和去重逻辑：
function threeSum(nums) {
nums.sort((a, b) => a - b);
const result = [];
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue;
let left = i + 1, right = nums.length - 1, target = -nums[i];
while (left < right) {
const sum = nums[left] + nums[right];
if (sum === target) {
result.push([nums[i], nums[left], nums[right]]);
while (left < right && nums[left] === nums[left + 1]) left++;
while (left < right && nums[right] === nums[right - 1]) right++;
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
return result;
}
最大子数组和
最大子数组和考察动态规划思想，时间复杂度为O(n)：
function maxSubArray(nums) {
let currentSum = nums[0];
let maxSum = nums[0];
for (let i = 1; i < nums.length; i++) {
currentSum = Math.max(nums[i], currentSum + nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
和为k的子数组
和为k的子数组考察前缀和与哈希表的结合使用：
function subarraySum(nums, k) {
const map = new Map([[0, 1]]);
let sum = 0, count = 0;
for (const num of nums) {
sum += num;
count += map.get(sum - k) || 0;
map.set(sum, (map.get(sum) || 0) + 1);
}
return count;
}
数组旋转
数组旋转考察原地操作和空间优化能力，可通过三次翻转实现：
function rotateArray(arr, k) {
k = k % arr.length;
reverse(arr, 0, arr.length - 1);
reverse(arr, 0, k - 1);
reverse(arr, k, arr.length - 1);
return arr;
}
function reverse(arr, start, end) {
while (start < end) {
const temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
字符串处理方法
统计字母出现次数
统计字母出现次数考察对象或Map的使用：
function countLetters(str) {
const count = {};
for (const char of str) {
count[char] = (count[char] || 0) + 1;
}
return count;
}
回文判断
回文判断考察字符串操作和循环逻辑：
function isPalindrome(str) {
return str === str.split('').reverse().join('');
}
function isPalindrome(str) {
let left = 0, right = str.length - 1;
while (left < right) {
if (str[left] !== str[right]) return false;
left++;
right--;
}
return true;
}
最长无重复子串
最长无重复子串考察滑动窗口和哈希表的结合使用，时间复杂度为O(n)：
function longest substringWithoutRepetition(s) {
const map = new Map();
let max = 0, left = 0;
for (let i = 0; i < s.length; i++) {
if (map.has(s[i]) && map.get(s[i]) >= left) {
left = map.get(s[i]) + 1;
}
map.set(s[i], i);
max = Math.max(max, i - left + 1);
}
return max;
}
```
最长回文子串（Manacher算法）
最长回文子串是字符串处理中的难点，Manacher算法可在O(n)时间内解决：
function longestPalindrome(s) {
if (s.length === 0) return '';
const processedStr = '#' + s.split('').join('#') + '#';
const n = processedStr.length;
const pArr = new Array(n).fill(1);
let center = 0, right = 0, maxLen = 0, maxCenter = 0;
for (let i = 1; i < n - 1; i++) {
if (i < right) {
pArr[i] = Math.min(pArr[2 * center - i], right - i);
}
while (processedStr[i + pArr[i]] === processedStr[i - pArr[i]]) {
pArr[i]++;
}
if (i + pArr[i] > right) {
center = i;
right = i + pArr[i];
}
if (pArr[i] > maxLen) {
maxLen = pArr[i];
maxCenter = i;
}
}
const start = (maxCenter - maxLen) / 2;
return s.substring(start, start + maxLen - 1);
}
```
进阶算法
随着前端技术栈的复杂化，一些进阶算法题也开始在面试中出现。
区间合并
区间合并考察数组排序和合并逻辑：
function mergeIntervals(intervals) {
if (intervals.length === 0) return [];
intervals.sort((a, b) => a[0] - b[0]);
const result = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const last = result[result.length - 1];
if (intervals[i][0] <= last[1]) {
last[1] = Math.max(last[1], intervals[i][1]);
} else {
result.push(intervals[i]);
}
}
return result;
}
版本号排序
版本号排序考察字符串分段和逐位比较：
function versionSort(arr) {
return arr.sort((a, b) => {
const arr1 = a.split('.').map(Number);
const arr2 = b.split('.').map(Number);
const len = Math.max(arr1.length, arr2.length);
for (let i = 0; i < len; i++) {
const num1 = arr1[i] || 0;
const num2 = arr2[i] || 0;
if (num1 !== num2) return num1 - num2;
}
return 0;
});
}
大数阶乘
大数阶乘考察数组模拟大数存储和进位处理：
function factorial(n) {
const result = [1];
for (let i = 2; i <= n; i++) {
let carry = 0;
for (let j = 0; j < result.length; j++) {
const product = result[j] * i + carry;
result[j] = product % 10;
carry = Math.floor(product / 10);
}
while (carry > 0) {
result.push(carry % 10);
carry = Math.floor(carry / 10);
}
}
return result.reverse().join('');
}
链表操作
链表反转是数据结构中的经典问题，考察指针操作：
function reverseLinkedList(head) {
let prev = null, cur = head;
while (cur !== null) {
const next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}
function reverseLinkedListRecursively(head) {
if (head === null || head.next === null) return head;
const newHead = reverseLinkedListRecursively(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
二叉树层次遍历
二叉树层次遍历考察队列数据结构的使用：
function levelOrder(root) {
if (root === null) return [];
const queue = [root];
const result = [];
while (queue.length > 0) {
const levelSize = queue.length;
const level = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
level.push(node.val);
if (node.left !== null) queue.push(node.left);
if (node.right !== null) queue.push(node.right);
}
result.push(level);
}
return result;
}
Aling