静态链表

对于没有指针和对象引用功能的语言，像 Basic、Fortran 不能用之前的方式来实现链表了。有人提出用数组来描述单链表，数组的元素由两个数据域组成：data和cur。data用来存放链表的数据，cur相当于 next 指针。

我们把这种用数组描述的链表叫做静态链表

静态链表表示法

静态链表表示法也叫游标实现法。数组的第一个元素和最后一个元素作为特殊元素处理，不存数据。

• 数组的第一个元素的 cur 用来存放备用链表第一个结点的下标
  在下图1中，因为整个数组都没有使用过，也就是说整个链表都是备用链表，它存放的 cur 为 1。下图2中，数组的第 7 个元素为空闲空间，所以存放的是 7

• 数组的最后一个元素存放第一个有数值的元素的下标，相当于头结点
  在下图1中，因为数组为空，所以为 0；下图2中，第一个有数值的元素为 1，所以为 1

• 静态链表的最后一个元素（非数组的最后元素）的游标为0，表示链尾

• 数组的第一个元素的 cur 为 0 表示链表已满

静态链表操作

初始化静态链表

export default class StaticLinkedList {
  constructor() {
    this.space = [] //静态链表使用一维数组space来表示
    this.length = 0 //链表的长度
    this.MAX_SIZE = 0 //申请的空间
  }

  /**
   * 静态链表初始化
   * @param {*} maxsize 申请的空间
   * @returns
   */
  init(maxsize) {
    //异常处理，由于数组第一个元素和最后一个元素不存放数据，所以申请的空间长度至少是3或以上
    if (maxsize < 3) {
      throw new Error('申请的空间至少是3或以上')
    }

    let i = 0
    //因为静态链表最后一个元素不用，所以这里 i < maxsize -1
    //数组第一个元素的cur用来存放备用链表第一个节点的下标
    //初始化时整个数组都没有被使用过，整个链表都是备用链表，所以space[0].cur = 1
    //其余每项的 cur 都存放它的下一个元素，处理逻辑一样
    for (i; i < maxsize - 1; i++) {
      this.space.push({
        cur: i + 1,
        data: null,
      })
    }
    //数组最后一个元素的cur用来存放第一个插入元素的下标，相当于头结点
    //因为是一个空链表，所以存放的下标是0
    this.space[maxsize - 1] = {
      cur: 0,
      data: null,
    }
    //申请的空间
    this.MAX_SIZE = maxsize
    return true
  }
}

malloc 和 free

使用静态链表插入和删除元素，与动态链表不一样，需要解决的问题是：**如何用静态链表模拟动态链表结构的存储空间分配问题，需要时申请，无用时释放。**在动态链表中，节点的申请和释放分别借用malloc和free函数实现，我们需要手动实现这两个函数。

malloc

为了辨明数组中哪些分量未被使用，解决的办法是将所有未被使用过的以及被删除的分量用游标链成一个备用链表，每当要插入时，便可从备用链表中取得第一个节点作为待插入的新节点。

如图，我们要插入一个元素，先找到备用链表第一个元素的位置，也就是space[0].cur = 7的位置，然后该分量被使用了，备用链表的第一个元素就变成了它的下一个元素，也就是space[0].cur = space[7].cur

代码实现如下：

/**
 * 模拟申请内存操作
 * 在静态链表中，每次插入数据都是从备用链表上取得第一个结点作为待插入的新结点
 * @returns
 */
_malloc_ssl() {
  //取出备用链表的第一个元素索引，也就是数组第一个元素的 cur
  let i = this.space[0].cur
  //如果 i 不存在，表示链表已满
  if (i) {
    //由于要拿出一个分量来使用了，所以我们就得把它的下一个分量用来做备用
    this.space[0].cur = this.space[i].cur
  }
  //返回备用链表第一个结点的下标作为待使用的分量
  return i
}

free

释放内存的过程如下图，space[1]位置的甲离开了，如果有新的元素要进来，优先考虑这个位置，而且我们要把备用链表给串起来。所以space[1].cur = space[0].cur; space[0].cur = 1

代码实现如下：

/**
 * 模拟释放内存
 * @param {*} index
 * @returns
 */
_free_ssl(index) {
  //把下标为0，即存放备用链表第一个元素的cur分量赋值给第index个元素
  this.space[index].cur = this.space[0].cur
  //data置为null，表示删除了
  this.space[index].data = null
  //由于第index个元素释放出来了，所以下标为0的元素的cur为index
  this.space[0].cur = index
}

整表创建

整表创建需要注意的是以下细节：

1. 如果表满了，需要设置数组第一个元素的 cur 为 0
2. 设置头结点的 cur 为链表第一个元素的下标，即 1
3. 设置链尾，即最后一个链表元素的 cur 为 0

代码实现如下：

/**
 * 链表整表创建，尾插法
 * @param {*} n
 * @returns
 */
