賴同學

賴同學

請多多指教

github hexo

為什么我要放棄javaScript數據結構與算法(第五章)—— 鏈表

這一章你將會學會如何實現和使用鏈表這種動態的數據結構,這意味著我們可以從中任意添加或移除項,它會按需進行擴張。

本章內容

  • 鏈表數據結構
  • 向鏈表添加元素
  • 從鏈表移除元素
  • 使用 LinkedList 類
  • 雙向鏈表
  • 循環鏈表

第五章 鏈表

鏈表數據結構

要存儲多個元素,數組(或列表)可能是最常見的數據結構了。然后這種數據結構有一個缺點:數組的大小是固定的,從數組的起點或中間插入或移除項的成本有點高,因為需要移動元素。

鏈表存儲有序的元素集合,但不同于數組,鏈表中的元素在內存并不是連續放置的。每個元素由一個存儲元素本身的節點和一個指向下一個元素的引用(也稱指針或鏈接)組成,下圖展示了一個鏈表的結構。

鏈表數據結構

相對于傳統的數組,鏈表的一個好處在于,添加或者移除元素的時候不需要移動其他元素,然后,鏈表需要使用指針,因為實現鏈表時需要額外注意。數組的另一個細節是可以直接訪問任何位置的任何元素,而想要訪問鏈表中間的一個元素,需要從起點(表頭)開始迭代列表直到找到所需的元素。

現實中也有一些鏈表的例子,第一個例子就是康加舞隊,每個人就是一個元素,手就是鏈向下一個人的指針,可以向隊列匯總增加人——只需要找到想加入的點,斷開連接,插入一個人,再重新連接起來。

另外一個例子就是尋寶游戲,你有一條線索,這條線索是指向尋找下一個線索的地點的指針,你順著這條鏈去下一個地點,得到另一條指向再下一處的線索。得到列表中間的線索的唯一方法,就是從起點(第一個線索)順著列表尋找。

還有一個可能就是用來說明鏈表中的最流行的例子,那就是火車。一列火車是由一系列車廂(也稱車皮)組成的。每節車廂或車皮都互相連接。可以很容易的分離開一節車皮,改變它的位置,添加或移除它。

創建鏈表

了解鏈表是什么之后,就要開始實現我們的數據結構了,一下是我們的 LinkedList 類的骨架:

function LinkedList(){
    let Node = function(element){ // 需要一個Node輔助類,表示要加入列表的項,element 代表要添加到列表中的值, next d代表指向列表的下一個節點向的指針
        this.element = element;
        this.next = null;
    }

    let length = 0; // 存儲列表項的數量 length 屬性
    let head = null; // 存儲第一個節點的引用在 head 變量

    this.append = function(element){};
    this.insert = function(position,element){}
    this.removeAt = function(position){}
    this.remove = function(element){}
    this.indexOf = function(position){}
    this.isEmpty = function(){}
    this.size = function(){}
    this.getHead = function(){}
    this.toString = function(){}
    this.print = function(){}

}

LinkedList 類的方法的功能

  • append(element):向列表尾部添加一個新的項
  • insert(position,element):向列表的特定位置插入一個新的項
  • removeAt(position):從列表的特定位置移除一項
  • remove(element):從列表中移除一項
  • indexOf(element):返回元素在列表中的索引。如果列表中沒有該元素則返回-1
  • isEmpty():如果鏈表中不包含任何元素,返回true,如果鏈表的長度大于0則返回 false
  • size():返回鏈表包含的元素個數,與數字的 length 屬性類似
  • toString():由于列表項使用 Node 類,就需要重寫繼承自 JavaScript 對象默認的 toString 方法,讓其只輸出元素的值。

向鏈表尾部追加元素

向 LinkedList 對象尾部添加一個元素時,可能有兩種場景,列表為空,添加的是第一個元素,或者列表不為空,向追加元素。

this.append = function(element){
    let node = new Node(element),current;
    if(head === null){
        head = node;
    }else{
        current = head;
        // 循環列表,直到找到最后一項
        while(current.next){
            current = current.next;
        }
        // 當current.next元素為null時,找到最后一項,將其 next 賦為 node,建立連接
        current.next = node;
    }
    length++;  // 更新列表的長度
};

可以在 append 函數 加上return node ,通過下面的代碼來使用和測試目前創建的數據結構

