前端开发是否有必要知道或者精通数据结构和算法？答案是肯定的，在实际的应用中，做前端开发并不会用到复杂的数据结构和算法，但是，想码出好代码却应该有个扎实的数据结构和算法基础，处理问题的思路也会不同，会算法的前端会想尽办法让代码得到更低的时间复杂度/空间复杂度，应对复杂的问题，会更加信手拈来。自认为自己就是个算法渣渣，遇到问题，就是嵌套几层循环，暴力输出，虽然能解决80%的问题，但是一旦真遇到棘手需求确实是寸步难行。

举个例子，

去年在接到公司的一个需求，需要针对面包屑导航来模拟一个类似浏览器前进后退的功能（当然对高手来说，应该很简单，哈哈），绞尽脑汁，写出来后，虽然最终实现了，但是bug层出不穷，改的是心力交瘁。今年在看相关算法的书时，里面一章关于介绍栈的小节，就介绍了如何用栈来实现浏览器的前进、后退功能，下面贴一下具体图示：

于是感慨算法真是个好东西，以前觉得前端不会用到那么多算法知识的，现在才知道算法的重要性，于是想在2022年花些时间把这个短板给补一下，下面是2月份学习的基础算法知识，所记下来的一些笔记（相对基础）。

单项链表与双向链表

let head = { next: '...', data: '...' };// 链表查找const find = (value) => {    const p = head;    while (p !== null && p.data !== value) {        p.next;    }    return p;}// 链表插入const insert = (b, x) => {    if (x === null) {        x.next = head;        head = x;    } else {        x.next = b.next;        b.next = x;    }}// 链表删除const remove = (b, x) => {    if (x === null) {        x.next = head;        head = x;    } else {        b.next = b.next.next;    }}复制代码

interface Node {    data: number;    prev: Node;    next: Node;}let head: Node = null;/*******给定值删除的单向链表、双向链表，时间复杂度为O(n)******/// 单向链表const oneWayRmove = (val: number) => {    let q: Node = head;    let p: Node = null; // 前驱节点    while(q != null && q.data != val) {        p = q;        q = q.next;    }    if (q != null) {        if (p == null) { // 尾节点            head = q.next;        } else {            p.next = q.next;        }    }}// 双向链表const twoWayRmove = (val: number) => {    let q: Node = head;    while(q != null && q.data != val) {        q = q.next;    }    if (q != null) {        if (q.prev == null) { // 尾节点            head = q.next;        } else {            q.prev.next = q.next;        }    }}/*******给定指针的删除的单向链表->时间复杂度为O(n)、双向链表->时间复杂度O(1)******/// 单向链表const oneWayPointerRmove = (q: Node) => {    if (q == null) { return; }    if (q == head) {        head = q.next;    }    let p: Node = head;    while (p != null && p.next != q) {        p = p.next;    }    if (p.next != null) {        p.next = q.next;    }}// 双向链表const twoWayPointerRmove = (q: Node) => {    if (q == null) return;    if (q.prev == null) {        head = q.next;    } else {        q.prev.next = q.next;    }}复制代码

思路: 遍历链表, 暂存当前节点next指针, 改变当前节点next指向, 更新前驱节点prev, 赋值下一遍历节点

// 单链表反转const reverseList = (head) => {    let cur: Node = head;    let prev: Node = null;    while (cur != null) { // 遍历链表        const temp = cur.next; // 暂存当前节点next指针        cur.next = prev; // 改变当前节点next指向        prev = cur; // 更新前驱节点        cur = temp; // 赋值下一遍历节点    }}复制代码

const middleNode = function(head) {    if (head == null) return;    const results = [];    let curNode = head;    while(curNode != null) {        results.push(curNode);        curNode = curNode.next;    }    if (results.length % 2 === 0) {        return [results[parseInt(results.length / 2 -1)], results[parseInt(results.length /2)]];    } else {        return results[parseInt(results.length /2)];    }};复制代码

思路一： 得到链表长度，再遍历一次链表，第k个节点，其实就是第n-k个节点 思路二： 快慢指针

interface Node {    data: number;    next: Node;}// 第k个节点，其实就是第n-k个节点const lookupForK1 = (head: Node, k: number) => { let cur = head; let node = head; let n = 0; while (cur != null) {    cur = cur.next;    n++; } for (let i = 0; i < n-k; i++) {    node = node.next; } return node;}// 快慢指针const lookupForK2 = (head: Node, k: number) => {    let fast = head; let slow = head;    for (let i = 0; i < k; i++) {        fast = fast.next;    }        while (fast) {        [fast, slow] = [fast.next, slow.next];    }    return slow;}复制代码

思路：维护一个有序的单链表，越靠近链表尾部的节点存储的是越早访问的数据，当访问某个数据的时候，会从链表的表头节点开始遍历链表，

