Skip to content

Latest commit

 

History

History
312 lines (259 loc) · 7.34 KB

2018-2-21-list.md

File metadata and controls

312 lines (259 loc) · 7.34 KB

再剖析数据结构与算法 javascript 描述--列表（List）

列表的定义

列表是一组有序的数据，每个列表中的数据项称为元素。在 JavaScript 中，列表中的元素 可以是任意数据类型。列表中可以保存多少元素并没有事先限定，实际使用时元素的数量 受到程序内存的限制。

当不需要在一个很 长的序列中查找元素，或者对其进行排序时，列表显得尤为有用。反之，如果数据结构非 常复杂，列表的作用就没有那么大了。

完整列表数据类型

属性/方法 描述
listSize(属性) 列表的元素个数
pos(属性) 列表的当前位置
length(属性) 返回列表中元素的个数
clear(方法) 清空列表中的所有元素
toString(方法) 返回列表的字符串形式
getElement(方法) 返回当前位置的元素
insert(方法) 在现有元素后插入新元素
append(方法) 在列表的末尾添加新元素
remove(方法) 从列表中删除元素
front(方法) 将列表的当前位置设移动到第一个元素
end(方法) 将列表的当前位置移动到最后一个元素
prev(方法) 将当前位置后移一位
next(方法) 将当前位置前移一位
currPos(方法) 返回列表的当前位置
moveTo(方法) 将当前位置移动到指定位置

List 类实现

根据以上定义的方法，实现自己的列表类，定义一个基本类 List，基本代码如下：

class List {
  constructor() {
    this.listSize = 0
    this.pos = 0
    this.dataStore = []
  }
}

定义添加元素的append方法，该方法给列表的下一个位置增加一个新的元素，这 个位置刚好等于变量 listSize 的值，片段代码如下：

  // 给列表增加元素
  append(elm) {
    this.dataStore[this.listSize++] = elm
  }

定义查找元素位置的find方法，返回值为元素的位置，如果不存在则返回-1，片段代码如下：

  // 从列表查找某一元素
  find(elm) {
    for (let v of Object.keys(this.dataStore)) {
      if (elm === this.dataStore[v]) {
        return Number(v)
      }
    }
    return -1
  }

定义删除remove方法，先根据上面定义的find方法找出元素的位置，然后通过 splice 来删除，片段代码如下：

  // 从列表中删除元素
  remove(elm) {
    let foundAt = this.find(elm)
    if (foundAt > -1) {
      this.dataStore.splice(foundAt, 1)
        --this.listSize
      return true
    }
    return false
  }

定义列表计算多少个元素length方法以及显示列表中的元素toString方法，片段代码如下：

  // 列表中有多少个元素
  length() {
    return this.listSize
  }

  // 显示列表中的元素
  toString() {
    return this.dataStore
  }

定义向列表插入一个元素的insert方法，主要也是先通过find方法找到元素位置，然后根据 splice 来插入元素，片段代码如下：

  // 向列表中插入一个元素
  insert(elm, after) {
    var insertPos = this.find(after)
    if (insertPos > -1) {
      this.dataStore.splice(insertPos + 1, 0, elm)
        ++this.listSize
      return true
    }
    return false
  }

定义清空列表的clear方法，主要将初始化定义的变量全部清空，片段代码如下：

  // 清空列表中所有的元素
  clear() {
    this.dataStore = []
    this.listSize = this.pos = 0
  }

判断给定值是否在列表中，通过定义contains方法来区分，片段代码如下：

  // 判断给定值是否在列表中
  contains(elm) {
    for (let v of Object.keys(this.dataStore)) {
      if (elm === this.dataStore[v]) {
        return true
      }
    }
    return false
  }

定义一组方便用户遍历列表的方法，可以访问列表中任意位置的元素，片段代码如下：

  // 将列表的当前位置设移动到第一个元素
  front() {
    this.pos = 0
  }

  // 将列表的当前位置移动到最后一个元素
  end() {
    this.pos = this.listSize - 1
  }

  // 将当前位置后移一位
  prev() {
    if (this.pos > 0) {
      --this.pos
    }
  }

  // 将当前位置前移一位
  next() {
    if (this.pos < this.listSize - 1) {
      ++this.pos
    }
  }

  // 返回列表的当前位置
  currPos() {
    return this.pos
  }

  // 将当前位置移动到指定位置
  moveTo(position) {
    this.pos = position
  }

  // 返回当前位置的元素
  getElement() {
    return this.dataStore[this.pos]
  }

以下是具体使用代码：

// 示例如下
let names = new List()
names.append('Clayton')
names.append('Raymond')
names.append('Cynthia')
names.append('Jennifer')
names.append('Bryan')
names.append('Danny')

names.length() // 6
names.toString() // ["Clayton", "Raymond", "Cynthia", "Jennifer", "Bryan", "Danny"]
names.contains('wq') // false
names.getElement() // Clayton

names.next()
names.getElement() // Raymond

完整代码如下：

class List {
  constructor() {
    this.listSize = 0
    this.pos = 0
    this.dataStore = []
  }

  // 给列表增加元素
  append(elm) {
    this.dataStore[this.listSize++] = elm
  }

  // 从列表查找某一元素
  find(elm) {
    for (let v of Object.keys(this.dataStore)) {
      if (elm === this.dataStore[v]) {
        return Number(v)
      }
    }
    return -1
  }

  // 从列表中删除元素
  remove(elm) {
    let foundAt = this.find(elm)
    if (foundAt > -1) {
      this.dataStore.splice(foundAt, 1)
      --this.listSize
      return true
    }
    return false
  }

  // 列表中有多少个元素
  length() {
    return this.listSize
  }

  // 显示列表中的元素
  toString() {
    return this.dataStore
  }

  // 向列表中插入一个元素
  insert(elm, after) {
    var insertPos = this.find(after)
    if (insertPos > -1) {
      this.dataStore.splice(insertPos + 1, 0, elm)
      ++this.listSize
      return true
    }
    return false
  }

  // 清空列表中所有的元素
  clear() {
    this.dataStore = []
    this.listSize = this.pos = 0
  }

  // 判断给定值是否在列表中
  contains(elm) {
    for (let v of Object.keys(this.dataStore)) {
      if (elm === this.dataStore[v]) {
        return true
      }
    }
    return false
  }

  // 将列表的当前位置设移动到第一个元素
  front() {
    this.pos = 0
  }

  // 将列表的当前位置移动到最后一个元素
  end() {
    this.pos = this.listSize - 1
  }

  // 将当前位置后移一位
  prev() {
    if (this.pos > 0) {
      --this.pos
    }
  }

  // 将当前位置前移一位
  next() {
    if (this.pos < this.listSize - 1) {
      ++this.pos
    }
  }

  // 返回列表的当前位置
  currPos() {
    return this.pos
  }

  // 将当前位置移动到指定位置
  moveTo(position) {
    this.pos = position
  }

  // 返回当前位置的元素
  getElement() {
    return this.dataStore[this.pos]
  }
}