js实现数据结构及算法之列表(List)-白红宇

前言：

最近在学习数据结构及算法，数据结构：列表，栈，队列，链表，字典，散列，集合，二叉树；算法：图和图算法，排序算法：冒泡、选择、插入、希尔、归并、快速，检索算法：顺序查找，二分查找；还有高级一点的动态规划和贪心算法，这些都会用js一一实现，算是记录下来，给自己以后复习用吧。

先上代码：列表

概念及定义：

列表是一组有序的数据，每个列表中数据被称为元素，元素的数量受内存控制。

不包括任何元素的列表称为空列表。

应用：

不需要很长序列查找元素或排序，元素不是很多。

js实现：

/** * 一个简单的列表 * @constructor */function List() {  this.dataSource = [];//初始化一个空数组来保存列表元素  this.listSize = 0;  // 列表长度  this.pos = 0;  // 当前位置  this.append = append; // 在列表的末尾添加元素  this.find = find; // 是否包含元素  this.getLength = getLength; // 获取列表的长度  this.remove = remove; // 从列表中删除当前元素  this.toString = toString; // 返回列表的字符串形式  this.insert = insert; //在当前位置元素的后面插入元素  this.clear = clear; // 清空列表  this.front = front; // 将列表的当前位置移动到第一个元素位置  this.end = end; // 将列表的当前位置移动到最后一个元素位置  this.getElement = getElement; // 返回当前位置的元素  this.prev = prev; // 将列表的当前位置向前移动一位  this.next = next; // 将列表的当前位置向后移动一位  this.currentPos = currentPos; // 返回列表的当前位置  this.moveTo = moveTo; // 将当前位置移动到指定位置  this.contains = contains; //是否包含该元素  this.loop = loop; // 列表的遍历器}/** * 给列表最后添加元素的时候，列表元素个数+1 * @param element */function append(element) {  this.listSize++;  this.dataSource.push(element);}/** * @param element 如果传入的是对象，需要判断是否是对象以及两个对象是否相等 * @returns {number} 如果找到，返回位置，否则-1 */function find(element) {  for (var i = 0; i < this.dataSource.length; i++) {    if (this.dataSource[i] === element) {      return i;    }  }  return -1;}/** * 返回列表元素的个数 * @returns {number} */function getLength() {  return this.listSize;}/** * 删除元素成功，元素个数-1 * @param element * @returns {boolean} */function remove(element) {  var removeIndex = this.find(element);  if (removeIndex !== -1) {    this.dataSource.splice(removeIndex, 1);    this.listSize--;    return true;  }  return false;}/** * 返回要展示的列表 * @returns {string} */function toString() {  return this.dataSource.toString();}/** * 插入某个元素 * @param element 要插入的元素 * @param afterElement 列表中的元素之后 * @returns {boolean} */function insert(element, afterElement) {  var insertIndex = this.find(afterElement);  if (insertIndex !== -1) {    this.dataSource.splice(insertIndex + 1, 0, element);    this.listSize++;    return true;  }  return false;}/** * 清空列表中的所有元素 */function clear() {  delete this.dataSource;  this.dataSource = [];  this.listSize = this.pos = 0;}/** * 将列表的当前位置移动到第一个元素 */function front() {  this.pos = 0;}/** * 将列表的当前位置移动到最后一个元素 */function end() {  this.pos = this.listSize - 1;}/** * 返回当前位置的元素 * @returns {*} */function getElement() {  return this.dataSource[this.pos];}/** * 将当前位置向前移动一位 */function prev() {  --this.pos;}/** * 将当前位置向后移动一位 */function next() {  ++this.pos;}/** * 返回列表的当前位置 * @returns {number|*} */function currentPos() {  return this.pos;}/** * 移动到指定位置 * @param position */function moveTo(position) {  this.pos = position;}/** * 是否包含某个元素 * @param element * @returns {boolean} */function contains(element) {  if(!this.listSize) return false  var index = this.dataSource.indexOf(element)  return index}/** * 迭代器：遍历出所有的元素及其位置 * @param function(index, data) */function loop (cb) {  for(this.front();this.currentPos()