本文實例講述了JS中的算法與數據結構之列表(List)。分享給大家供大家參考，具體如下：
前端很少有機會接觸到算法，大多都交互性的操作，所以不少前端工程師會抱著這么一種想法：我是做前端的，為什么要學數據結構與算法？沒有數據結構與算法，我一樣很好的完成工作。實際上，算法是一個寬泛的概念，我們平時寫的任何代碼都可以成為算法，它是對一個問題的解決方案的準確而完整的描述，是解決一系列問題的清晰指令，它代表著用系統的方法描述解決問題的策略機制。隨著現在互聯網的飛速發展，前端工程師已不是靠幾個選擇器操作加鏈接加事件就能應付的，越來越復雜的產品和基礎庫，需要堅實的數據結構與算法才能駕馭，所以我認為前端工程師也是應該要重視算法和數據結構，這對于自己的職業發展是有很大幫助的。當然，算法的學習也不是一朝一夕的事情，這是一個過程，得自己去摸索，去實踐，去總結，我這里只是將一些常見的算法和數據結構用 JavaScript 去實現，起到一個拋磚引玉的作用。
列表是計算機中一種常見的數據結構，日常生活中的購物清單，待辦事項等都可以成為列表，它是一組有序的數據，每個列表中的數據項稱為元素。在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 方法刪除一個元素
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;
}
我想知道我的列表還有多少個元素的時候，就得構建 length 方法，
length：返回列表中總的元素個數
//該方法直接將 listSize 返回即可
function length(){
return this.listSize;
}
如果能顯示我的列表元素就好了，這個可以有，我們來看看 toString 方法，
toString：顯示列表的元素
//該方法直接返回了列表數組，顯示出當前列表內容
function toString(){
return this.dataStore;
}
現在我們的列表已經有了基本的一些功能，不妨下試試
//構造列表對象
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"]
如果我們刪除了 Grape 元素 ， 我們還想將它放回到原來的位置 ，這時候我們就需要調用 insert 方法
insert：向列表某個位置添加一個元素
//該方法需要傳入兩個參數，第一個參數表示待插入的元素，第二個參數表示待插入元素的前一個元素，用于確定插入元素的位置，并調用 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;
}
現在，我們把 Grape 放到原來的位置上去;
fruits.insert( 'Grape' , 'Apple' ); console.log( fruits.toString() ) // ["Apple", "Grape", "Banana"]
ok，現在已經能夠把 Grape 插入到原來的位置了。
如果我吃完了所有水果，我現在想要清空列表，我們就需要一個 clear 方法；
clear：清空列表
//該方法使用 delete 操作符刪除 dataStore 數組 ， 接著創建新的數組，并將其 listSize 和 pos 初始化設為 1 。
function clear(){
delete this.dataStore;
this.dataStore = [];
this.listSize = this.pos = 0;
}
我們不妨試一試。
fruits.clear(); console.log( fruits.toString() ); // []
成功了！
上面我們看到了列表中有個 pos 屬性，表示當前列表所在的位置，我們接下來就圍繞它做點事情，讓用戶可以自由操作列表
front：將列表的位置移到第一個位置上
//該方法只要將 pos 置為 0 即可
function front(){
this.pos = 0 ;
}
end：將列表的位置移到最后一個位置上
//同上，該方法只要將 pos 置為列表長度減 1 即可，因為數組下標從 0 開始嘛
function end(){
this.pos = this.listSize - 1;
}
prev：將當前位置前移一位
//只要將 pos 的位置減 1 即可，但要主要不能越界
function prev(){
if( this.pos > 0 ){
this.pos --;
}else{
console.log('您當前已在首位');
}
}
next：將當前位置后移一位
//同理，只要將 pos 的位置加 1 即可，但要主要不能越界
function next(){
if( this.pos < this.listSize - 1 ){
++this.pos;
}else{
console.log('您當前已在末尾');
}
}
moveTo：將當前位置移動到指定位置
//直接改變 pos 的值即可，注意輸入的合法性
function moveTo( position ){
if( position < 0 || position > (this.listSize - 1) ){
console.log('請輸入正確的位置');
}else{
this.pos = position;
}
}
我既然可以隨意改變我的列表位置，那我總得知道我當前位置在哪里啊，因此我們需要 currPos 和 getElement 兩個方法分別返回當前的位置和元素;
currPos：返回列表的當前位置
//只需將 pos 直接返回即可
function currPos(){
return this.pos;
}
getElement：返回當前位置的元素
//直接取對應的元素就好
function getElement(){
return this.dataStore[this.pos];
}
接著，我們測試一下，首先將列表恢復到清空前的樣子，然后我們在多添加幾個元素進去。
//再添加幾個
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
至此，我們已經基本完成了列表的所有功能，還差最后一個，判斷給定元素是否在列表內，我們這里采用 contains 方法
contains：判斷給定值是否在列表中
//我們直接利用利用 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 );
}
( ps：對 ES6 不太熟悉的同學，也可以參考本站https://www.jb51.net/article/138409.htm )
寫完測試一下，
console.log(fruits.contains('Banana')); // true
console.log(fruits.contains('Watermelon')); // false
大功告成！我們自己用 javascript 實現了一個列表，至于后面如何拓展，自己可以發散思維，多動手實踐實踐，一起加油！
感興趣的朋友可以使用在線HTML/CSS/JavaScript代碼運行工具：http://tools.jb51.net/code/HtmlJsRun測試上述代碼運行效果。
更多關于JavaScript相關內容感興趣的讀者可查看本站專題：《JavaScript數學運算用法總結》、《JavaScript數據結構與算法技巧總結》、《JavaScript數組操作技巧總結》、《JavaScript排序算法總結》、《JavaScript遍歷算法與技巧總結》、《JavaScript查找算法技巧總結》及《JavaScript錯誤與調試技巧總結》
希望本文所述對大家JavaScript程序設計有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