let list = new LinkedList();
console.log(list.append(15)); // Node?{element: 15, next: null}
console.log(list.append(10)); // Node?{element: 10, next: null}

從鏈表中移除元素

移除元素也有兩種場景:第一種是移除第一個元素,第二種是移除第一個以外的任一元素。我們要實現兩種 remove 方法:第一種是從特定位置移除第一個元素,第二種是根據元素的值移除元素。

首先先實現移除特定位置的元素

this.removeAt = function(position){
    // 檢查越界值
    if(position >-1 && position < length){
        let current = head,previous,index = 0;

        // 移除第一項
        if(position === 0){
            head = current.next;
            console.log(current.element);
        }else{
            while(index++ < position){
                previous = current;
                current = current.next;
            }
            // 將 previous 與 current 的下一項連接起來,跳過 current,從移除它
            previous.next = current.next;
        }
        length --;
        console.log(current.element);
        return current.element;
    }else{              
        return null;
    }           
}

如果想要移除第一個元素(position=0),要做的就是讓 head 指向列表的第二個元素,我們用 current 變量穿甲一個對列表中第一個元素的應用,這樣 current 變量就是對列表中第一個元素的引用,如果吧 head 賦值為 current.next 就會移除第一個元素。

如果我們要移除列表的最后一項或者是中間的一項,為此,需要依靠一個細節來迭代列表,知道到達目標位置(index++ < position),使用一個用于內部控制和遞增的 index 變量,current 變量總是對所循環列表的當前元素的引用(current = current.next),我們還需要一個對當前元素的前一個元素的引用(previous = current),它被命名為 previous。

因此,要從列表中移除當前元素,要做的就是將 previous.next 和 current.next 鏈接起來,這樣當前元素就會被丟棄在計算機內存中,等著被垃圾回收站清除。

對于最后一個元素,在(while(index++ < position))跳出循環時, current 變量總是對列表中最后一個元素的引用(要移除的元素)。current.next 的值將是 null(因為它是最后一個元素)。由于還保留了對 previous 的引用(當前元素的前一個元素),previous 就指向了 current 。那么要移除 current,要做的就是把 previous.next 的值改變為 current.next 。

在任意位置插入元素

實現 insert 方法,使用這個方法可以在任意位置插入一個元素。

this.insert = function(position,element){
    // 檢查越界值
    if(position >=0 && position <= length){
        let node = new Node(element),
        current = head,
        previous,
        index = 0;
        if(position === 0 ){ // 在第一個位置添加
            node.next = current;
            head = node;
        }else{
            while(index++ < position){
                previous = current;
                current = current.next;
            }
            node.next = current;
            previous.next = node;
        }
        length++;
        return true;
    }else{
        return false;
    }
}

current 變量是對列表中第一個元素的引用,我們需要做的是把 node.next 的值設為 current (列表中的第一個元素),現在 head 和 node.next 都指向了 current ,接下來要做的就是把 head 的引用改為 node ,這樣列表中就有了一個新元素。

現在來處理第二種場景,在列表中間或者末尾添加一個新的元素。首先,循環訪問列表,找打目標為位置,當跳出循環的時候, current 變量將是對想要插入新元素的位置之后一個元素的引用,而 previous 將是對想要插入新元素的位置之前的一個元素的引用。在這種情況下,我門要在 previous 和 current 之間添加新項。因此,需要將新項(node)和當前鏈接起來(node.next = current),然后需要改變 previous 和 current z之間的鏈接,我們還需要讓 previous.next 指向 node。

實現其他方法

toString方法

this.toString = function(){
    let current = head,
    string = '';
    while(current){
        string += current.element + (current.next ? '-':'');
        current = current.next;
    }
    return string;
}

賦值current為 head, 循環訪問 current,將 current 變量當做索引,初始化用于拼接元素的變量(string)。通過 current 來檢查元素是否存在,如果列表為空或是到達列表中最后一個元素的下一位(null),while 循環中的代碼就不會執行,就可以得到元素的內容,將其拼接到字符串中,最后,迭代下一個元素。最后,返回列表內容的字符串。

indexOf方法

indexOf方法接受一個元素的值,如果在列表中找到它,就返回元素的位置,否則返回 -1

