栈队列与链表

栈（Stack）

栈是后进先出的线性表，在js中，我们可以看做一个数组，进栈（添加元素）的方法为push()，而出栈（移除元素）的方法为pop()

例如：

const stack = [];
//入栈
stack.push(1);//[1]
stack.push(2);//[1,2]
stack.push(3);//[1,2,3]
//出栈
stack.pop();//[1,2]
stack.pop();//[1]
stack.pop();//[]

队列（Queue）

队列是先进先出的线性表，在js中，我们同样也可以把队列看做一个数组，入队（添加元素）的方法为push()，而出队（移除元素）的方法为shift()

例如：

const queue = [];
//入队
queue.push(1);//[1]
queue.push(2);//[1,2]
queue.push(3);//[1,2,3]
//出对
queue.shift();//[2,3]
queue.shift();//[3]
queue.shift();//[]

链表（ListNode）

在js中，链表是一种类数组对象。关于数组，它的内存空间是连续的，而链表是分散的。所以链表需要前驱和后继来进行关联。其中，链表的数据单位叫结点

注意，为了确保起点结点是能抵达的，我们有时还会设定一个head指针来专门指向链表的开始位置。

我们可以使用对象来模拟它：

const node = {
    value:1,
    next:{
        value:2,
        next:{
            //...
        }
    }
}

书写构造函数

function ListNode(value){
  this.value = value
  this.next = null
}

const node = new ListNode(1)
node.next = new ListNode(2)
console.log(node);//ListNode { value: 1, next: ListNode { value: 2, next: null } }

链表结点的添加

//如果节点不存在，则创建该节点
const node3 = new ListNode(3)
//将node3的后继指向node2（node1的后继）
node3.next = node1.next
//将node1的后继指向node3
node1.next = node3

链表结点的删除

（node1-node3-node2=>node1-node2）：

//找到node1当前的后继（node3）
const target = node1.next
//将此时的node1的后继改为node3的后继（node2）
node1.next = target.next

此时的node3便成为一个无法到达的节点了，所以会被js的垃圾回收自动回收。

链表与数组比较

链表读取数据的时间复杂度为O(n)，因为需要从起始结点遍历到查询的结点为止，数组为O(1)。但相对数组，链表对数据的添加删除更加便捷。