JS 算法与数据结构之列表
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()) // a3、接下来往后移动一个单位并显示
names.next()
console.log(names.getElement()) // b4、prev() 的使用
names.next()
names.next()
names.prev()
console.log(names.getElement()) // c腾讯云开发者