create(n) {
  if (n < 0 || n > this.MAX_SIZE - 2) {
    return false
  }
  let i = 0,
    j
  //循环创建节点
  for (i; i < n; i++) {
    j = this._malloc_ssl()
    this.space[j].data = Number.parseInt(Math.random() * 10 + 1)

    //如果创建的是最后一个节点，需要设置 cur 为 0
    if (j == n) {
      this.space[j].cur = 0
    }
    this.length++
  }
  //设置头结点
  this.space[this.MAX_SIZE - 1].cur = 1
  //如果链表满了，需要设置第一个元素的cur为0
  if (this.length == this.MAX_SIZE - 2) {
    this.space[0].cur = 0
  }
  return true
}

清空链表

清空链表比较简单，根据头结点去遍历整个链表，依次释放即可

clear() {
  //最后一个元素下标，也就是找到头结点
  let cursor = this.MAX_SIZE - 1
  //循环清空所有的节点
  while (this.space[cursor].cur !== 0) {
    this._free_ssl(cursor)
    cursor = this.space[cursor.cur]
  }
  this.length = 0
}

插入操作

插入操作，在表头、表尾和中间插入基本都是一样的。我们可以分别讨论一下：

表尾插入：push

在表尾插入元素，比较简单，但是陷阱也挺多的，不要把链表的插入当成了数组的插入。我们接上图，甲从链表中出去后，再次插入到链表，结果如下：

_malloc_ssl给它分配到了space[1]的位置，有两个地方发生了变化：

因为顺序变成了乙->丙->丁->甲，所以甲的 cur 应该指向之前丁的 cur；丁的 cur 指向甲所在的位置。

中间插入：insert

那么在链表中间插入呢，比如插入的 index 是 3，也就是在丁之前插入，我们可以看下图：

顺序变成了乙->丙->甲->丁，所以甲的 cur 应该指向之前丙的 cur；丙的 cur 指向甲的位置

表头插入：unshift

表头插入逻辑是一样的，比如 index 是 1，回到了最开始的顺序：甲->乙->丙->丁，所以甲的 cur 应该指向已，因为已是第一个元素，所以它实际指向的是头结点的 cur；头结点的 cur 指向甲的位置，回到了初始时候的样子。

所以我们的核心逻辑如下：

//最后一个元素下标，也就是找到头结点
let i = 1, cursor = this.MAX_SIZE - 1
//找到第index元素的前一个元素
for (i; i <= index - 1; i++) {
    cursor = this.space[cursor].cur
}
//获得空闲分量的下标，也就是新插入元素的下标
let new_node_index = this._malloc_ssl()

//新元素的 cur 应该指向 index 前一个元素的 cur
this.space[new_node_index].cur = this.space[cursor].cur
//把新元素的下标赋值给 index 前一个元素
this.space[cursor].cur = new_node_index

整个过程跟之前的动态链表其实是一样的，只不过表示方式不同而已。

insert(index, elem) {
  //异常处理，可以插入的范围：1到最后一个元素+1，即可以插入到表尾
  if (index < 1 || index > this.length + 1) {
    return false
  }
  //先找到头结点
  let i = 1,
    cursor = this.MAX_SIZE - 1,
    new_node_index = this._malloc_ssl()
		
  //内存已满，插入不进去
  if (!new_node_index) {
    return false
  }

  //插入元素，表长+1
  this.space[new_node_index].data = elem
  this.length++

  //找到第index元素的前一个元素，如果 index 为 1，即插入到表头，它的前一个元素就是头结点了
  for (i; i <= index - 1; i++) {
    cursor = this.space[cursor].cur
  }

  //新元素的 cur 应该指向 index 前一个元素的 cur
  this.space[new_node_index].cur = this.space[cursor].cur
  //把新元素的下标赋值给 index 前一个元素
  this.space[cursor].cur = new_node_index

  //如果链表满了，需要设置第一个元素的cur为0，表示已满
  if (this.length == this.MAX_SIZE - 2) {
    this.space[0].cur = 0
  }
}

删除操作

在前面的free操作我们举了一个例子，甲删除后，头结点指向甲的下一个元素。所以我们删除 index 位置的元素，实际操作就是找到 index 的前一个节点，它的 cur 指向 index 的后一个节点。

delete(index) {
  //异常处理
  if (index < 1 || index > this.length) {
    return false
  }
  //找到 index 的前一个元素
  let i = 1,
    cursor = this.MAX_SIZE - 1
  for (i; i <= index - 1; i++) {
    cursor = this.space[cursor].cur
  }
  //第index个元素的下标
  i = this.space[cursor].cur
  //前一个元素的cur指向index元素的cur，即表示 index已经删除了，前一个元素指向它后一个元素
  this.space[cursor].cur = this.space[i].cur
  this._free_ssl(index)
  this.length--
  return true
}