列表是一种数据结构, 在生活中也有广泛应用, 例如待办事项清单, 购物清单等都可以做成列表. 在开发中, 我们就可以把列表抽象成一个数据类型, 将它写成一个可以循环使用并能用来解决问题的程序, 这就是一个列表抽象类.
类的定义
用 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 方法的使用吗? 如果忘了, 可以查看上一篇文章 数据结构之数组 https://mp.weixin.qq.com/s/Mb6c2wQ9myACpDCdNlmlcw 里面有关于数组常用方法的介绍.
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 著
来源: http://www.jianshu.com/p/9b08de1e8484