js数据结构--列表

发表于 | 更新于 | 阅读次数 1
js算法与数据结构--列表

列表（List）

列表是计算机中一种常见的数据结构，它是一组有序的数据，每个列表中的数据项成为元素。在javascript中，列表中的元素可以是任意数据类型。

1
2
3
4
5
6
7
8
9
10
11
12
function List() {
  this.dataStore = []     // 初始化空数组来保存列表元素
  this.size = 0           // 初始化元素个数为0

  this.append = append
  this.insert = insert
  this.find = find
  this.remove = remove
  this.toString = toString
  this.clear = clear
  this.contains = contains
}

接下来实现这些方法：

append: 列尾添加元素

1
2
3
function append(el) {
  this.dataStore[this.size++] = el
}

insert: 任意位置添加元素

1
2
3
4
5
6
7
8
9
function insert(el, target) {
  var insertPos = this.find(target)
  if (insertPos > -1) {
    this.dataStore.splice(insertPos + 1, 0, el)
    this.size++
    return true
  }
  return false
}

find: 查找元素

1
2
3
4
5
6
7
8
function find(el) {
  for (var i = 0, len = this.dataStore.size; i < len; i++) {
    if (this.dataStore[i] === el) {
      return i
    }
  }
  return i
}

remove: 删除元素

1
2
3
4
5
6
7
8
9
function remove(el) {
  var foundAt = this.find(el)
  if (foundAt > -1) {
    this.dataStore.splice(foundAt, 1)
    --this.size
    return true
  }
  return false
}

toString: 显示元素

1
2
3
function toString() {
  return this.dataStore
}

clear: 清空元素

1
2
3
4
5
function clear() {
  delete this.dataStore
  this.dataStore = []
  this.size = this.pos = 0
}

contains: 是否包含元素

1
2
3
4
function contains(el) {
  // return this.data.indexOf(el) > -1
  return this.dataStore.includes(el)
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
function List() {
  this.dataStore = []     // 初始化空数组来保存列表元素
  this.size = 0           // 初始化元素个数为0

  this.append = append
  this.insert = insert
  this.find = find
  this.remove = remove
  this.toString = toString
  this.clear = clear
  this.contains = contains
}

function append(el) {
  this.dataStore[this.size++] = el
}

function insert(el, target) {
  var insertPos = this.find(target)
  if (insertPos > -1) {
    this.dataStore.splice(insertPos + 1, 0, el)
    this.size++
    return true
  }
  return false
}

function find(el) {
  for (var i = 0, len = this.dataStore.size; i < len; i++) {
    if (this.dataStore[i] === el) {
      return i
    }
  }
  return i
}

function remove(el) {
  var foundAt = this.find(el)
  if (foundAt > -1) {
    this.dataStore.splice(foundAt, 1)
    --this.size
    return true
  }
  return false
}

function toString() {
  return this.dataStore
}

function clear() {
  delete this.dataStore
  this.dataStore = []
  this.size = this.pos = 0
}

function contains(el) {
  // return this.data.indexOf(el) > -1
  return this.dataStore.includes(el)
}

参考：简书 JS中的算法与数据结构——列表(List)