这篇文章主要站在数据结构和算法的角度来描述列表
列表的定义
列表是一组有序或者无序的数据。每个列表中的数据项称为元素；在基础数据结构中，列表作为最为基础的一个数据结构进行体现
列表的模型
list-model.png
列表的抽象数据类型定义(ADT)
| 名称 | 类型 | 描述 |
|---|---|---|
| listSize | 属性 | 列表的元素个数 |
| pos | 属性 | 列表的当前位置 |
| length | 属性 | 返回列表中元素的个数 |
| clear | 方法 | 清空列表中的所有元素 |
| toString | 方法 | 返回列表的字符串形式 |
| getElement | 方法 | 返回当前位置的元素 |
| insert | 方法 | 在现有元素后插入新元素 |
| append | 方法 | 在列表的末尾添加新元素 |
| remove | 方法 | 从列表中删除元素 |
| front | 方法 | 将列表的当前位置设移动到第一个元素 |
| end | 方法 | 将列表的当前位置移动到最后一个元素 |
| prev | 方法 | 将当前位置后移一位 |
| next | 方法 | 将当前位置前移一位 |
| currPos | 方法 | 返回列表的当前位置 |
| moveTo | 方法 | 将当前位置移动到指定位置 |
javascript编码实现（这里用的是typescript 超集来实现）
class MyList {
// 保存数据
dataStore: [any] | [];
// 列表的元素个数
listSize: number;
// 列表的当前位置
pos: number;
// 返回列表中的元素个数
length: number;
constructor() {
this.listSize = 0;
this.pos = 0;
this.length = this.myLength();
this.dataStore = [];
}
/**
* 清空列表
*/
public clear(): this {
delete this.dataStore;
this.dataStore = [];
this.listSize = this.pos = 0;
return this;
}
/**
* 在列表末尾添加元素
* @param element
*/
public append(element: any): this {
this.dataStore[this.listSize++] = element;
return this;
}
/**
* 在列表中查找元素，存在返回索引，失败返回-1
* @param element
*/
public find(element: any):
any {
for (var i = 0; i < this.dataStore.length; ++i) {
if (this.dataStore[i] == element) {
return i;
}
}
return -1;
}
/**
* 删除列表中的元素，成功true，失败false
* @param element
*/
public remove(element: any): boolean {
var foundAt = this.find(element);
if (foundAt > -1) {
this.dataStore.splice(foundAt, 1);
--this.listSize;
return true;
}
return false;
}
/**
* 返回列表的长度
*/
public myLength(): any {
return this.listSize;
}
/**
* 将列表序列化
*/
public toString(): any {
return this.dataStore;
}
/**
* 将元素插入列表中 成功true，失败false
* @param element
* @param after
*/
public insert(element: any, after: any): boolean {
var insertPos = this.find(after);
if (insertPos > -1) {
this.dataStore.splice(insertPos + 1, 0, element);
++this.listSize;
return true;
}
return false;
}
/**
* 判断一个给定值是否在列表 成功true，失败false
* @param element
*/
public contains(element: any): boolean {
for (var i = 0; i < this.dataStore.length; ++i) {
if (this.dataStore[i] == element) {
return true;
}
}
return false;
}
/**
* 获取第一个元素的索引
*/
public front() {
this.pos = 0;
}
/**
* 获取最后一个元素的索引
*/
public end() {
this.pos = this.listSize - 1;
}
/**
* 将列表的位置向前移动一位
*/
public prev() {
if (this.pos > 0) {
--this.pos;
}
}
/**
* 将列表的位置向后移动一位
*/
public next() {
if (this.pos <= this.listSize - 1) {
++this.pos;
}
}
/**
* 获取列表当前的位置
*/
public currPos() {
return this.pos;
}
/**
* 将列表当前的位置移动几步
* @param position
*/
public moveTo(position: any) {
this.pos = position;
}
/**
* 获取列表当前位置的元素
*/
public getElement() {
return this.dataStore[this.pos];
}
}
let myobj = new MyList();
console.log('length :' + myobj.length);
myobj.append('lxl');
myobj.append('zy');
myobj.append('pl');
myobj.append('tz');
myobj.append('mm');
myobj.append('mj');
console.log('append :' + myobj.toString());
console.log('mylength :' + myobj.myLength());
console.log('find :' + myobj.find('zy'));
myobj.insert('nw', 'pl');
console.log('insert :' + myobj.toString());
console.log('contains :' + myobj.contains('lxl'));
myobj.remove('mm');
console.log('remove :' + myobj.toString());
myobj.front();
console.log('front :' + myobj.getElement());
myobj.next();
console.log('next :' + myobj.getElement());
myobj.prev();
console.log('pre :' + myobj.getElement());
console.log(myobj.currPos());
console.log(myobj.myLength());
myobj.next();
console.log(myobj.currPos());
for(myobj.front(); myobj.currPos() < myobj.myLength(); myobj.next()) {
console.log('currPos :' + myobj.currPos());
console.log('len :' + myobj.myLength());
console.log(myobj.getElement());
}
下面是在node环境中测试结果
length :0
append :lxl,zy,pl,tz,mm,mj
mylength :6
find :1
insert :lxl,zy,pl,nw,tz,mm,mj
contains :true
remove :lxl,zy,pl,nw,tz,mj
front :lxl
next :zy
pre :lxl
0
6
1
currPos :0
len :6
lxl
currPos :1
len :6
zy
currPos :2
len :6
pl
currPos :3
len :6
nw
currPos :4
len :6
tz
currPos :5
len :6
mj
从测试结果看出各个算法（方法）都基本达到了要求的效果，最后的迭代也比较理想；最后此次文章参考了：Data Structure and Algorithms Using JavaScript ，Michael McMillan 著 (O’Reilly，2014)。版权所有，978-1-449-36493-9。
在此特别感谢
