《Javascript數據結構和算法》筆記-「鏈表」

gclove 發布于2019-08-26 13:22 / 2902人閱讀

摘要：鏈表數據結構與算法第五章鏈表數據結構鏈表不同與數組數組要插入或者移入一個元素的成本很高，因為所有元素都需要移動位置。

JavaScript-鏈表

《Javascript數據結構與算法》第五章

5.1 鏈表數據結構

鏈表不同與數組

數組要插入或者移入一個元素的成本很高，因為所有元素都需要移動位置。

鏈表插入或者移動一個元素時很高效，因為并不需要移動其他的元素位置。

鏈表存儲元素的方式，在內存中不是有順序的，每一個元素由

1.存儲元素本身的節點

2.指向一下元素的指針組成

5.2 創建鏈表

5.2.0 創建鏈表的骨架

1.鏈表需要有一個 Node 類，表示要加入鏈表的項，它包括 2 個部分，一個是該項的值，和一個只想下一項的指針

2.鏈表還需要個表示鏈表長度的屬性 length

3.表示第一項的引用 head

4.和一系列增刪改查、查詢長度的方法

function LinkedList() {
    function Node(element) {
        this.element = element;
        this.next = null;
    }

    this.length = 0;
    this.head = null;

    this.append = function(element) {};
    this.insert = function(position, element) {};
    this.remove = function(position) {};
}

5.2.1 append，向鏈表尾部添加元素

this.append = function(element) {
    var node = new Node(element); //此時node實例 {element:"111",next:null}

    this.length + 1;

    if (this.head === null) {
        this.head = node;
    } else {
        //插入到最后一項，但是由于沒有順序，所以我們沒法直接得到鏈表的最后一項，只能while循環next為null
        let lastNode = head;
        while (lastNode.next !== null) {
            lastNode = lastNode.next;
        }
        lastNode.next = node;
    }
};

5.2.2 removeAt 從鏈表中刪除元素

思路就是分 2 個情況

如果要刪除第 0 項，就把 head 指向 head.next 就行了

如果要刪除第 n 項，需要 while 循環找到這當前這個 current 項目，將 current 的前一項的 next，越過 current，指向指向 current 的下一項

這樣當前元素被丟棄在計算機內存中，就等著被垃圾回收機制，自己回收了。

this.removeAt = function(position) {
    // 檢查是否position參數的邊界
    if (position > -1 && position < length) {
        let current = head,
            previous, // 表示position上一項元素
            index = 0;

        if (position === 0) {
            head = current.next;
        } else {
            // 如果index++，一直到index追上position時，那么這個current就是position索引對應的元素了
            while (index++ < position) {
                previous = current;
                current = current.next;
            }
            // 讓position對應的元素的，上一項的next，越過要刪除的這一項，直接指向下一項元素就好了
            previous.next = current.next;
        }
        length--;
        return current;
    } else {
        return null;
    }
};

5.2.3 insert 在某個位置插入

this.insert = function(position, element) {
    if (position >= 0 && position < length) {
        let node = new Node(element);
        let index = 0;
        let current = head;
        let previous;
        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;
    }
};

5.2.4 toString 打印鏈表

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

5.2.5 size 獲取鏈表長度

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

雙向鏈表骨架

以上是單向鏈表的JS實現，實際上鏈表還有多種不同的類型，比如雙向鏈表、循環鏈表

雙向鏈表和單向鏈表的一個區別在于，每一個item，不僅僅包括value和next指針，還包括prev指針

同時雙向鏈表不僅僅保存head，也保存最后一項的引用。

這樣的好處是：迭代單向鏈表時，如果錯過了某一項，只能重新迭代，但是雙向鏈表就找到上一項

function DoublyLinkedList(){
    let Node = function(){
        this.element = element;
        this.next = null;
        this.prev = null;  // 指向上一項的指針
    }

    let length = 0;
    let head = null;
    let tail = null;  // 保存最后一項的索引
}

循環鏈表

循環鏈表，是指最后一項的指針不是null，而是指向第一個元素的一種鏈表。

所以循環鏈表，有可能是單向鏈表，也可能是雙向鏈表

雙向循環鏈表，最后一項的指針指向head，第一項的指針指向tail

GPU云服務器云服務器鏈表算法鏈表排序算法算法 c語言鏈表 javascript學習筆記

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/108706.html

《JavaScript數據結構與算法》筆記——第5章鏈表

摘要：鏈表存儲有序的元素集合，不同于數組，鏈表中的元素在內存中并不是連續放置，每個元素有一個存取元素本身的節點和一個指向下一個元素的引用組成。優點添加或者移除元素的時候不需要移動其他元素。鏈表存儲有序的元素集合，不同于數組，鏈表中的元素在內存中并不是連續放置，每個元素有一個存取元素本身的節點和一個指向下一個元素的引用組成。優點：添加或者移除元素的時候不需要移動其他元素。只需要找到加入的節...

sutaking 2019-08-26 13:28 評論0 收藏0
CSS技巧

摘要：技巧使你的更加專業這是上關于技巧的一篇譯文，另外你也可以在本項目看到原文。列舉了一些很實用的技巧，比如給空內容的標簽添加內容，逗號分隔列表等等。排序算法看源碼，把它背下來吧排序算法的封裝。主要幫助初學者更好的掌握排序算法的實現。成為專業程序員路上用到的各種優秀資料、神器及框架成為一名專業程序員的道路上，需要堅持練習、學習與積累，技術方面既要有一定的廣度，更要有自己的深度。 Java...

DangoSky 2019-08-22 11:15 評論0 收藏0
CSS技巧

摘要：技巧使你的更加專業這是上關于技巧的一篇譯文，另外你也可以在本項目看到原文。列舉了一些很實用的技巧，比如給空內容的標簽添加內容，逗號分隔列表等等。排序算法看源碼，把它背下來吧排序算法的封裝。主要幫助初學者更好的掌握排序算法的實現。成為專業程序員路上用到的各種優秀資料、神器及框架成為一名專業程序員的道路上，需要堅持練習、學習與積累，技術方面既要有一定的廣度，更要有自己的深度。 Java...

zgbgx 2019-08-29 14:01 評論0 收藏0
CSS技巧 - 收藏集 - 掘金

摘要：筆者作為一位，將工作以來用到的各種優秀資料神器及框架整理在此，畢竟好記性不如爛鍵盤，此前端知識點大百科全書前端掘金，，不定期更新技巧前端掘金技巧，偶爾更新。計算數組的極值技巧使你的更加專業前端掘金一個幫你提升技巧的收藏集。 CSS 樣式畫各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經常用到的圖案，還有一些是在css-tricks看到的。記錄一下，以后會用到。會持續更新… 一、...

Jonathan Shieber 2019-08-29 12:33 評論0 收藏0
CSS技巧 - 收藏集 - 掘金

摘要：筆者作為一位，將工作以來用到的各種優秀資料神器及框架整理在此，畢竟好記性不如爛鍵盤，此前端知識點大百科全書前端掘金，，不定期更新技巧前端掘金技巧，偶爾更新。計算數組的極值技巧使你的更加專業前端掘金一個幫你提升技巧的收藏集。 CSS 樣式畫各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經常用到的圖案，還有一些是在css-tricks看到的。記錄一下，以后會用到。會持續更新… 一、...

SHERlocked93 2019-08-22 11:04 評論0 收藏0