1）如果查找得到节点，将其从原来位置删除，插入到链表头部2）如果查找不到节点，对应会分两种情况： 缓存空间未满，将新的数据节点插入链表头部 缓存空间已满，删除链表尾部节点，将新的数据节点插入链表头部

// 基于链表的LRU缓存淘汰算法/* 实现思路，维护一个有序的单链表，越靠近链表尾部的节点存储的是越早访问的数据，当访问某个数据的时候，会从链表的表头节点开始遍历链表，1）如果查找得到节点，将其从原来位置删除，插入到链表头部2）如果查找不到节点，对应会分两种情况：   缓存空间未满，将新的数据节点插入链表头部   缓存空间已满，删除链表尾部节点，将新的数据节点插入链表头部*/interface Node {    data: number;    next: Node | null;}let head: Node = null; // 头节点let cacheSize = 10; // 最大缓存空间const lruLook = (val: number) => {  let q: Node = head;  let p: Node = null; // 前驱第一个节点  let e: Node = null; // 前驱第二个节点  let i = 0;   while (q !== null && q.data !== val) {      i++;      e = p;      p = q;      q = q.next;  }  if (q !== null) {    if (p === null) { // q为头部节点        return q;    } else {        // 将其从原来位置删除，插入到链表头部        p.next = q.next;        q.next = head;        head = q;        return q;    }  } else {      // 创建新节点      const n = {        data: val,        next: null      };      if (i === 0) { // 存储空间为空        head = n;      } else if (i < cacheSize) { // 存储空间未满        n.next = head;      } else { // 存储空间未满        e.next = null; // 此时p为尾节点，而e是倒数第二个节点        n.next = head;      }      return n;  }}复制代码

思路： 对n个数进行排序，每次都是由前一个数跟后一个数比较，每循环一轮， 就可以将最大的数移到数组的最后， 总共循环n-1轮，完成对数组排序。