this.indexOf = function(element){
    let current = head,
    index = 0;
    while(current){
        if(element === current.element){
            return index;
        }
        index++;
        current = current.next;
    }
    return -1;
}

循環變量 current,它的初始值是 head ,利用index 來計算位置數。訪問元素,檢查當前元素是否是我們要找的,如果是,就返回它的位置,不是就繼續計數,檢查列表中的下一個節點。

如果列表為空,或是到達列表的尾部(current = current.next 將是 null),循環就不會執行。如果沒有找到值就返回 -1 。

實現了上面的方法,就可以實現remove等其他方法了

remove方法

this.remove = function(element){
    let index = this.indexOf(element);
    return this.removeAt(index);
}

isEmpty、size 和 getHead方法

isEmpty和size 和之前章節實現一模一樣

this.isEmpty = function(){
    return length === 0;
}

this.size = function(){
    return length;
}

還有 getHead方法

this.getHead = function(){
    return head;
}

head 變量是 LinkedList 類的私有變量,我們如果需要在類的實現外部循環訪問列表,就需要提供一種獲取類的第一個元素的方法。

整個 LinkedList函數

function LinkedList(){
    let Node = function(element){ // 需要一個Node輔助類,表示要加入列表的項,element 代表要添加到列表中的值, next d代表指向列表的下一個節點向的指針
        this.element = element;
        this.next = null;
    }

    let length = 0; // 存儲列表項的數量 length 屬性
    let head = null; // 存儲第一個節點的引用在 head 變量

    this.append = function(element){
        let node = new Node(element),current;
        if(head === null){
            head = node;
        }else{
            current = head;
            // 循環列表,直到找到最后一項
            while(current.next){
                current = current.next;
            }
            // 當current.next元素為null時,找到最后一項,將其 next 賦為 node,建立連接
            current.next = node;
        }
        length++;  // 更新列表的長度
    };

    this.insert = function(position,element){
        // 檢查越界值
        if(position >=0 && position <= length){
            let node = new Node(element),
            current = head,
            previous,
            index = 0;
            if(position === 0 ){ // 在第一個位置添加
                node.next = current;
                head = node;
            }else{
                while(index++ < position){
                    previous = current;
                    current = current.next;
                }
                node.next = current;
                previous.next = node;
            }
            length++;
            return true;
        }else{
            return false;
        }
    }

    this.removeAt = function(position){
        // 檢查越界值
        if(position >-1 && position < length){
            let current = head,previous,index = 0;

            // 移除第一項
            if(position === 0){
                head = current.next;
                console.log(current.element);
            }else{
                while(index++ < position){
                    previous = current;
                    current = current.next;
                }
                // 將 previous 與 current 的下一項連接起來,跳過 current,從移除它
                previous.next = current.next;
            }
            length --;
            return current.element;
        }else{              
            return null;
        }           
    }

    this.remove = function(element){
        let index = this.indexOf(element);
        return this.removeAt(index);
    }

    this.indexOf = function(element){
        let current = head,
        index = 0;
        while(current){
            if(element === current.element){
                return index;
            }
            index++;
            current = current.next;
        }
        return -1;
    }

    this.isEmpty = function(){
        return length === 0;
    }

    this.size = function(){
        return length;
    }

    this.getHead = function(){
        return head;
    }

    this.toString = function(){
        let current = head,
        string = '';
        while(current){
            string += current.element + (current.next ? '-':'');
            current = current.next;
        }
        return string;
    }

}

雙向鏈表

鏈表有多種不同的類型,這一節介紹 雙向鏈表,雙向鏈表和普通鏈表的區別在于,在鏈表中,一個節點只有鏈向下一個鏈接,而在雙向鏈表中,鏈接是雙向的:一個鏈向下一個元素,另一個鏈向前一個元素。如下圖所示

雙向鏈表

先從實現 DoublyLinkedList 類所需要的變動開始

function DoublyLinkedList(){
    let Node = function(elememt){
        this.elememt = elememt;
        this.next = null;
        this.prev = null; // 新增的
    }
    let length = 0;
    let head = null;
    let tail = null // 新增的

    // 這里是方法
}

可以看出,Node 類中新增了 prev屬性(一個新指針),在 DoublyLinkedList 類里也有用來保存對列表最后一項的引用的 tail 屬性。

