列表是有序的数据，常用语最受欢迎榜单、购物车列表、其他列表展示。
在js中并不存在列表结构，所以列表结构需要去通过构造函数去构建。本系列参考Michael McMillan所著《数据结构与算法javascript描述》，并对其中存在的细节问题进行改正，如有不对请各位指正。
1.列表ADT
this.listSize = 0; // 列表长度
this.pointer = 0; //当前指针位置
this.dataSource = []; // 初始化一个空数组来保存列表元素
this.clear = clear; // 清空列表
this.find = find; // 查找指定下标
this.toString = toString; // 构造toString函数
this.valueOf = valueOf; // 构造valueOf函数
this.insertAfter = insertAfter; // 指定元素后添加元素
this.insertBefore = insertBefore; // 指定元素前添加元素
this.add = add; // 向列表尾端添加元素
this.remove = remove; // 删除列表中指定元素
this.front = front; // 将列表的指针移到第一个元素
this.end = end; // 将列表的指针移到最后一个元素
this.prev = prev; // 将列表的指针前移一位
this.next = next; // 将列表的指针后移一位
this.hasNext = hasNext; // 判断后一位
this.hasPrev = hasPrev; // 判断前一位
this.length = length; // 返回列表中元素的个数
this.getPointer = getPointer; // 返回列表指针
this.moveTo = moveTo; // 列表指针移动到指定位置
this.getItem = getItem; // 获取列表元素
this.contains = contains; // 判断列表是否包含指定元素
2.构造函数
/**
* 定义List构造函数
*/
function List() {
this.listSize = 0; // 列表长度
this.pointer = 0; //当前指针位置
this.dataSource = []; // 初始化一个空数组来保存列表元素
this.clear = clear; // 清空列表
this.find = find; // 查找指定下标
this.toString = toString; // 构造toString函数
this.valueOf = valueOf; // 构造valueOf函数
this.insertAfter = insertAfter; // 指定元素后添加元素
this.insertBefore = insertBefore; // 指定元素前添加元素
this.add = add; // 向列表尾端添加元素
this.remove = remove; // 删除列表中指定元素
this.front = front; // 将列表的指针移到第一个元素
this.end = end; // 将列表的指针移到最后一个元素
this.prev = prev; // 将列表的指针前移一位
this.next = next; // 将列表的指针后移一位
this.hasNext = hasNext; // 判断后一位
this.hasPrev = hasPrev; // 判断前一位
this.length = length; // 返回列表中元素的个数
this.getPointer = getPointer; // 返回列表指针
this.moveTo = moveTo; // 列表指针移动到指定位置
this.getItem = getItem; // 获取列表元素
this.contains = contains; // 判断列表是否包含指定元素
}
3.显式方法
/**
* 向列表末尾添加元素
* 并将列表长度自加1
*/
function add(item) {
this.dataSource[this.listSize++] = item;
}
/**
* 清空列表
*/
function clear() {
delete this.dataSource;
this.dataSource.length = 0;
this.listSize = this.pointer = 0;
}
/**
* 转为String
*/
function toString() {
return this.dataSource.join();
}
/**
* 返回原值
*/
function valueOf() {
return this.dataSource;
}
/**
* 查找指定元素index
*/
function find(item) {
return this.dataSource.findIndex(data => data === item);
}
/**
* 删除指定元素
*/
function remove(item) {
let index = find(item);
if(index > -1){
this.dataSource.splice(index, 1);
this.listSize--;
return true;
}
return false;
}
/**
* 指定元素后添加元素
*/
function insertAfter(after, item) {
let index = find(after);
if(index > -1) {
this.dataSource.splice(index,0,item);
this.listSize ++;
return true;
}
return false;
}
/**
* 指定元素前添加元素
*/
function insertBefore(before, item) {
let index = find(before) - 1;
if(index > -2) {
this.dataSource.splice(index,0,item);
this.listSize ++;
return true;
}
return false;
}
/**
* 返回列表长度
*/
function length() {
return this.listSize;
}
/**
* 判断指定的值是否在列表中
*/
function contains(item) {
return this.dataSource.some(data => data === item);
}
/**
* 指针移位到首位
*/
function front() {
this.pointer = 0;
}
/**
* 指针移位到末位
*/
function end() {
this.pointer = this.listSize - 1;
}
/**
* 指针前移一位
*/
function prev() {
if(this.pointer > 0) {
this.pointer--;
}
}
/**
* 指针后移一位
*/
function next() {
if(this.pointer < this.listSize -1) {
this.pointer++;
}
}
/**
* 拥有下一位
*/
function hasNext() {
return this.pointer < this.listSize - 1; // 非原著
}
/**
* 拥有前一位
*/
function hasPrev() {
return this.pointer > 0; // 非原著
}
/**
* 获取指针
*/
function getPointer() {
return this.pointer;
}
/**
* 移动指针
*/
function moveTo(index) {
this.pointer = index;
}
/**
* 获取指针指向的对象
*/
function getItem() {
return this.dataSource[this.pointer];
}
在原著中hasPrev()、hasNext()均包含了上下界，包含上下界的好处是，可以通过遍历去遍历所有的元素，缺点是不符合函数原本的意义，当this.pointer === 0 || this.pointer === this.listSize.length - 1时，是不能前一位||后一位仍然存在元素的。
4.遍历元素
如果采用原著所言的，包含上下界，则遍历list元素的方法为
for(lists.end(); lists.hasPrev(); lists.prev()) {
clg(lists.getItem())
}
如果不采取原著所言，使判断前后一位的函数具有原意，则不能使用原著的遍历方法，否则会出现死循环，应想办法跳出死循环
for(lists.end(); lists.pointer >= 0; lists.prev()) {
clg(lists.getItem())
if(lists.pointer === 0) break;
}
5.原著错误
构造函数中存在两处函数零引用，this.hasNext； this.hasPrev;
网友评论