Javascript資料結構與演算法列表詳解_javascript技巧

前言：在日常生活中，人們經常要使用列表，比如我們有時要去購物時，為了購物時東西要買全，我們可以在去之前，列下要買的東西，這就要用的列表了，或者我們小時候上學那段時間，每次考完試後，學校都會列出這次考試成績前十名的同學的排名及成績單，等等這些都是列表的列子。我們計算機內也在使用列表，那麼列表適合使用在什麼地方呢？不適合使用在什麼地方呢？

適合使用在：當列表的元素不是很多的情況下，可以使用列表，因為對列表中的元素查找或排序時，效率還算非常高，反之：如果列表元素非常多的情況下，就不適合使用清單了。

一：列表的抽象資料型別定義

為了設計清單的抽象資料類型，我們需要給出清單的定義，包括清單應該擁有哪些屬性，應該在清單上執行哪些操作等。

列表是一組有序的資料。每個列表中的資料項稱為元素。在javascript中，清單中的元素可以是任意資料類型。清單中可以保存多少元素並沒有事先約定。但是實際使用時元素數量受到程式記憶體的限制。

現在我們想設計一個列表，那麼我們可以想想實現一個列表，他們應該包含哪些屬性和方法，當然我下面的設計都是根據"javascript資料結構與演算法" 書上的demo來設計的，為止我們可以學習下，如果以後我們寫程式時，該如何來設計我們自己的抽象類別來作為一個參考，我們現在學習書上的demo最主要的是學習他們中的設計思想及編寫程式碼的方式。他們有以下屬性；

 1. listSize（屬性）：使用一個listSize變數來保存清單中元素的個數。
 2. pos(屬性)：  清單的目前位置，元素的索引。
 3. dataStore(屬性)： 初始化一個空數組來保存元素的個數。如果我們想要取得具體的列表中的元素 可以使用上面的pos屬性；如 dataStore[pos];

所有的方法；如下列表解釋，不一一介紹了。

二：如何實作列表類別

根據上面定義的列表抽象資料類型，我們可以實作如下一個List類，如下透過建構子 原型模式。

複製程式碼 程式碼如下:

function List() {
    // 清單的元素數量
    this.listSize = 0;

    // 清單的目前位置 是第幾個
    this.pos = 0;

    // 初始化一個空數組來保存列表元素
    this.dataStore = [];

}

List.prototype = {
   
    // 在清單末端新增元素
    append: function(element) {
        var self = this;
        self.dataStore[this.listSize ] = element;
    },

    // 從清單中移除元素
    remove: function(element) {
        var self = this;
        var curIndex = self.find(element);
        if(curIndex > -1) {
            self.dataStore.splice(curIndex,1);
            --self.listSize;
            return true;
        }
        return false;
    },

    // 尋找清單中的元素 回傳索引
    find: function(element) {
        var self = this;
        for(var i = 0,dataLen = self.dataStore.length; i             if(self.dataStore[i] == element) {
                return i;
            }
        }
        return -1;
    },
   
    // 傳回清單中元素的數量
    length: function() {
        return this.listSize;
    },

    // 顯示清單中的元素
    toString: function(){
        return this.dataStore;
    },

    /*
     * 在指定元素後面插入一個元素
     * @param element 目前的元素
     * @param elementAfter 把目前的元素插入到此元素後面
     */
    insert: function(element,elementAfter){
        var self = this;
        var insertPos = self.find(elementAfter);
        if(insertPos > -1) {
            self.dataStore.splice(insertPos 1,0,element);
            self.listSize;
            return true;
        }
        return false;
    },
   
    // 清空清單中的所有元素
    clear: function() {
        delete this.dataStore;
        this.dataStore = [];
        this.listSize = this.pos = 0;
    },
    // 判斷給定的元素是否在列表中
    contains: function(element) {
        var self = this;
        for(var i = 0,ilen = self.dataStore.length; i             if(self.dataStore[i] == element) {
                return true;
            }
        }
        return false;
    },
    // 將清單中的目前元素移到第一個位置
    front: function(){
        this.pos = 0;
    },
    // 將清單中目前的元素移到最後一個位置
    end: function(){
        this.pos = this.listSize - 1;
    },
    // 將目前位置 後移一位
    prev: function(){
        if(this.pos > 0) {
            --this.pos;
        }
    },
    // 將目前位置 前移一位
    next: function(){
        if(this.pos             this.pos;
        }
    },
    // 返回清單的目前位置
    curPos: function(){
        return this.pos;
    },
    // 將目前位置移到指定位置
    moveTo: function(n) {
        this.pos = n;
    },
    // 傳回目前位置的元素
    getElement:function(){
        return this.dataStore[this.pos];
    }
};

如上：實作一個列表類，包含上面的如上那麼多方法，當然我們也可以擴展一些其他的方法，來豐富實現列表類，最主要可以學習如上編碼方式。