成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

【js4agls】數(shù)據(jù)結(jié)構(gòu)JavaScript描述-鏈表篇

Xufc / 1162人閱讀

摘要：我們可以使用鏈表這種數(shù)據(jù)結(jié)構(gòu)，來刪除元素的時候而不必讓后面的元素向前移動。一個節(jié)點的上一個節(jié)點稱為它的前驅(qū)，下一個節(jié)點即指向的節(jié)點稱為它的后繼節(jié)點，在簡單的單向鏈表中，第一個節(jié)點稱為頭節(jié)點它沒有前驅(qū)節(jié)點，最后一個節(jié)點沒有后繼節(jié)點為。

之前我們用數(shù)組的方式來實現(xiàn)了隊列，是否還記得在出隊列后有這樣一段代碼：

for (i = 0; i < this.length - 1; i++) {
    this.dataStore[i] = this.dataStore[i + 1];
}

我們?yōu)榱藙h除一個元素，導致了整個數(shù)組元素的前移，顯然這是非常低效的！尤其是當元素很多時。我們可以使用鏈表這種數(shù)據(jù)結(jié)構(gòu)，來刪除元素的時候而不必讓后面的元素向前移動。

一個節(jié)點的上一個節(jié)點稱為它的前驅(qū)，下一個節(jié)點即next指向的節(jié)點稱為它的后繼節(jié)點，在簡單的單向鏈表中，第一個節(jié)點稱為頭節(jié)點它沒有前驅(qū)節(jié)點，最后一個節(jié)點沒有后繼節(jié)點(為NULL)。關(guān)于頭節(jié)點head其實是可有可無的，但是一般都會加上這個數(shù)據(jù)為空的節(jié)點，保存當前鏈表信息，如果一個鏈表的頭節(jié)點找不到了，那么將會導致整個鏈表的丟失。

ADT

我們來看抽象數(shù)據(jù)類型的結(jié)構(gòu)：

Node，單個節(jié)點
- element，節(jié)點數(shù)據(jù)
- next，下一個節(jié)點的指針

LinkList，鏈表的信息與方法
- insert，插入節(jié)點
- find，查找一個節(jié)點
- remove，刪除一個節(jié)點
- findPrevious，查找節(jié)點的前驅(qū)節(jié)點
- print，打印鏈表
JavaScript完整描述 
function Node (element) {
    this.element = element;
    this.next = null;
}
function LinkList () {
    this.head = new Node("head");
}
LinkList.prototype = {
    constructor: LinkList,
    insert: function (target, element) {
        var newNode = new Node(target);
        var current = this.find(element);
        newNode.next = current.next;
        current.next = newNode;
        return this;
    },
    find: function (target) {
        var currentNode = this.head;
        while (currentNode.element !== target) {
            currentNode = currentNode.next;
        }
        return currentNode;
    },
    remove: function (element) {
        var preNode = this.findPrevious(element);
        if (preNode.next !== null) {
            preNode.next = preNode.next.next;
            return true;
        }
        return false;
    },
    findPrevious: function (element) {
        var current = this.head;
        while (current.next !== null && current.next.element !== element) {
            current = current.next;
        }
        return current;
    },
    print: function () {
        var current = this.head.next;
        var str = "";
        while (current) {
            str += current.element + "->";
            current = current.next;
        }
        console.log(str.substr(0, str.length-2));
    }
}
分析 插入節(jié)點

通過find方法找到要插入的節(jié)點位置target

創(chuàng)建新的節(jié)點

當前節(jié)點的next指向target的next

target.next指向新節(jié)點

在插入的最后我們返回了this是為了方便進行鏈式插入。

算了直接看圖：

刪除節(jié)點

找到要刪除元素的前驅(qū)preNode

將preNode的下一個節(jié)點指向preNode的下一個節(jié)點(要刪除的節(jié)點)的下一個節(jié)點

