栈（Stack）——只用 pop 和 push 完成增删的“数组”

栈是一种后进先出(LIFO，Last In First Out )的数据结构。
我们可以把它想象成小时候学校门口小卖部里，摞满了冰淇淋的方形大冰柜。
小卖部老板往里面摆置冰淇淋的时候，最先摆进去的会落在冰柜的底部，最后摆置进去的留在冰柜的顶部。如果这时候咱们去买冰淇淋，老板就会把冰柜顶部的那个取出来给我们。在冰淇淋不断被取出的这个过程里，越是后来放进去的，越是先被取出来；越是先放进去的，越是最后被取出来。这个过程，就是所谓的“后进先出”：

我们看到这个过程有两个特征：

只允许从尾部添加元素
只允许从尾部取出元素
对应到数组的方法，刚好就是 push 和 pop。因此，我们可以认为在 JavaScript 中，栈就是限制只能用 push 来添加元素，同时只能用 pop 来移除元素的一种特殊的数组。
除了 pop 和 push 之外，栈相关的面试题中往往还会涉及到取栈顶元素的操作。所谓栈顶元素，从图上我们不难看出来，实际上它指的就是数组尾部的元素。

下面我们基于数组来实现一波栈的常用操作，完成“放置冰淇淋”和“卖冰淇淋”的过程

// 初始状态，栈空
const stack = []  
// 入栈过程
stack.push('东北大板')
stack.push('可爱多')
stack.push('巧乐兹')
stack.push('冰工厂')
stack.push('光明奶砖')

// 出栈过程，栈不为空时才执行
while(stack.length) {
    // 单纯访问栈顶元素（不出栈）
    const top = stack[stack.length-1]
    console.log('现在取出的冰淇淋是', top)  
    // 将栈顶元素出栈
    stack.pop()
}

丢到控制台运行，冰淇淋就会按照后进先出的顺序被取出：

VM97:14 现在取出的冰淇淋是 光明奶砖
VM97:14 现在取出的冰淇淋是 冰工厂
VM97:14 现在取出的冰淇淋是 巧乐兹
VM97:14 现在取出的冰淇淋是 可爱多
VM97:14 现在取出的冰淇淋是 东北大板

队列（Queue）——只用 push 和 shift 完成增删的“数组”

队列是一种先进先出（FIFO，First In First Out）的数据结构。
它比较像咱们去肯德基排队点餐。先点餐的人先出餐，后点餐的人后出餐：

这个过程的规律也很明显：

只允许从尾部添加元素
只允许从头部移除元素

也就是说整个过程只涉及了数组的 push 和shift方法。
在栈元素出栈时，我们关心的是栈顶元素（数组的最后一个元素）；队列元素出队时，我们关心的则是队头元素（数组的第一个元素）。
下面我们基于数组来实现一波队列的常用操作，完成“小册姐排队”和“小册姐取餐”的过程：

const queue = []  
queue.push('小册一姐')
queue.push('小册二姐')
queue.push('小册三姐')  
  
while(queue.length) {
    // 单纯访问队头元素（不出队）
    const top = queue[0]
    console.log(top,'取餐')
    // 将队头元素出队
    queue.shift()
}

把上面代码丢进控制台运行，我们可以看到小册姐一个接一个地乖乖去取餐了：

VM385:9 小册一姐 取餐
VM385:9 小册二姐 取餐
VM385:9 小册三姐 取餐

链表

链表和数组相似，它们都是有序的列表、都是线性结构（有且仅有一个前驱、有且仅有一个后继）。不同点在于，链表中，数据单位的名称叫做“结点”，而结点和结点的分布，在内存中可以是离散的。

与数组不同！数组在内存中是一块连续的内存！

而链表中的结点，则允许散落在内存空间的各个角落里。一个内容为1->2->3->4->5的链表，在内存中的形态可以是散乱如下的：

正是由于数组中的元素是连续的，每个元素的内存地址可以根据其索引距离数组头部的距离来计算出来。因此对数组来说，每一个元素都可以通过数组的索引下标直接定位。但是对链表来说，元素和元素之间似乎毫无内存上的瓜葛可言。就比如说咱们图上这种情况，1、2、3、4、5各据山头，站在元素1的坑位里，我们对元素2、3、4、5的内存地址一无所知，连遍历都没法遍历，那么如果想去便利，操作元素要怎么做呢？

如果没有关联，就创造关联！
在链表中，每一个结点的结构都包括了两部分的内容：数据域和指针域。
JS 中的链表，是以嵌套的对象的形式来实现的：

{
    // 数据域
    val: 1,
    // 指针域，指向下一个结点
    next: {
        val:2,
        next: ...
    }
}

数据域存储的是当前结点所存储的数据值(val)
指针域则代表下一个结点（后继结点）的引用(next)

有了 next 指针来记录后继结点的引用，每一个结点至少都能知道自己后面的同学是哪位了，原本相互独立的结点之间就有了如下的联系：

我们把这个关系给简化一下：

要想访问链表中的任何一个元素，我们都得从起点结点开始，逐个访问 next，一直访问到目标结点为止。为了确保起点结点是可抵达的，我们有时还会设定一个 head 指针来专门指向链表的开始位置（哨兵模式）：

以上，就是链表的基本形态啦。

链表结点的创建

自己根据链表的特性实现一个链表节点、链表！
链表节点类

// 链表节点类
class LinkNode<T>{
    val: T;
    next: LinkNode<T> | null = null;
    constructor(val: T) {
        this.val = val
    }
}

