列表是一种数据结构,在生活中也有广泛应用,例如待办事项清单、购物清单等都可以做成列表。在开发中,我们就可以把列表抽象成一个数据类型,将它写成一个可以循环使用并能用来解决问题的程序,这就是一个列表抽象类。
类的定义
用 JavaScript 定义一个 List 类,代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| 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 的值:
1 2 3
| function append(element) { this.dataStore[this.listSize++] = element; }
|
listSize 表示列表的元素个数,所以添加后就要加 1.
remove:删除元素
它的实现思路是:首先在列表中查找到我们传入的这个需要删除的元素,然后删除它,最后让所有元素移动以填补删除元素的空白。为方便,先定义一个查找元素的 find 方法:
1 2 3 4 5 6 7 8
| function find(element) { for(var i=0;i<this.dataStore.length;i++){ if(this.dataStore[i] == element) { return i; } } return -1; }
|
这个方法类似于很多字符串或数组之类的查找方法,找到一个元素,就返回该元素在列表中的位置;否则返回 -1.接下来我们就可以写删除元素的 remove 方法.
1 2 3 4 5 6 7 8 9
| function remove(element) { var foundAt = this.find(element); if(foundAt > -1) { this.dataStore.splice(foundAt,1); --this.listSize; return true; } return false; }
|
还记得 splice 方法的使用吗?如果忘了,可以查看上一篇文章 数据结构之数组 里面有关于数组常用方法的介绍。
length:长度
这个方法无需多说,直接上代码:
1 2 3
| function length() { return this.listSize; }
|
toString:把元素陈列出来
这个方法就是输出列表中的元素:
1 2 3
| function toString() { return this.dataStore; }
|
测试
上面列了这么多方法,不妨来测试下,下面是简短的测试代码:
1 2 3 4 5 6 7
| 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:插入元素
1 2 3 4 5 6 7 8 9
| 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:清空元素
该方法相当于扫把,把所有列表里的东西都清理掉:
1 2 3 4 5
| function clear() { delete this.dataStore; this.dataStore.length = 0; this.listSize = this.pos = 0; }
|
可以看到,使用了 delete 操作符来删除数组 dataStore,接着在创建一个空数组,最后将属性值归零。
contains:判断给定值是否在列表中
1 2 3 4 5 6 7 8
| function contains(element) { for (var i = 0; i < dataStore.length; i++) { if(this.dataStore[i] == element) { return true; } } return false; }
|
遍历列表
下面的这些方法可以在列表上移动元素
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
| 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 著
最后更新时间:
欢迎关注微信公众号,分享原创技术文章,见下方二维码。
v1.5.2