雙向鏈表提供了兩種迭代列表的方式:從頭到尾,或者從尾到頭。我們也可以方位一個特定節點的下一個或者是上一個元素。在單向鏈表中,如果迭代列表時錯過了要找的元素,就需要回到列表起點,重新迭代。這是雙向鏈表的一個優點。

在任意位置插入新元素

向雙向鏈表中插入一個新項跟(單向)鏈表非常相類似。區別在于,鏈表只要控制一個 next 指針,而雙向鏈表則要同時控制 next 和 prev (previous,前一個)這兩個指針。

this.insert = function(position,elememt){
    // 檢查越界值
    if(position >= 0 && position <= length){
        let node = new Node(elememt),
        current = head,
        previous,
        index = 0;
        if(position === 0){ // 在第一個位置添加
            if(!head){
                head = node;
                tail = node;
            }else{
                node.next = current;
                current.prev = node;
                head = node;
            }
        }else if(position === length){ // 最后一項
            current = tail;
            current.next = node;
            node.prev = current;
            tail = node;
        }else{
            while (index++ < position) {
                previous = current;
                current = current.next;
            }
            node.next = current;
            previous.next = node;

            current.prev = node;
            node.prev = previous;
        }
        length++
        return true;
    }else{
        return false;
    }
}   

在列表的第一個位置(列表的起點)插入一個新元素,如果列表為空(if(!head)),那只需將 head 和 tail 都指向這個新節點。如果不為空, current 變量將是對列表中的第一個元素的引用。就像我們在鏈表中所做的,把 node.next 設為 current ,而head 將指針指向 node (它被設為列表中的第一個元素)。不同之處,我們還需要為指向上一個元素的指針設一個值。current.prev 指針將由 指向 null 變成指向 新元素(current.prev = node)。node.prev 指針已經是 null,因此不需要在更新任何東西了。

假如我們要在列表最后添加一個新元素。這是一個特殊情況,因為我們還控制著指向最后一個元素的指針(tail)。current 變量將引用最后一個元素(current = tail)。然后分開建立第一個鏈接:node.prev 將引用current。current.next 指針(指向null)將指向 node (由于構造函數,node.next 已經指向了 null)。然后只剩下一件事,就是更新 tail ,它將由 指向 current 變成指向 node 。

第三種場景:在列表中插入一個新元素,就像我們在之前方法中所做,迭代列表,知道到達要找的位置(while (index++ < position))。我們將在 current 和 previous 元素之間插入新元素。首先,node.next 將指向 current ,而 previous.next 將指向 node,這樣就不會跌勢節點之間的鏈接。然后需要處理所有的鏈接:current.prev 將指向node ,而 node.prev 將指向 previous

從任意位置移除元素

從雙向鏈表中移除元素跟鏈表非常類似。唯一區別就是還需要設置一個位置的指針。

this.removeAt = function(position){
    // 檢查越界值
    if(position > -1 && position < length){
        let current = head,
        previous,
        index = 0;
        // 移除第一項
        if(position === 0){
            head = current.next;
            // 如果只有一項,更新 tail
            if(length === 1){
                tail = null;
            }else{
                head.prev = null;
            }
        }else if(position === length-1){ // 最后一項
            current = tail;
            tail = current.prev;
            tail.next = null;
        }else{
            while (index++ < position) {
                previous = current;
                current = current.next;
            }
            // 將 previous 與 current 的下一項連接起來——跳過 current
            previous.next = current.next;
            current.next.prev = previous;
        }
        length --;
        return current.elememt;
    }else{
        return null;
    }
}

我們需要處理三種場景,從頭部、從中間和從尾部移除一個元素。

移除第一個元素。current 變量是對列表中第一個元素的引用,也就是我們想要移除的遠古三。需要做的就是改變 head 的引用,將其從 current 改為下一個元素(head = current.next;),但是我們還需要更新 current.next 指向上一個元素的指針(因為第一個元素的 prev 指針是 null)。因此,把 head.prev 的引用改為 null(因為 head 也指向了列表中的第一個元素,或者也可以用 current.next.prev )。由于還需要控制 tail 的引用,我們可以檢測要移除的是否是第一個元素,如果是,只需要把 tail 也設為 null。