自己实现的一个链表类（增删查的操作，都是对链表循环啦！）

// 链表
class LinkedList<T> {
    head: LinkNode<T> | null = null; // 头部
    append(node: LinkNode<T>) {
        if (this.head) {
            // 如果有头部，但是不能确认链表下面到底有多少，只能遍历去找到最后一个，然后append
            let n = this.head
            while (n.next) {
                n = n.next
            }
            n.next = node;
        } else {
            // 如果头部没有，那么就当作头部
            this.head = node;
        }
    }
    delete(val) {
        let temp: any = {
            val: null,
            next: this.head
        }
        while (temp && temp.next) {
            if (temp.next.val === val) {
               if (temp.next === this.head) {//如果是头节点，那么需要换一下头结点
                    this.head = temp.next.next
                } else {
                    temp.next = temp.next.next || null
                }
            }
            temp = temp.next
        }
    }
    // 找到第一个值能匹配的节点
    find(val: T): LinkNode<T> | null {
        let f = this.head;
        if (!f) return null;
        while (f.val !== val && f.next) {
            f = f?.next
        }
        return f;
    }
    print(): void {
        if (this.head) {
            let last = this.head;
            let ret: Array<LinkNode<T>> = []
            while (last.next) {
                ret.push(last)
                last = last.next
            }
            // 最后一项next为空，需要手动放入
            ret.push(last)
            console.log(ret);
        } else {
            console.log('empty')
        }
    }
}

测试代码

const ll = new LinkedList<number>()
const node1 = new LinkNode<number>(1)
const node2 = new LinkNode<number>(2)
const node3 = new LinkNode<number>(3)
const node4 = new LinkNode<number>(4)
console.log('初始');
ll.print()
ll.append(node1)
ll.append(node2)
ll.append(node3)
ll.append(node4)
console.log('添加');
ll.print()
console.log('删除');
ll.delete(1)
ll.print()

执行结果

初始
empty
添加
[
  LinkNode { next: LinkNode { next: [LinkNode], val: 2 }, val: 1 },
  LinkNode { next: LinkNode { next: [LinkNode], val: 3 }, val: 2 },
  LinkNode { next: LinkNode { next: null, val: 4 }, val: 3 },
  LinkNode { next: null, val: 4 }
]
删除
[
  LinkNode { next: LinkNode { next: [LinkNode], val: 3 }, val: 2 },
  LinkNode { next: LinkNode { next: null, val: 4 }, val: 3 },
  LinkNode { next: null, val: 4 }
]

链表和数组的辨析

在大多数的计算机语言中，数组都对应着一段连续的内存。如果我们想要在任意位置删除一个元素，那么该位置往后的所有元素，都需要往前挪一个位置；相应地，如果要在任意位置新增一个元素，那么该位置往后的所有元素也都要往后挪一个位置。

我们假设数组的长度是 n，那么因增加/删除操作导致需要移动的元素数量，就会随着数组长度 n 的增大而增大，呈一个线性关系。所以说数组增加/删除操作对应的复杂度就是 O(n)。

但 JS 中不一定是。
JS比较特别。如果我们在一个数组中只定义了一种类型的元素，比如：

const arr = [1,2,3,4]

它是一个纯数字数组，那么对应的确实是连续内存。
但如果我们定义了不同类型的元素：

const arr = ['haha', 1, {a:1}]

它对应的就是一段非连续的内存。此时，JS 数组不再具有数组的特征，其底层使用哈希映射分配内存空间，是由对象链表来实现的。

说起来有点绕口，但大家谨记“JS 数组未必是真正的数组”即可。

何谓“真正的数组”？在各大教材（包括百科词条）对数组的定义中，都有一个“存储在连续的内存空间里”这样的必要条件。

因此在本文中，我们描述的“数组”就是符合这个定义的数组。面试时，若考到数组和链表的辨析，大家也沿着这个思路往下说，是没有问题的。如果能够说出 JS 数组和常规数组的不同，那就是锦上添花了。

相对于数组来说，链表有一个明显的优点，就是添加和删除元素都不需要挪动多余的元素。但是查找需要沿着链表一个个的去找，直到能找到匹配的！

高效的增删操作

在链表中，添加和删除操作的复杂度是固定的

不管链表里面的结点个数 n 有多大，只要我们明确了要插入/删除的目标位置，那么我们需要做的都仅仅是改变目标结点及其前驱/后继结点的指针指向。因此我们说链表增删操作的复杂度是常数级别的复杂度，用大 O 表示法表示为 O(1)。

麻烦的访问操作

但是链表也有一个弊端：当我们试图读取某一个特定的链表结点时，必须遍历整个链表来查找它。

比如说我要在一个长度为 n（n>10）的链表里，定位它的第 10 个结点，我需要这样做：

// 记录目标结点的位置
const index = 10  
// 设一个游标指向链表第一个结点，从第一个结点开始遍历
let node = head  
// 反复遍历到第10个结点为止
for(let i=0;i<index&&node;i++) {
    node = node.next
}

随着链表长度的增加，我们搜索的范围也会变大、遍历其中任意元素的时间成本自然随之提高。这个变化的趋势呈线性规律，用大 O 表示法表示为 O(n)。

但在数组中，我们直接访问索引、可以做到一步到位，这个操作的复杂度会被降级为常数级别(O(1))

总结一下，链表适用于增删操作较多的场景，而标准数组则适用于查找较多的场景！
链表的插入/删除效率较高，而访问效率较低；数组的访问效率较高，而插入效率较低

目录CONTENT

从JavaScript的角度看一些简单的数据结构！