const bubbleSort  = (arr) => {    if (arr === null) { return; }    //i控制循环次数，长度为len的数组只需要循环len-1次，i的起始值为0所以i<len-1    for (let i = 0; i < arr.length - 1; i++) {        for (let j = 0; j < arr.length - i - 1; j++) {            // j控制比较次数，第i次循环内需要比较len-i次            // 但是由于是由arr[j]跟arr[j+1]进行比较，所以为了保证arr[j+1]不越界，j<len-i-1            if (arr[j] > arr[j + 1]) {                //如果前一个数比后一个数大，则交换位置将大的数往后放。                const temp = arr[j];                arr[j] = arr[j + 1];                arr[j + 1] = temp;                            }                    }    }}复制代码

思路： 冒泡排序的改良版，不再是前一个数跟后一个数相比较， 而是在每一次循环内都由一个数去跟 所有的数都比较一次，每次比较都选取相对较小的那个数来进行下一次的比较，并不断更新较小数的下标。

这样在一次循环结束时就能得到最小数的下标，再通过一次交换将最小的数放在最前面，通过n-1次循环之后完成排序

const selectSort  = (arr) => {    if (arr === null) { return; }    //i控制循环次数，长度为len的数组只需要循环len-1次，i的起始值为0所以i<len-1    for (let i = 0; i < arr.length - 1; i++) {        //minIndex 用来保存每次比较后较小数的下标。        let minPos = i;        //j控制比较次数，因为每次循环结束之后最小的数都已经放在了最前面，        //所以下一次循环的时候就可以跳过这个数，所以j的初始值为i+1而不需要每次循环都从0开始，并且j<len即可        for (let j = i + 1; j < arr.length; j++) {            //每比较一次都需要将较小数的下标记录下来            if (arr[minPos] > arr[j]) {                minPos = j;            }        }        //当完成一次循环时，就需要将本次循环选取的最小数移动到本次循环开始的位置。        if (minPos != i) {            const temp = arr[minPos];            arr[minPos] = arr[i];            arr[i] = temp;        }    }}复制代码

思路：首先就默认数组中的第一个数的位置是正确的，即已经排序。 然后取下一个数，与已经排序的数按从后向前的顺序依次比较，如果该数比当前位置排好序的数小，则将排好序的数的位置向后移一位。 重复上一步骤，直到找到合适的位置。

找到位置后就结束比较的循环，将该数放到相应的位置。

const insertSort  = (arr) => {    if (arr === null) { return; }    //i控制循环次数，因为已经默认第一个数的位置是正确的，所以i的起始值为1，i<len，循环len-1次    for (let i = 1; i < arr.length; i++) {        let j = i; // 变量j用来记录即将要排序的数的位置即目标数的原位置        let target= arr[j];        //while循环用来为目标值在已经排好序的数中找到合适的位置，        //因为是从后向前比较，并且是与j-1位置的数比较，所以j>0        while (j > 0 && target < arr[j-1]) {            arr[j] = arr[j-1];            j--;        }        arr[j] = target;     }}复制代码

思路： 分而治之的思想，递归实现，将数组每次递归切分成两个小数组，再分别递归，终止条件是小数组的起始下标大于等于结束小标，

递归公式： mergeSort(p,r) = merge(mergeSort(p,q), mergeSort(q+1,r))[p>=r]

合并方法merge：我们能获得两个小数组的下标，申请长度为r-p + 1的临时数组tempArr，同时遍历两个小数组，填充临时数组tempArr,计算哪个小数组有剩，则补到临时数组tempArr后面,最后把临时数组tempArr，整合到原数组arr中

const merge = (arr, start, center, afterCenter, end) => {    const tempArr = new Array(end - start + 1); // 申请一个大小为end - start + 1的临时数组    let i = start, j = afterCenter, k = 0, surplusStart, surplusEnd;    // 切分的小数组，前后下标我们都有，同时遍历，填充临时数组    while (i <= center && j <= end) {        if (arr[i] <= arr[j]) {            tempArr[k++] = arr[i++];        } else {            tempArr[k++] = arr[j++];        }    }    // 获得遍历完后剩下的数组    surplusStart = i;    surplusEnd = center;    if (j <= end) {        surplusStart = j;        surplusEnd = end;    }    while (surplusStart <= surplusEnd) {        tempArr[k++] = arr[surplusStart++];    }    for (let index = 0; index <= end - start; index++) {       arr[start + index] = tempArr[index];    }}const mergeSort_c = (arr, start, end) => {    // 终止条件    if (start >= end)  {        return;    }    const center = Math.floor((start + end) / 2);    // 分而治之，大问题切分成小问题，用递归    mergeSort_c(arr, start, center);    mergeSort_c(arr, center + 1, end);    // 归并    merge(arr, start, center, center + 1, end);}// 入参 arr => 待排序数组， n => 数组大小const mergeSort = (arr, n) => {  mergeSort_c(arr, 0, n-1);}// 运行结果：[1, 2, 3, 3, 7, 8, 9, 11]const handleArr = [11, 8, 3, 9, 7, 1, 2, 3];mergeSort(handleArr, 8);复制代码

思路：分而治之的思想，递归实现，与归并的区别，没有空间换时间,核心就是找到分区临界点，把小于临界点的数值，通过数组交换。换至临界点前面，依次递归

递归公式： quicksort(p,r) = (q = partition = (A, p, r)) + quicksort(p,q-1) + quicksort(q+1,r) [p>=r]

分区方法partition：以该入参数组区间最后一个值为分区点，入参数组第一个数值为起始游标，遍历该区间数组，小于分区点qivot的，交换下标i，j的值， 游标i进一，最终得到的i之前的值都是小于分区点qivot值的，交换分区点与下标r的值，返回分区点下标，那么就分区成功了

// 核心：分区方法const partition = (A, p, r) => {    const qivot = A[r]; // 以该区间最后一个值为分区点    let i = p; // 起始游标    // 遍历该区间数组，小于分区点qivot的，交换下标i，j的值， 游标i进一，最终得到的i之前的值都是小于分区点qivot值的    for (let j = p; j < r; j++) {        if (A[j] < qivot) {            [A[i], A[j]] = [A[j], A[i]];            i++;        }    }    // 交换分区点与下标i的值，那么就分区成功了    [A[i], A[r]] = [A[r], A[i]];    return i; // 返回分区点下标}const quicksort_c = (A, start, end) => {    if (start >= end) { return; } // 终止条件    const qivot = partition(A, start, end); // 分区    // 数组会被分成[start...qivot-1]、qivot、 [qivot+1...end]    quicksort_c(A, start, qivot-1);    quicksort_c(A, qivot+1, end);}// 快速排序const quicksort = (A, n) => {    quicksort_c(A, 0, n-1);}// 运行结果：[1, 2, 3, 3, 7, 8, 9, 11]const handleArr = [11, 8, 3, 9, 7, 1, 2, 3];quicksort(handleArr, 8);复制代码

思路：遍历数组(反向遍历)找到最大值的下标，如arr[0...k]，做一次数组翻转, k会变成第一个下标，然后对整个数组arr[0, end]做一次数组翻转，那么数组最大值便会出现数组的尾部，依次遍历，得到排序好的数组。

// 反转数组const reverse = (arr, end) => {    for (let i = 0, j = end; i < j; i++,j--) {        let temp = arr[i];        arr[i] = arr[j];        arr[j] = temp;    }}var pancakeSort = function(arr) {const ret = []; for (let n = arr.length; n > 1 ;n--) {    let index = 0;    for (let i = 1; i < n; i++) {        if (arr[index] <= arr[i]) {            index = i        }    }    if (index === n - 1) {        continue;    }    reverse(arr, index);    reverse(arr, n - 1);    ret.push(index+1);    ret.push(n);}    return ret;};