数据结构之列表的定义

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

类的定义

用 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 的值：

1
2
3

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:长度

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

1
2
3

function length() {
  return this.listSize;
}

toString:把元素陈列出来

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

1
2
3

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 著