「数据解构」顺序线性表 - pod4g/tool GitHub Wiki

/**
 * 线性表：零个或多个数据元素的有限序列
 *  序列即有序列表，说明线性表是有顺序的
 *
 * 判断一个解构是不是线性表，看2点：
 *  1、是不是零个或多个数据元素的有限序列
 *  2、第一个元素无前驱、最后一个元素无后继、其他元素有且仅有一个前驱和后继
 *
 * 顺序线性表
 */

class ArrayList {
  constructor () {
    this.size = 0
  }

  _getValidIndex (index){
    if(index > this.size){
      throw new Error('下标越界')
    }
    return index < 0 ? this.size + index : index
  }

  // 线性表是否为空，为空返回true，否则返回false
  isEmpty () {
    return this.size === 0
  }

  // 清空线性表
  clear () {
    if(this.isEmpty()){
      return
    }
    let i = 0
    do{
      delete this[i++]
      this.size--
    }while(this.size)
  }

  // 往后追加元素。类似于数组的push
  add (element) {
    this[this.size++] = element
  }

  // 返回index索引处的数据元素
  get (index) {
    return this[this._getValidIndex(index)]
  }

  // 寻找element在线性表中的索引
  find (element) {
    let i = 0, n = this.size, item, ret = -1
    while( i < n ){
      item = this[i++]
      if(item === element){
        return i + ret
      }
    }
    return ret
  }

  // 把element插入指定位置
  insert (index, element) {
    index = this._getValidIndex(index)
    if(index === this.size){
      return this.size
    }
    const elementAtIndex = this[index] // 欢
    this[index++] = element
    this[this.size] = elementAtIndex
    return this.insert(index, elementAtIndex)
  }

  // 删除指定位置的元素。或删除指定element
  delete (index) {
     // TODO:
  }
}


/************************TEST***********************/
var list = new ArrayList()
list.add('北')
list.add('京')
list.add('欢')
list.add('迎')
list.add('你')
list.add('!')

console.log(list)
// list.clear()
// console.log(list)
console.log(list.find('欢'))
console.log(list.find('啊'))
console.log(list.insert(4, '，'))
console.log(list)
// console.log(list.insert(6, '！'))
// console.log(list)