【js4agls】數據結構JavaScript描述-鏈表篇

Xufc 發布于2019-08-19 18:14 / 1159人閱讀

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

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

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

我們為了刪除一個元素，導致了整個數組元素的前移，顯然這是非常低效的！尤其是當元素很多時。我們可以使用鏈表這種數據結構，來刪除元素的時候而不必讓后面的元素向前移動。

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

ADT

我們來看抽象數據類型的結構：

Node，單個節點
- element，節點數據
- next，下一個節點的指針

LinkList，鏈表的信息與方法
- insert，插入節點
- find，查找一個節點
- remove，刪除一個節點
- findPrevious，查找節點的前驅節點
- 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));
    }
}

分析 插入節點

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

創建新的節點

當前節點的next指向target的next

target.next指向新節點

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

算了直接看圖：

刪除節點

找到要刪除元素的前驅preNode

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

如果遍歷整個鏈表都沒找到要刪除的節點將會返回最后一個節點，而最后一個節點的下一個節點是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

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

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

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

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

數據結構大總結（鏈表篇）

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

不知名網友 2021-11-29 10:50 評論0 收藏0
【js4agls】數據結構JavaScript描述-棧篇

摘要：列表項目棧是一種后進先出的數據結構，我們所能操作的都是棧頂元素，刪除一個棧頂元素叫做出棧或者彈棧，添加一個元素叫做入棧或者壓棧首先構建我們的抽象數據類型棧頂元素位置保存數據的數組壓棧出棧查看棧頂元素清空棧棧的長度輸出棧元素描述模擬輸出列表項目棧是一種后進先出(LIFO)的數據結構，我們所能操作的都是棧頂元素，刪除一個棧頂元素叫做出棧或者彈棧，添加一個元素叫做入棧或者壓棧. show...

psychola 2019-08-19 18:13 評論0 收藏0
【js4agls】數據結構JavaScript描述-隊列篇

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

Anonymous1 2019-08-19 18:13 評論0 收藏0
數據結構與算法（鏈表） --javascript語言描述

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

617035918 2019-08-26 11:44 評論0 收藏0
數據結構JavaScript描述（二）

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

OldPanda 2019-08-21 18:20 評論0 收藏0