以下为2021年11月27日心得总结，基于前端。

1. 前言

一个好的程序 = 数据结构 + 算法

对于大多数人来说，数据结构与算法很难，学习起来很枯燥

从我自身的学习情况来看，前期也是觉得数据结构与算法“用不到、没必要学”，待慢慢接触之后，才开始感受到数据结构和算法的美妙之处！

常用的数据结构与算法：

• 数据结构：栈、队列、链表、集合、字典、树、图、堆

• 算法：链表/树/图的遍历、数组的排序和搜索……

• 算法设计思想：分而治之、动态规划、贪心、回溯……

2. 为什么学习

简单归纳为：

• 学习解决问题的思想
• 面试准备

在学习数据结构前，对待问题：暴力出奇迹。题是写出来了，功能也实现了，但是可能嵌套了多层for，或是写了非常庸长的代码，性能极差，若是真正用于实现功能，时间复杂、空间复杂呈指数式增长，还挺恐怖的。。。

待一步一步学习完数据结构之后，“原来这个问题可以这样解决！”

当然，面试是离不开数据结构和算法的，这个就不多说了。

↓ 贴一个图，当时做出来之后，大叹：神奇的数据结构

这一个题是困难级别，在未学习数据结构时，可能第一时间想到的是：用for去遍历，然后再根据题目去解决

本题用到了字典和链表两个数据结构

解题思路：

• 先找出所有包含t的子串
• 找出长度最小的那个子串，并返回

解题步骤：

• 用双指针维护应该滑动窗口
• 移动右指针，找到包含t的子串，移动左指针，尽量减少包含t的子串的长度
• 存入Map这一数据结构中

3. 时间复杂度 vs 空间复杂度

题完成了，数据结构和算法用上了

不仅要实现功能，还要考虑时间复杂度和空间复杂度，进一步去优化自己的算法，使得这段程序的性能更加好、

因此，做题时应该有意识去分析程序的时间复杂度和空间复杂度

时间复杂度

空间复杂度

一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。

一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。

4. 总结

重点难点

• 数据结构：所有数据结构都很重要，和前端最相关的是链表和树
• 算法：链表/树/图的遍历、数组的排序和搜索……
• 设计思想：分而治之、动态规划较常考，贪心、回溯次之

心得

• 搞清楚数据结构与算法的特点和应用场景
• 用JS自己实现一遍
• 学会分析时间复杂度 / 空间复杂度
• 提炼前端和算法的结合点，用于实战中

5. 如何学习

途径

不限于书籍、视频、刷题

• 书籍：《学习JavaScript数据结构与算法（第3版）》
• 视频：慕课网《JavaScript版数据结构与算法》
• 刷题：LeetCode

方式

1. 系统学习数据结构与算法
2. 分类进行刷题
3. 定期回顾与总结
4. 选择经典题目：《剑指offer》

建议

• 多刷题，300+
• 多总结各种模板、套路
• 多阅读源码
• 多实战，将数据结构与算法用于实际开发中

源码里有非常多优秀的数据结构，例如Vue里面的虚拟DOM操作

↓ 贴一段源码，使用的是树这一个数据结构。树这个数据结构在前端中使用得非常多，其次还有链表

function updateChildren(parentElm, oldCh, newCh) {
    let oldStartIdx = 0;
    let newStartIdx = 0;
    let oldEndIdx = oldCh.length - 1;
    let newEndIdx = oldCh.length - 1;
    
    let oldStartVnode = oldCh[0];
    let oldEndVnode = oldCh[oldEndIdx];
    let newStartVnode = newCh[0];
    let newEndVnode = newCh[newEndIdx];
    
    while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx){
        // 先略过已经加了undefined标记的东西
        if(oldStartVnode == null || oldCh[oldStartIdx] == undefined) {
            oldStartVnode = old[++oldStartIdx]
        } else if(oldEndVnode == null || oldCh[oldEndIdx] == undefined) {
            oldEndVnode = old[--oldEndIdx]
        } else if(newStartVnode == null || newCh[newStartIdx] == undefined) {
            newStartVnode = old[++oldStartIdx]
        } else if(newEndVnode == null || newCh[newEndIdx] == undefined) {
            newEndVnode = old[--newEndIdx]
        } else if(checkSameVnode(oldStartVnode, newStartVnode)){
            // ①新前和旧前
            patchVnode(oldStartVnode,newStartVnode);
            oldStartVnode = oldCh[++oldStartIdx];   //先自增后使用
            newStartVnode = newCh[++newStartIdx];
        } else if(checkSameVnode(oldStartVnode, newStartVnode)){
            // ②新后和旧后
            patchVnode(oldStartVnode, newStartVnode);
            oldEndVnode = oldCh[--oldEndIdx];
            newEndVnode = newCh[--newEndIdx];
        } else if(checkSameVnode(oldStartVnode, newEndVnode)){
            // ③新后和旧前
            patchVnode(oldStartVnode, newEndVnode);
            // 此时要移动节点，移动新前指向的这个节点到老节点的旧后的后面
            parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling) //下一个兄弟节点前
            oldStartVnode = oldCh[++oldStartIdx];
            newEndVnode = newCh[--newEndIdx];
        } else if(checkSameVnode(oldEndVnode, newStartVnode)){
            // ④新前和旧后
            patchVnode(oldEndVnode, newStartVnode);
            // 此时要移动节点，移动新前指向的这个节点到老节点的旧后的后面
            parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm) //下一个兄弟节点前
            oldEndVnode = oldCh[++oldEndIdx];
            newStartVnode = newCh[--newStartIdx];
        } else {
            // 全都没有命中
            // 制作key的map
            if(!keyMap) {
                keyMap = {};
                for (let i = oldStartIdx; i <= oldEndIdx; i++) {
                    const key = oldCh[i].key;
                    if (key != undefined) {
                        keyMap[key] = i;
                    }
                }
            }
            // 寻找当前这项newStartIdx在keyMap中的映射的位置序号
            const idxInOld = keyMap[newStartVnode.key];
            if(idxInOld == undefined) {
                // 判断，如果idxInOld是undefined，表示是全新的项
                // 被加入的项（极速newStartVnode这项），现在还不是真正的DOM节点
                parentElm.insertBefore(ceateElem(newSrartVnode), oldStartVnode.elm);
            } else {
                // 如果不是undefined，不是全新的项，要移动
                const elmToMove = oldCh[idxInOld];
                patchVnode(elmToMove, newStartVnode);
                // 处理完后，设置为undefined
                oldCh[idxInOld] = undefined;
                parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm);
            }
            // 指针下移，只移动新的头
            newStartVnode = newCh[++newStartIdx]
        }
    }
    
    //继续看看有没有剩余的
    // 当start还是比old小,new还有剩余节点没有处理，要加项
    if (newStartIdx <= oldEndIdx) {
        // 遍历新的newChrome，添加到老的没有处理的之前
        for(let i = newStartIdx; i <= newEndIdx; i++) {
            // 如果是null，自动排到队尾
            parentElm.insertBefore(createElement(newCh[i]), oldCh[oldStartIdx].elm);
        }
    } else if (oldStartIdx <= oldEndIdx) {
        // old还有剩余节点没有处理
        // 批量删除oldStart和oldEnd指针之间的项，要减项
        for (let i = oldStartIdx; i <= oldEndIdx; i++) {
            if (oldCh[i]) {
                parentElm.removeChild(oldCh[i].elm);
            }
        }
    }
}

综上，对程序员来说，数据结构与算法是非常重要的一部分

参考文章：

前端该如何准备数据结构和算法？