js实现复杂数据结构之List

前言

List是一组有序的数据，我们将List中的每个数据称之为元素。

定义

在设计一个数据结构之前，首先我们需要对其进行抽象，给出List的定义，List应该有什么属性以及什么方法，这个例子中，我们将使用javaScrip数组来作为数据源(近期在学习typeScript，所以以下例子使用ts实现,如想查看js版，请访问gitHub)

1.属性

• 查看 List中的元素个数
  length
• List当前的位置
  index
• 数据源
  dataSourc

2. 方法

• 获取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())
}