移除最后一個位置的元素。既然已經有了對最后一個元素的引用(tail),我們就不需要為找到它而迭代列表。我們可以把 tail 的引用賦給 current 變量。接下來,就需要吧 tail 的引用更新為列表中的倒數第二個元素(current.prev,或者 tail.prev也可以)。既然 tail 指向了倒數第二個元素,我們需要把 next 指針更新為 null (tail.next = null)。

最后一種場景,從列表中移除一個元素。首先需要迭代列表,直到到達要找的位置。current 變量所引用的就是要移除的遠古三。那么要移除它,我們可以通過更新 previous.next 和 current.next.prev 的引用,在列表中跳過它。因此,previous.next 將 指向 current.next ,而 current.next.prev 將指向 previous。

完整代碼

function DoublyLinkedList(){
    let Node = function(elememt){
        this.elememt = elememt;
        this.next = null;
        this.prev = null; // 新增的
    }
    let length = 0;
    let head = null;
    let tail = null // 新增的


    this.append = function(elememt){
        let node = new Node(elememt),
        current;
        if(!head){
            head = node;
            tail = node;
        }else{
            current = tail;
            current.next = node;
            node.prev = current;
            tail = node;
        }
        length++;
    }

    this.insert = function(position,elememt){
        // 檢查越界值
        if(position >= 0 && position <= length){
            let node = new Node(elememt),
            current = head,
            previous,
            index = 0;
            if(position === 0){ // 在第一個位置添加
                if(!head){
                    head = node;
                    tail = node;
                }else{
                    node.next = current;
                    current.prev = node;
                    head = node;
                }
            }else if(position === length){ // 最后一項
                current = tail;
                current.next = node;
                node.prev = current;
                tail = node;
            }else{
                while (index++ < position) {
                    previous = current;
                    current = current.next;
                }
                node.next = current;
                previous.next = node;

                current.prev = node;
                node.prev = previous;
            }
            length++
            return true;
        }else{
            return false;
        }
    }   

    this.removeAt = function(position){
        // 檢查越界值
        if(position > -1 && position < length){
            let current = head,
            previous,
            index = 0;
            // 移除第一項
            if(position === 0){
                head = current.next;
                // 如果只有一項,更新 tail
                if(length === 1){
                    tail = null;
                }else{
                    head.prev = null;
                }
            }else if(position === length-1){ // 最后一項
                current = tail;
                tail = current.prev;
                tail.next = null;
            }else{
                while (index++ < position) {
                    previous = current;
                    current = current.next;
                }
                // 將 previous 與 current 的下一項連接起來——跳過 current
                previous.next = current.next;
                current.next.prev = previous;
            }
            length --;
            return current.elememt;
        }else{
            return null;
        }
    }

    this.remove = function(elememt){
        let index = this.indexOf(elememt);
        this.removeAt(index);
    }   

    this.toString = function(){
        let current = head,
        str = '';
        while (current) {
            str += current.elememt + (current.next?'-':'');
            current = current.next;
        }
        return str;
    }       

    this.indexOf = function(elememt){
        let current = head,
        index = 0;
        while (current) {
            if(current.elememt === elememt){
                return index
            }
            current = current.next;
            index++
        }
        return -1;
    }

    this.isEmpty = function(){
        return length === 0;
    }

    this.size = function(){
        return length;
    }

    this.getHead = function(){
        return head;
    }

}

循環鏈表

循環鏈表可以像鏈表一樣只有單向引用,也可以像雙向鏈表一樣有雙向引用。循環鏈表和鏈表之間唯一的區別在于,最后一個元素指向下一個元素的指針(tail.next)不是引用 null,而是指向第一個元素(head),如下圖所示

循環鏈表

雙向鏈表有指向 head 元素的 tail.next ,和指向 tail 元素的 head.prev

雙向循環鏈表

小結

這一章中,學習了鏈表這種數據結構,及其辯題雙向鏈表和循環鏈表,知道了如何在任意位置添加和移除元素,已經如何循環訪問兩邊,比數組重要的優點就是,無需移動鏈表中的元素,就能輕松添加和移除元素。當你需要添加和移除很多元素的時候,最好的選擇就是鏈表,而非數組。下一章將學習集合,最后一種順序數據結構。

書籍鏈接: 學習JavaScript數據結構與算法

posted @ 2018-11-03 11:25 賴同學 閱讀(...) 評論(...) 編輯 收藏
耐克篮球多少钱