?? ?? ?列表是有序的數(shù)據(jù)充择，常用語(yǔ)最受歡迎榜單取胎、購(gòu)物車列表展哭、其他列表展示。
?? ?? ?在js中并不存在列表結(jié)構(gòu)闻蛀，所以列表結(jié)構(gòu)需要去通過(guò)構(gòu)造函數(shù)去構(gòu)建匪傍。本系列參考Michael McMillan所著《數(shù)據(jù)結(jié)構(gòu)與算法javascript描述》，并對(duì)其中存在的細(xì)節(jié)問(wèn)題進(jìn)行改正觉痛，如有不對(duì)請(qǐng)各位指正役衡。
1.列表ADT
this.listSize = 0; // 列表長(zhǎng)度
this.pointer = 0; //當(dāng)前指針位置
this.dataSource = []; // 初始化一個(gè)空數(shù)組來(lái)保存列表元素
this.clear = clear; // 清空列表
this.find = find; // 查找指定下標(biāo)
this.toString = toString; // 構(gòu)造toString函數(shù)
this.valueOf = valueOf; // 構(gòu)造valueOf函數(shù)
this.insertAfter = insertAfter; // 指定元素后添加元素
this.insertBefore = insertBefore; // 指定元素前添加元素
this.add = add; // 向列表尾端添加元素
this.remove = remove; // 刪除列表中指定元素
this.front = front; // 將列表的指針移到第一個(gè)元素
this.end = end; // 將列表的指針移到最后一個(gè)元素
this.prev = prev; // 將列表的指針前移一位
this.next = next; // 將列表的指針后移一位
this.hasNext = hasNext; // 判斷后一位
this.hasPrev = hasPrev; // 判斷前一位
this.length = length; // 返回列表中元素的個(gè)數(shù)
this.getPointer = getPointer; // 返回列表指針
this.moveTo = moveTo; // 列表指針移動(dòng)到指定位置
this.getItem = getItem; // 獲取列表元素
this.contains = contains; // 判斷列表是否包含指定元素
2.構(gòu)造函數(shù)
/**
* 定義List構(gòu)造函數(shù)
*/
function List() {
this.listSize = 0; // 列表長(zhǎng)度
this.pointer = 0; //當(dāng)前指針位置
this.dataSource = []; // 初始化一個(gè)空數(shù)組來(lái)保存列表元素
this.clear = clear; // 清空列表
this.find = find; // 查找指定下標(biāo)
this.toString = toString; // 構(gòu)造toString函數(shù)
this.valueOf = valueOf; // 構(gòu)造valueOf函數(shù)
this.insertAfter = insertAfter; // 指定元素后添加元素
this.insertBefore = insertBefore; // 指定元素前添加元素
this.add = add; // 向列表尾端添加元素
this.remove = remove; // 刪除列表中指定元素
this.front = front; // 將列表的指針移到第一個(gè)元素
this.end = end; // 將列表的指針移到最后一個(gè)元素
this.prev = prev; // 將列表的指針前移一位
this.next = next; // 將列表的指針后移一位
this.hasNext = hasNext; // 判斷后一位
this.hasPrev = hasPrev; // 判斷前一位
this.length = length; // 返回列表中元素的個(gè)數(shù)
this.getPointer = getPointer; // 返回列表指針
this.moveTo = moveTo; // 列表指針移動(dòng)到指定位置
this.getItem = getItem; // 獲取列表元素
this.contains = contains; // 判斷列表是否包含指定元素
}
3.顯式方法
/**
* 向列表末尾添加元素
* 并將列表長(zhǎng)度自加1
*/
function add(item) {
this.dataSource[this.listSize++] = item;
}
/**
* 清空列表
*/
function clear() {
delete this.dataSource;
this.dataSource.length = 0;
this.listSize = this.pointer = 0;
}
/**
* 轉(zhuǎn)為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;
}
/**
* 返回列表長(zhǎng)度
*/
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;
}
/**
* 移動(dòng)指針
*/
function moveTo(index) {
this.pointer = index;
}
/**
* 獲取指針指向的對(duì)象
*/
function getItem() {
return this.dataSource[this.pointer];
}
在原著中hasPrev()、hasNext()均包含了上下界薪棒，包含上下界的好處是手蝎，可以通過(guò)遍歷去遍歷所有的元素，缺點(diǎn)是不符合函數(shù)原本的意義俐芯，當(dāng)this.pointer === 0 || this.pointer === this.listSize.length - 1時(shí)棵介，是不能前一位||后一位仍然存在元素的。
4.遍歷元素
如果采用原著所言的吧史，包含上下界邮辽，則遍歷list元素的方法為
for(lists.end(); lists.hasPrev(); lists.prev()) {
clg(lists.getItem())
}
如果不采取原著所言，使判斷前后一位的函數(shù)具有原意贸营，則不能使用原著的遍歷方法吨述，否則會(huì)出現(xiàn)死循環(huán)，應(yīng)想辦法跳出死循環(huán)
for(lists.end(); lists.pointer >= 0; lists.prev()) {
clg(lists.getItem())
if(lists.pointer === 0) break;
}
5.原著錯(cuò)誤
構(gòu)造函數(shù)中存在兩處函數(shù)零引用莽使，this.hasNext锐极； this.hasPrev;
