列表是一种数据结构，在生活中也有广泛应用，例如待办事项清单、购物清单等都可以做成列表。在开发中，我们就可以把列表抽象成一个数据类型，将它写成一个可以循环使用并能用来解决问题的程序，这就是一个列表抽象类。
类的定义
用 JavaScript 定义一个 List 类，代码如下：
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; // 判断元素是否存在列表
}
以上，基本把一个列表类的所有方法都列举出来了。下面针对每一个方法做一个具体的实现。
append:给列表添加元素
当调用 append 方法后，就会给列表的下一个位置增加一个新的元素，这个位置就等于变量 listSize 的值：
function append(element) {
this.dataStore[this.listSize++] = element;
}
listSize 表示列表的元素个数，所以添加后就要加 1.
remove:删除元素
它的实现思路是：首先在列表中查找到我们传入的这个需要删除的元素，然后删除它，最后让所有元素移动以填补删除元素的空白。为方便，先定义一个查找元素的 find 方法：
function find(element) {
for(var i=0;i<this.dataStore.length;i++){
if(this.dataStore[i] == element) {
return i;
}
}
return -1;
}
这个方法类似于很多字符串或数组之类的查找方法，找到一个元素，就返回该元素在列表中的位置；否则返回 -1.接下来我们就可以写删除元素的 remove 方法.
function remove(element) {
var foundAt = this.find(element);
if(foundAt > -1) {
this.dataStore.splice(foundAt,1);
--this.listSize;
return true;
}
return false;
}
还记得 splice 方法的使用吗？如果忘了，可以查看上一篇文章 数据结构之数组 里面有关于数组常用方法的介绍。
length:长度
这个方法无需多说，直接上代码：
function length() {
return this.listSize;
}
toString:把元素陈列出来
这个方法就是输出列表中的元素：
function toString() {
return this.dataStore;
}
测试
上面列了这么多方法，不妨来测试下，下面是简短的测试代码：
var names = new List();
names.append("John");
names.append("Mike");
names.append("Amy");
console.log(names.toString());
names.remove("Amy");
console.log(names.toString());
执行结果为：
John,Mike,Amy
John,Mike
insert:插入元素
function insert(element,after) {
var curr = this.find(after);
if(curr > -1) {
this.dataStore.splice(curr+1,0,element);
++this.listSize;
return true;
}
return false;
}
insert 方法的实现思路是：首先找到一个元素 after ，你想要把元素插入在这个 after 元素之后，于是你得先找到这个 after 在列表里的位置，然后你就可以利用 splice 方法将你想插入的元素进行插入。插入成功返回 true，失败返回 false；
clear：清空元素
该方法相当于扫把，把所有列表里的东西都清理掉：
function clear() {
delete this.dataStore;
this.dataStore.length = 0;
this.listSize = this.pos = 0;
}
可以看到，使用了 delete 操作符来删除数组 dataStore,接着在创建一个空数组，最后将属性值归零。
contains：判断给定值是否在列表中
function contains(element) {
for (var i = 0; i < dataStore.length; i++) {
if(this.dataStore[i] == element) {
return true;
}
}
return false;
}
遍历列表
下面的这些方法可以在列表上移动元素
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;
}
参考资料：Data Structure and Algorithms Using JavaScript, Michael McMillan 著
网友评论