轻键快码

用 Javascript 实现数据类型列表

轻键快码 Javascript数据结构列表

在计算机科学中,列表或序列是一种抽象数据类型,表示可数数量的有序值,其中相同的值可能多次出现。 列表的实例是有限序列的数学概念的计算机表示; 列表的(潜在的)无限模拟是流。列表是容器的基本示例,因为它们包含其他值。 如果相同的值出现多次,则每次出现都被视为不同的项目。wiki

列表是一种十分常用的数据类型,如排行榜,待办事项表, 购物车清单等。在存储数据量不大,不需要在很长的序列中查找或者排序其中的元素时列表就十分适合。 列表中的数据称为元素,且他们的数据类型不一定相同,在 Javascript 中可以用一个数据来存储他们。每一个列表应该有一个表示元素个的 listSize 属性,以及可以增加,删除,插入,查找元素等方法。

首先定义一个列表类

class List {
  constructor () {
    this.datas = [] // 用于存储数据的数组
    this.listSize = 0 // 表示列表大小的值
    this.index = 0 // 表示列表当前位置的值
  }
}

为列表类添加基本方法

class List {
  ......
  // 清空列表的方法
  clear () {
    delete this.datas
    this.datas = []
    this.listSize = this.index = 0
  }
  // 返回列表元素个数的方法
  length () {
    return this.listSize
  }
  // 显示列表中元素的方法
  elements () {
    return this.datas.join(', ')
  }
  // 返回列表中当前位置元素的方法
  current () {
    return this.datas[this.index]
  }
  // 向列表中添加元素的方法
  append (element) {
    if (!element) return
    this.datas[this.listSize++] = element
  }
  // 向列表中插入元素的方法
  insert (element, after) {
    const pos = this.findIndex(element)
    if (pos > -1) {
      this.datas.splice(pos, 0, element)
      this.listSize += 1
      return true
    }
    return false
  }
  // 删除列表中元素的方法
  remove (element) {
    const index = this.findIndex(element)
    if (index > -1) {
      this.datas.splice(index, 1)
      this.listSize -= 1
      return true
    }
    return false
  }
  // 查找列表元素位置的方法
  findIndex (element) {
    for (let i = 0; i < this.datas.length; i++) {
      if (this.datas[i] === element) {
        return i
      }
    }
    return -1
  }
  // 判断元素是否存在列表中的方法
  contains (element) {
    if (this.datas.contains) {
      return this.datas.contains(element)
    } else {
      for (let i = 0; i < this.datas.length; i++) {
        if (element === this.datas[i]) {
          return true
        }
      }
      return false
    }
  }
}

为列表类添加遍历方法

class List {
  ......
  // 返回列表中第一个元素的方法
  first () {
    return this.datas[0]
  }
  // 返回列表中最后一个元素的方法
  last () {
    return this.datas[this.listSize]
  }
  // 将列表的位置向前移动一位,并返回当前位置
  prev () {
    this.index -= 1
    return this.position()
  }
  // 将列表的位置向后移动一位,并返回当前位置
  next () {
    if (this.index < this.listSize) {
      this.index += 1
    }
    return this.position()
  }
  // 判断是否有下一个元素
  hasNext () {
    return this.index < this.listSize
  }
  // 判断是否有上一个元素
  hasPrev () {
    return this.index > 0
  }
  // 将列表的位置移动到第一位
  moveFront () {
    this.index = 0
  }
  // 将列表的位置移动到最后一位
  moveEnd () {
    this.index = this.listSize - 1
  }
  // 将列表的位置移动到指定位置
  moveTo (pos) {
    if (pos >= 0 && pos < this.listSize) {
      this.index = pos
    }
  }
  // 返回列表当前的位置
  position () {
    return this.index + 1
  }
}

定义好列表类之后,测试以下

const names = new List()
names.append('Perry')
names.append('Genoveva')
names.append('Lavina')
names.append('Verlie')
names.append('Ernesto')
names.append('Sigrid')

console.log(names.elements()) // Perry, Genoveva, Lavina, Verlie, Ernesto, Sigrid

for (names.moveFront(); names.hasNext(); names.next()) {
  console.log(names.current(), names.position())
}
// Perry 1
// Genoveva 2
// Lavina 3
// Verlie 4
// Ernesto 5
// Sigrid 6

names.clear()
console.log(names.length()) // 0

一个基本的列表类就实现了,如果数据的顺序不重要,也不必对数据进行查找且数据量不大的话,用列表存储数据就在适合不过了。