JS中的算法与数据结构之列表(List)实例详解

(编辑：jimmy 日期: 2024/11/28 浏览：3 次 )

本文实例讲述了JS中的算法与数据结构之列表(List)。分享给大家供大家参考，具体如下：

前言

前端很少有机会接触到算法，大多都交互性的操作，所以不少前端工程师会抱着这么一种想法：我是做前端的，为什么要学数据结构与算法？没有数据结构与算法，我一样很好的完成工作。实际上，算法是一个宽泛的概念，我们平时写的任何代码都可以成为算法，它是对一个问题的解决方案的准确而完整的描述，是解决一系列问题的清晰指令，它代表着用系统的方法描述解决问题的策略机制。随着现在互联网的飞速发展，前端工程师已不是靠几个选择器操作加链接加事件就能应付的，越来越复杂的产品和基础库，需要坚实的数据结构与算法才能驾驭，所以我认为前端工程师也是应该要重视算法和数据结构，这对于自己的职业发展是有很大帮助的。当然，算法的学习也不是一朝一夕的事情，这是一个过程，得自己去摸索，去实践，去总结，我这里只是将一些常见的算法和数据结构用 JavaScript 去实现，起到一个抛砖引玉的作用。

列表(List)

列表是计算机中一种常见的数据结构，日常生活中的购物清单，待办事项等都可以成为列表，它是一组有序的数据，每个列表中的数据项称为元素。在javascript中，列表中的元素可以是任意数据类型。列表中可以保存多少元素并没有限定（在实际使用时会受到程序内存的限制）。列表中会有一些常见属性或方法，比如列表中的元素个数，列表当前的位置，向列表末尾增加一个元素，从列表中删除一个元素，清空列表等一系列操作。接下来，我们抽象出一个列表的数据类型定义，并用JS中的数组去实现它。

列表的数据类型定义

列表类

/*定义List类*/
 function List () {
  this.listSize = 0;  //初始化元素个数为0
  this.pos = 0;    //初始化位置为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.contains = contains; //判断给定值是否在列表中
}

接着我们来实现这些方法。

首先得可以添加元素，所以我们先来编写 append 方法

append：向列表中添加一个元素

//该方法给列表的最后一个位置添加一个新的元素，待插入成功后，更新列表中的元素个数

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

这样我们就可以往列表里面添加元素了，接着我们来看查找 find 方法

find：查找列表中的某一个元素

//该方法通过循环查找给定元素是否在列表中，如果存在返回元素的位置，否则返回 -1

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

可以插入元素，那总得可以删除了，我们利用 remove 方法删除一个元素

//该方法通过使用find()方法返回元素的位置对 dataStore 数组进行截取，如果删除成功，返回 true , 并将 listSize 的值减1，更新列表长度，否则返回 false function remove ( element ) { var foundAt = this.find(element); if( foundAt > -1 ){ this.dataStore.splice( foundAt , 1 ); --this.listSize; return true; } return false; }

//构造列表对象 var fruits = new List(); //添加三个元素 fruits.append('Apple'); fruits.append('Grape'); fruits.append('Banana'); //打印列表 console.log( fruits.toString() ) // ["Apple", "Grape", "Banana"] //查看列表长度 console.log( fruits.length() ) // 3 //查找 Banana 的位置 console.log( fruits.find('Banana') ) // 2 //删除 Grape fruits.remove('Grape'); console.log( fruits.toString() ) // ["Apple", "Banana"]

//该方法需要传入两个参数，第一个参数表示待插入的元素，第二个参数表示待插入元素的前一个元素，用于确定插入元素的位置，并调用 splice 方法更改列表数组，插入成功后更新 listSize 并返回 true ，否则返回 false； 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; }

//该方法使用 delete 操作符删除 dataStore 数组，接着创建新的数组，并将其 listSize 和 pos 初始化设为 1 。 function clear(){ delete this.dataStore; this.dataStore = []; this.listSize = this.pos = 0; }

//同理，只要将 pos 的位置加 1 即可，但要主要不能越界 function next(){ if( this.pos < this.listSize - 1 ){ ++this.pos; }else{ console.log('您当前已在末尾'); } }

//直接改变 pos 的值即可，注意输入的合法性 function moveTo( position ){ if( position < 0 || position > (this.listSize - 1) ){ console.log('请输入正确的位置'); }else{ this.pos = position; } }

//再添加几个 fruits.append('Pear'); fruits.append('Orange'); fruits.append('Strawberry'); console.log( fruits.toString() ); // ["Apple", "Grape", "Banana", "Pear", "Orange", "Strawberry"] //我们先看当前的位置和元素 console.log( fruits.currPos() ); // 0 console.log( fruits.getElement() ); // Apple //我们尝试改变一下 fruits.moveTo( 2 ); fruits.next(); console.log( fruits.currPos() ); // 3 console.log( fruits.getElement() ); // Pear fruits.end(); fruits.prev(); console.log( fruits.currPos() ); // 4 console.log( fruits.getElement() ); // Orange

//我们直接利用利用 indexOf() 或者采用跟为高级的 ES6 中的 includes 方法来判断 //ES5 function contains( element ){ if( this.dataStore.indexOf( element ) > -1 ) return true; else return false; } //ES6 function contains( element ){ return this.dataStore.includes( element ); }