Javascript 列表List

List是日常生活中使用最多的一种数据组织工具，例如购物单，运货单，排名表等。注意List不适合需要进行频繁排序或查找的场景。
List中的元素是按顺序组织（存储）起来的。元素可以是任意类型。可以在列表的任意位置添加或删除元素。

List的ADT（抽象数据类型）定义

List的类定义

function List() {  // 定义class 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.length = length;
   this.currPos = currPos;
   this.moveTo = moveTo;
   this.getElement = getElement;
   this.length = length;
   this.contains = contains;
}   

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

function find(element) {
   for (var i = 0; i < this.dataStore.length; ++i) {
      if (this.dataStore[i] == element) {
         return i;
      }
   }
   return -1;  // 未找到时返回-1
}

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

function length() {
   return this.listSize;
}

function toString() {
    return this.dataStore;
}

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

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

function contains(element) {
   for (var i = 0; i < this.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() {
   if (this.pos > 0) {
      --this.pos;
   }
}

function next() {
   if (this.pos < this.listSize-1) {
      ++this.pos;
   }
}

function currPos() {
   return this.pos;
}

function moveTo(position) {
   this.pos = position;
}

function getElement() {
   return this.dataStore[this.pos];
}

假设有文件films.txt包含如下内容：
The Shawshank Redemption
The Godfather
The Godfather: Part II
Pulp Fiction
The Good, the Bad and the Ugly
12 Angry Men
Schindler’s List
The Dark Knight
The Lord of the Rings: The Return of the King
Fight Club
Star Wars: Episode V - The Empire Strikes Back
One Flew Over the Cuckoo’s Nest
The Lord of the Rings: The Fellowship of the Ring
Inception
Goodfellas
Star Wars
Seven Samurai
The Matrix
Forrest Gump
City of God
现在我们编程序使用List来管理电影数据

// 读取电影清单，保存在数组中
function createArr(file) {
   var arr = read(file).split("\n");
   for (var i = 0; i < arr.length; ++i) {
      arr[i] = arr[i].trim();
   }
   return arr;
}

// 创建List，保存电影
var movieList = new List();
for (var i = 0; i < movies.length; ++i) {
   movieList.append(movies[i]);
}

// 显示所有电影
function displayList(list) {
   for (list.front(); list.currPos() < list.length(); list.next()) {
      print(list.getElement());
}

// 定义客户，假设客户可以借一部电影
function Customer(name, movie) {
   this.name = name;
   this.movie = movie;
}

// list中存储的是Customer对象，显示所有Customer信息
function displayList(list) {
   for (list.front(); list.currPos() < list.length(); list.next()) {
      if (list.getElement() instanceof Customer) {  // 使用 instanceof 判断对象类型
         print(list.getElement()["name"] + ", " +
               list.getElement()["movie"]);
      }
      else {
         print(list.getElement());
      }
   }
}

// 借阅电影
function checkOut(name, movie, filmList, customerList) {
   if (movieList.contains(movie)) {
      var c = new Customer(name, movie);
      customerList.append(c);
      filmList.remove(movie);
   }
   else {
      print(movie + " is not available.");
   }
}

总结

List是一种非常常用的数据结构，提供了灵活的访问接口。适合管理有序数据，但要注意其查询和插入效率都是O(n)，较费时。可以使用instanceof关键字判断对象的类型。