线性表

由同一类型的元素构成有序序列的线性结构。数据存储可以通过数组或者链表实现。

主要操作集：

• 初始化线性表
• 插入新的元素
• 查找已存在元素的位置
• 获取指定位置元素
• 删除某个指定的元素

数组实现存储（数组相对简单，JS 数组存储就可以）

链表

相比数据， 链表数据不需要存储在相邻的内存位置。而是随时添加到内存各个位置，他们直接通过"链"形成一种关联，使之能够快速查到下一个数据。

TIP

就好比火车车厢，车头到车尾，一个车厢连着下一个车厢。能通过 1 号车厢找到 2 号车厢。而链表通过存储了指向下一个节点地址来访问。

基本结构

// 链表节点数据结构
class LinkNode {
  constructor() {
    // 存储数据
    this.data = null;
    // 指向下一个节点
    this.next = null;
  }
}

链表结构以及方法

class Link {
  constructor() {
    this.head = null;
    this._length = 0;
  }

  // 获取链表长度
  get length() {
    return this._length;
  }

  // insert
  push(node) {
    if (this.head != null) {
      let _node = this.head;
      while (_node) {
        if (_node.next != null) {
          _node = node.next;
        } else {
          _node.next = node;
        }
      }
    } else {
      this.head = node;
    }
    this._length++;
  }

  // pop
  pop() {
    if (this.head != null) {
      let _node = this.head;
      let prev = _node;
      while (_node) {
        if (_node.next != null) {
          prev = _node;
          _node = _node.next;
        } else {
          prev.next = null;
          this._length--;
          return _node;
        }
      }
    } else {
      return;
    }
  }

  // 查找节点
  find(data) {
    if (this.head != null) {
      let _node = this.head;
      while (_node) {
        if (_node.data === data) {
          return _node;
        }
        _node = _node.next;
      }
      return;
    }
  }

  // 查找索引
  findIndex(data) {
    if (this.head != null) {
      let _node = this.head;
      let index = 0;
      while (_node) {
        if (_node.data === data) {
          return index;
        }
        _node = _node.next;
        index++;
      }
      return -1;
    }
  }

  // 根据索引获取节点
  indexOf(index) {
    if (this.head != nul) {
      let _node = this.head;
      let idx = 0;
      while (_node) {
        if (idx === index) {
          return _node;
        }
        _node = _node.next;
        idx++;
      }
    }
    return;
  }

  // 移除指定索引节点，并返回移除节点
  // 删除操作将上一个节点next指向删除节点的下一个节点。
  remove(index) {
    if (index === 0) {
      this.head = null;
    } else {
      const node = this.indexOf(index);
      const prevNode = this.indexOf(index - 1);
      prevNode.next = node.next;
      node.next = null;
      return node;
    }
    return;
  }
}

广义表

基于线性表的推广，在线性表中，N个元素都是基本的单元素。而在广义表中，这些元素可以是单元素，也可以是另外一个广义表。

即数据段不再是单纯数据，也可能是指向下一个表。

多重链表

TODO