前言
List是一组有序的数据，我们将List中的每个数据称之为元素。
定义
在设计一个数据结构之前，首先我们需要对其进行抽象，给出List的定义，List应该有什么属性以及什么方法，这个例子中，我们将使用javaScrip数组来作为数据源(近期在学习typeScript，所以以下例子使用ts实现,如想查看js版，请访问gitHub)
1.属性
- 查看 List中的元素个数
length - List当前的位置
index - 数据源
dataSourc
- 方法
- 获取List中元素个数
getSize - 清空List中所有的元素
clear - 返回List的字符串形式
toString - 获取当前位置的元素
getElement - 在现有元素后插入新元素
insert - 在List末尾添加元素
add - 从List中删除元素
remove - 将List当前的位置移动到第一个元素
front - 将List当前的位置移动到最后一个元素
end - 将当前位置前移一位
prev - 将当前位置后移一位
next - 判断后一位
hasNext - 判断前一位
hasPrev - 返回List当前位置
getIndex - 将位置移动到指定位置
moveTo - 判断List中是否存在某元素
contains
实现List类
class List<T> {
private _length: number;
private _index: number;
private _dataSource: Array<T>;
public clear = () => { }
private _find = () => { }
public toString = () => { }
public insert = () => { }
public add = () => { }
public remove = () => { }
public front = () => { }
public end = () => { }
public prev = () => { }
public next = () => { }
public hasPrev = () => { }
public hasNext = () => { }
public getSize = () => { }
public getIndex = () => { }
public moveTo = () => { }
public getElement = () => { }
public contains = () => { }
}
实现方法
- add
在数组的最后添加一个元素，并让长度+1
public add = (element: T): void => {
this._dataSource[this._length] = element;
this._length++;
}
- remove
首先判断该List中是否存在元素，如果存在则删除，并返回true，否则返回false
public remove = (element: T): boolean => {
const index = this._find(element);
if (index > -1) {
this._dataSource.splice(index, 1);
this._length--;
return true;
}
return false;
}
- clear
数组的length属性是可写的，设为0删除所有元素，并设置其它状态初始化
public clear = (): void => {
this._dataSource.length = 0;
this._length = 0;
this._index = 0;
}
- contains
判断元素是否存在与List中，内部调用_find方法来进行判断；
public contains = (element: T): boolean => {
const index: number = this._find(element);
if (index > -1) return true;
return false;
}
- 遍历List
public front = (): void => {
this._index = 0;
}
public end = (): void => {
this._index = this._length - 1;
}
public prev = (): void => {
if (this._index > 0) this._index --;
}
public next = (): void => {
if (this._index < this._length) this._index ++;
}
public hasPrev = (): boolean => {
return this._index >= 0;
}
public hasNext = (): boolean => {
return this._index < this._length;
}
public getSize = (): number => {
return this._length;
}
public getIndex = (): number => {
return this._index;
}
public moveTo = (newIndex): number => {
return this._index = newIndex;
}
public getElement = (): T => {
return this._dataSource[this._index];
}
到目前为止就已经实现了List的所有方法，下面让我们来使用这个List
const list = new List<string>();
list.add('a');
list.add('b');
list.add('c');
for (list.front(); list.hasNext(); list.next()) {
console.log('element', list.getElement())
}
