JS数据结构&算法学习——链表

链表

终于到链表篇了，掌握了链表就大概掌握了半个数据结构

链表是一种线性的存储结构，其节点之间的逻辑关系是通过节点所对应的引用（指针）来进行关联，其链表中的每个节点含有两部分，一个为存储数据（data）的，一个是作为存储引用（next），也就是相邻节点的地址，其实最后一个节点的next为空

生活应用

我们生活中能体现链表的特点的就是列车了，列车一个车厢一个车厢连在一起，乘客是data，而列车的钩子为next，指向下一个列车，我们想在中间添加一个车厢只需要将两节车厢断开中间加入一个新的车厢，并将前一个车厢的钩子指向新的车厢，新的车厢的钩子指向下一个车厢，删除也是如此。

链表 VS 数组

参照之前的数组篇，可以对比一下链表和数组之前的区别

链表与数组同为线性的存储结构，但是有很大的区别如下：

1. 数组的创建需要一段连续的存储空间，因为其物理地址是连续的，而链表的物理地址是可以是不连续的，所以它的创建只需要创建一个头结点即可
2. 由于数组定义的限制所在，若不满足容量需求则需要麻烦的扩容，因为其连续性，扩容很麻烦，甚至来说如果物理地址被占用是无法进行扩容的，而链表可以任意增加容量，也就是说无穷大
3. 数组进行插入和删除操作需要进行对目标元素后的所有元素进行移动，耗费时间极长，虽然JS给我们提供的Array类能帮助我们进行插入及删除等操作，比如说splice，但是底层原理还是不变的，而链表的插入与删除只需要通过修改引用值就可以完成，时间复杂度接近于O(1)
4. 链表进行元素查找过程是需要从头部开始根据引用来寻找目标值，而数组查找元素只需要使用下标即可

链表封装

我们了解了链表的结构与其逻辑后封装了一个链表类如下：

function LinkList() {
    this.head = null
    this.length = 0
    function Node(data, next) {
        this.data = data
        this.next = next
    }
}
复制代码

链表的封装需要考虑整体的结构，在链表类内再定义一个节点类，因为链表中的节点有两个部分即数据和引用，和优先级队列封装类似