Skip to main content

列表的定义及实现

JS 如何创建一个简单的列表类？以下将描述如何实现该抽象数据类型（ADT）

一、 什么是列表​

列表是一组有序的数据，每个列表中的数据项称为元素。在 JS 中，列表的元素可以是任意数据类型，且列表保存多少元素没有事先限定。

要设计列表的抽象数据类型，我们需要列出列表的属性及方法：

1、列表的属性​

属性名作用
listSize列表的元素个数
pos列表的当前位置
length返回列表中元素的个数

2、列表的方法​

方法名作用
clear清空列表中的所有元素
toString返回列表的字符串形式
getElement返回当前位置的元素
insert在现有元素后插入新元素
append在列表的末尾添加新元素
remove从列表中删除元素
front将列表的当前位置移动到第一个元素
end将列表的当前位置移动到最后一个元素
prev将当前位置后移一位
next将当前位置前移一位
hasNext判断后一位
hasPrev判断前一位
currPos返回列表的当前位置
moveTo将当前位置移动到指定位置

二、列表的实现​

我们先从定义构造函数开始实现

function List() {
  this.listSize = 0
  this.pos = 0
  this.dataStore = [] // 初始化一个空数组来保存列表元素
  this.clear = clear
  this.find = find
  this.toString = toString
  this.insert = insert
  this.append = append
  this.remove = remove
  this.front = front
  this.end = end
  this.prev = prev
  this.next = next
  this.hasNext
  this.hasPrev
  this.length = length
  this.currPos = currPos
  this.moveTo = moveTo
  this.getElement = getElement
  this.contains = contains
}

1、append 方法​

给列表添加元素

function append(element) {
  this.dataStore[this.listSize++] = element
}

当新元素就位后，变量 listSize 加 1。

2、find 方法​

在列表中查找某一元素。

function find(element) {
  for (var i = 0; i < this.dataStore.length; ++i) {
    if (this.dataStore[i] == element) {
      return i
    }
  }
  return -1
}

3、remove 方法​

从列表中删除元素。

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

remove() 方法中使用 find() 方法返回的位置对数组 dataStore 进行截取，数组改变后，将变量 listSize 的值减 1。

如果元素删除成功，返回 true，否则返回 false。

4、length 方法​

返回列表中元素个数。

function length() {
  return this.listSize
}

5、toString 方法​

显示列表中的元素。

function toString() {
  return this.dataStore
}

下面对以上形成的类进行一个简短的测试：

var names = new List()

names.append('a')
names.append('b')
names.append('c')
console.log(names.toString()) // ["a", "b", "c"]

names.remove('b')
console.log(names.toString()) // ["a", "c"]

6、insert 方法​

向列表中插入一个元素。

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

insert() 方法中使用 find() 方法，寻找传入的 after 参数在列表中的位置，然后使用 splice() 方法将新元素插入该位置，再将变量 listSize 加 1 并返回 true。

7、clear 方法​

清空列表中所有的元素。

function clear() {
  delete this.dataStore
  this.dataStore.length = 0
  this.listSize = this.pos = 0
}

clear() 方法使用 delete 操作符删除数组 dataStore，接着在下一行创建一个空数组，最后一行将 listSize 和 pos 的值设为 1，表明这是一个新的空列表。

8、contains 方法​

判断给定值是否在列表中。

function contains(element) {
  for (var i = 0; i < this.dataStore.length; i++) {
    if (this.dataStore[i] == element) {
      return true
    }
  }
  return false
}

9、遍历列表方法​

允许用户在列表上自由移动的方法集合。

function front() {
  this.pos = 0
}

function end() {
  this.pos = this.listSize - 1
}

function prev() {
  --this.pos
}

function next() {
  if (this.pos < this.listSize) {
    ++this.pos
  }
}

function currPos() {
  return this.pos
}

function moveTo(position) {
  this.pos = position
}

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

function hasNext() {
  return this.pos < this.listSize
}

function hasPrev() {
  return this.pos >= 0
}

三、列表的使用​

下面用一个例子来展示这些方法的使用：

1、创建列表​

var names = new List()

names.append('a')
names.append('b')
names.append('c')
names.append('d')
names.append('e')

2、查看列表第一个元素​

names.front()
console.log(names.getElement()) // a

3、往后移动一个单位​

// 从 a 开始
names.next()
console.log(names.getElement()) // b

4、往前移动一个单位​

// 从 b 开始
names.next()
names.next()
names.prev()
console.log(names.getElement()) // c