数据结构之列表的定义

列表是一种数据结构，在生活中也有广泛应用，例如待办事项清单、购物清单等都可以做成列表。在开发中，我们就可以把列表抽象成一个数据类型，将它写成一个可以循环使用并能用来解决问题的程序，这就是一个列表抽象类。

类的定义

用 JavaScript 定义一个 List 类，代码如下：

function List() {
  this.listsize = 0;       // 列表的元素个数
  this.pos = 0;            // 列表的当前位置
  this.dataStore = [];      // 保存列表元素的数组
  this.clear = clear;          // 清空列表元素
  this.find = find;            // 查找某一元素
  this.toString = toString;       // 显示列表元素
  this.insert = insert;          // 插入元素
  this.append = append;           // 添加元素
  this.remove = remove;          // 删除元素
  this.front = front;             // 将当前位置移动到第一个元素
  this.end = end;                // 将当前位置移动到最后一个元素
  this.prev = prev;              // 将当前位置后移一位
  this.next = next;              // 将当前位置前移一位
  this.hasNext;                  // 判断后一位
  this.hasPrev;                  // 判断前一位
  this.length = length;          // 列表的元素个数
  this.currPos = currPos;        // 返回列表的当前位置
  this.moveTo = moveTo;          // 将当前位置移动到指定位置
  this.getElement = getElement;       // 获取元素
  this.contains = contains;           // 判断元素是否存在列表
} 

以上，基本把一个列表类的所有方法都列举出来了。下面针对每一个方法做一个具体的实现。

append:给列表添加元素

当调用 append 方法后，就会给列表的下一个位置增加一个新的元素，这个位置就等于变量 listSize 的值：

function append(element) {
  this.dataStore[this.listSize++] = element;
}

listSize 表示列表的元素个数，所以添加后就要加 1.

remove:删除元素

它的实现思路是：首先在列表中查找到我们传入的这个需要删除的元素，然后删除它，最后让所有元素移动以填补删除元素的空白。为方便，先定义一个查找元素的 find 方法：

function find(element) {
  for(var i=0;i<this.dataStore.length;i++){
    if(this.dataStore[i] == element) {
       return i;
    }
  }
  return -1;
}

这个方法类似于很多字符串或数组之类的查找方法，找到一个元素，就返回该元素在列表中的位置；否则返回 -1.接下来我们就可以写删除元素的 remove 方法.

function remove(element) {
  var foundAt = this.find(element);
  if(foundAt > -1) {
    this.dataStore.splice(foundAt,1);
    --this.listSize;
    return true;
  }
  return false;
}

还记得 splice 方法的使用吗？如果忘了，可以查看上一篇文章 数据结构之数组 里面有关于数组常用方法的介绍。

length:长度

这个方法无需多说，直接上代码：

function length() {
  return this.listSize;
}

toString:把元素陈列出来

这个方法就是输出列表中的元素：

function toString() {
  return this.dataStore;
}

测试

上面列了这么多方法，不妨来测试下，下面是简短的测试代码：

var names = new List();
names.append("John");
names.append("Mike");
names.append("Amy");
console.log(names.toString());
names.remove("Amy");
console.log(names.toString());

执行结果为：

John,Mike,Amy
John,Mike

insert:插入元素

function insert(element,after) {
  var curr = this.find(after);
  if(curr > -1) {
    this.dataStore.splice(curr+1,0,element);
    ++this.listSize;
    return true;
  }
   return false;
}

insert 方法的实现思路是：首先找到一个元素 after ，你想要把元素插入在这个 after 元素之后，于是你得先找到这个 after 在列表里的位置，然后你就可以利用 splice 方法将你想插入的元素进行插入。插入成功返回 true，失败返回 false；

clear：清空元素

该方法相当于扫把，把所有列表里的东西都清理掉：

function clear() {
  delete this.dataStore;
  this.dataStore.length = 0;
  this.listSize = this.pos = 0;
}

可以看到，使用了 delete 操作符来删除数组 dataStore,接着在创建一个空数组，最后将属性值归零。

contains：判断给定值是否在列表中

function contains(element) {
  for (var i = 0; i < dataStore.length; i++) {
    if(this.dataStore[i] == element) {
       return true;
    }
  }
  return false;
}

遍历列表

下面的这些方法可以在列表上移动元素

function front() {
  this.pos = 0;
}
function end() {
  this.pos = this.listSize-1;
}
function prev() {
  --this.pos;
}
function next() {
  if(this.pos < this.listSize) {
    ++this.pos;
  }
}
function currPos() {
  return this.pos;
}
function moveTo(position) {
  this.pos = position;
}
function getElement() {
  return this.dataStore[this.pos];
}
function hasNext() {
  return this.pos<this.listSize;
}
function hasPrev() {
  return this.pos >= 0;
}

参考资料：Data Structure and Algorithms Using JavaScript, Michael McMillan 著