成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

《Javascript數(shù)據(jù)結(jié)構(gòu)和算法》筆記-「鏈表」

gclove / 2969人閱讀

摘要：鏈表數(shù)據(jù)結(jié)構(gòu)與算法第五章鏈表數(shù)據(jù)結(jié)構(gòu)鏈表不同與數(shù)組數(shù)組要插入或者移入一個(gè)元素的成本很高，因?yàn)樗性囟夹枰苿?dòng)位置。

JavaScript-鏈表

《Javascript數(shù)據(jù)結(jié)構(gòu)與算法》第五章

5.1 鏈表數(shù)據(jù)結(jié)構(gòu)

鏈表不同與數(shù)組

數(shù)組要插入或者移入一個(gè)元素的成本很高，因?yàn)樗性囟夹枰苿?dòng)位置。

鏈表插入或者移動(dòng)一個(gè)元素時(shí)很高效，因?yàn)椴⒉恍枰苿?dòng)其他的元素位置。

鏈表存儲(chǔ)元素的方式，在內(nèi)存中不是有順序的，每一個(gè)元素由

1.存儲(chǔ)元素本身的節(jié)點(diǎn)

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

5.2 創(chuàng)建鏈表 
5.2.0 創(chuàng)建鏈表的骨架

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

2.鏈表還需要個(gè)表示鏈表長度的屬性 length

3.表示第一項(xiàng)的引用 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); //此時(shí)node實(shí)例 {element:"111",next:null}

    this.length + 1;

    if (this.head === null) {
        this.head = node;
    } else {
        //插入到最后一項(xiàng)，但是由于沒有順序，所以我們沒法直接得到鏈表的最后一項(xiàng)，只能while循環(huán)next為null
        let lastNode = head;
        while (lastNode.next !== null) {
            lastNode = lastNode.next;
        }
        lastNode.next = node;
    }
};
5.2.2 removeAt 從鏈表中刪除元素

思路就是分 2 個(gè)情況

如果要?jiǎng)h除第 0 項(xiàng)，就把 head 指向 head.next 就行了

如果要?jiǎng)h除第 n 項(xiàng)，需要 while 循環(huán)找到這當(dāng)前這個(gè) current 項(xiàng)目，將 current 的前一項(xiàng)的 next，越過 current，指向指向 current 的下一項(xiàng)

這樣當(dāng)前元素被丟棄在計(jì)算機(jī)內(nèi)存中，就等著被垃圾回收機(jī)制，自己回收了。

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

        if (position === 0) {
            head = current.next;
        } else {
            // 如果index++，一直到index追上position時(shí)，那么這個(gè)current就是position索引對應(yīng)的元素了
            while (index++ < position) {
                previous = current;
                current = current.next;
            }
            // 讓position對應(yīng)的元素的，上一項(xiàng)的next，越過要?jiǎng)h除的這一項(xiàng)，直接指向下一項(xiàng)元素就好了
            previous.next = current.next;
        }
        length--;
        return current;
    } else {
        return null;
    }
};
5.2.3 insert 在某個(gè)位置插入
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實(shí)現(xiàn)，實(shí)際上鏈表還有多種不同的類型，比如雙向鏈表、循環(huán)鏈表

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

同時(shí)雙向鏈表不僅僅保存head，也保存最后一項(xiàng)的引用。

這樣的好處是： 迭代單向鏈表時(shí)，如果錯(cuò)過了某一項(xiàng)，只能重新迭代，但是雙向鏈表就找到上一項(xiàng)

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

    let length = 0;
    let head = null;
    let tail = null;  // 保存最后一項(xiàng)的索引
}
循環(huán)鏈表

循環(huán)鏈表，是指最后一項(xiàng)的指針不是null，而是指向第一個(gè)元素的一種鏈表。

所以循環(huán)鏈表，有可能是單向鏈表，也可能是雙向鏈表

雙向循環(huán)鏈表，最后一項(xiàng)的指針指向head，第一項(xiàng)的指針指向tail

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/108706.html

相關(guān)文章

  • 《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》筆記——第5章 鏈表

    摘要：鏈表存儲(chǔ)有序的元素集合，不同于數(shù)組，鏈表中的元素在內(nèi)存中并不是連續(xù)放置，每個(gè)元素有一個(gè)存取元素本身的節(jié)點(diǎn)和一個(gè)指向下一個(gè)元素的引用組成。優(yōu)點(diǎn)添加或者移除元素的時(shí)候不需要移動(dòng)其他元素。 鏈表存儲(chǔ)有序的元素集合，不同于數(shù)組，鏈表中的元素在內(nèi)存中并不是連續(xù)放置，每個(gè)元素有一個(gè)存取元素本身的節(jié)點(diǎn)和一個(gè)指向下一個(gè)元素的引用組成。 優(yōu)點(diǎn)：添加或者移除元素的時(shí)候不需要移動(dòng)其他元素。只需要找到加入的節(jié)...

    sutaking 評論0 收藏0

  • CSS技巧

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

    DangoSky 評論0 收藏0

  • CSS技巧

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

    zgbgx 評論0 收藏0

  • CSS技巧 - 收藏集 - 掘金

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

    Jonathan Shieber 評論0 收藏0

  • CSS技巧 - 收藏集 - 掘金

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

    SHERlocked93 評論0 收藏0

發(fā)表評論

0條評論

閱讀需要支付1元查看
<