JavaScript中最常见的集合型数据结构是数组,数组的特点是存储一系列同类数据,且是连续的,可通过索引访问元素,也有丰富的操作方法方便我们对其进行处理。

虽然它能够胜任几乎一切操作,但如果更细化地看,数组不是没有缺点,比如,它必须要分配一段连续的存储空间,若空间不够,则无法分配,而且,对于插入或删除元素,它的效率是较低的,它需要移动插入或者删除元素位置之后的所有元素才能达到目的。

有没有可以弥补这些缺陷的方法呢?

正是本文要介绍的链表了。

介绍链表

链表,顾名思义,元素像一条链子一样彼此连接,既然彼此连接,就要有相互连接的纽带,这个纽带起到的作用就是,即使不连续,我也能根据纽带找到你,再者,如果两个元素之间增加一个元素,或者从链表中删除一个元素,都可以通过解除原有关系,建立新的关系就好了,而不需要其他任何的成本。

有了大概了解之后,怎么使用链表呢?JavaScript语言本身并没有这种数据结构,需要我们自定义,下面就来看看如何定义。

定义链表

怎么开始?

在定义之前,我们可以先捋一捋头绪,链表需要什么?

  • 既然也是一系列的元素,就需要有个数——count
  • 要从零开始建立关系,就需要有表头元素——head
  • 要有一种结构来进行节点定义——node
  • 要获取链表大小——size
  • 要能够对链表进行操作——增(push)、删(pop)、查(get)、插(insert)

下面就来逐一定义:

链表骨架

class LinkList{
    constructor(){
        this.count = 0
        this.head = undefined
    }
}

节点

class Node{
    constructor(element){
        this.element = element
        this.next = undefined
    }
}