如果遍歷整個鏈表都沒找到要刪除的節(jié)點將會返回最后一個節(jié)點，而最后一個節(jié)點的下一個節(jié)點是NULL，所以，這樣的刪除操作會失敗，返回false
測試 
var list = new LinkList();
list.insert("jiavan1", "head").insert("jiavan2", "jiavan1").insert("jiavan3", "jiavan2").insert("jiavan4", "jiavan3");
list.print(); // jiavan1->jiavan2->jiavan3->jiavan4
list.remove("jiavan2"); // true
list.print(); // jiavan1->jiavan3->jiavan4
list.remove("none"); // false

這只是最簡單的一種鏈表，復雜點的還有雙向鏈表，循環(huán)鏈表，我們將用另外的文章實現(xiàn)。

原文出處 https://github.com/Jiavan/jia... 覺得對你有幫助就給個star吧

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/79354.html

相關(guān)文章

  • 數(shù)據(jù)結(jié)構(gòu)大總結(jié)（鏈表篇）

    摘要：實際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶圖的鄰接表等等。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。 文章目錄 一.算法的時間復雜度和空間復雜度1.算法...

    不知名網(wǎng)友 評論0 收藏0

  • 【js4agls】數(shù)據(jù)結(jié)構(gòu)JavaScript描述-棧篇

    摘要：列表項目棧是一種后進先出的數(shù)據(jù)結(jié)構(gòu)，我們所能操作的都是棧頂元素，刪除一個棧頂元素叫做出?；蛘邚棗＃砑右粋€元素叫做入?；蛘邏簵Ｊ紫葮?gòu)建我們的抽象數(shù)據(jù)類型棧頂元素位置保存數(shù)據(jù)的數(shù)組壓棧出棧查看棧頂元素清空棧棧的長度輸出棧元素描述模擬輸出 列表項目 棧是一種后進先出(LIFO)的數(shù)據(jù)結(jié)構(gòu)，我們所能操作的都是棧頂元素，刪除一個棧頂元素叫做出?；蛘邚棗?，添加一個元素叫做入?；蛘邏簵? show...

    psychola 評論0 收藏0

  • 【js4agls】數(shù)據(jù)結(jié)構(gòu)JavaScript描述-隊列篇

    摘要：隊列是一種先進先出的數(shù)據(jù)結(jié)構(gòu)，與棧不同的是，它操作的元素是在兩端，而且進行的是不一樣的操作。 隊列(Queue)是一種先進先出(First-In-First-Out, FIFO)的數(shù)據(jù)結(jié)構(gòu)，與棧不同的是，它操作的元素是在兩端，而且進行的是不一樣的操作。向隊列的隊尾加入一個元素叫做入隊列(enQueue)，向隊列的隊首刪除一個元素叫做出隊列(delQueue). showImg(http...

    Anonymous1 評論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)與算法（鏈表） --javascript語言描述

    從尾到頭打印鏈表 輸入一個鏈表，從尾到頭打印鏈表每個節(jié)點的值。思路：先將鏈表每個結(jié)點的值存入數(shù)組中，然后通過數(shù)組的reverse方法，即可從尾到頭打印。 function ListNode(x){ this.val = x; this.next = null; } function printListFromTailToHead(head){ if(!head...

    617035918 評論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)JavaScript描述（二）

    摘要：在上一篇文章中，我們了解了隊列和棧的描述，現(xiàn)在讓我們來了解一下單鏈表和雙向鏈表的實現(xiàn)。單鏈表和雙向鏈表具有以下特點可動態(tài)分配空間，但不能隨機訪問。 在上一篇文章中，我們了解了隊列和棧的JavaScript描述，現(xiàn)在讓我們來了解一下 單鏈表 和雙向鏈表 的實現(xiàn)。本文的代碼并非所有都由本人所寫，只是出于學習目的，在此分享出來，并加上一定的解釋，便于大家學習。 本系列文章的代碼可在ht...

    OldPanda 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<