使用JavaScript實(shí)現(xiàn)一個(gè)靜態(tài)鏈表

更新時(shí)間：2023年06月26日 08:25:17 作者：freephp

這篇文章主要為大家詳細(xì)介紹了如何使用JavaScript實(shí)現(xiàn)一個(gè)靜態(tài)鏈表，文中的示例代碼講解詳細(xì)，具有一定的學(xué)習(xí)價(jià)值，感興趣的小伙伴可以跟隨小編一起了解一下

最近重新開(kāi)始翻起《大話數(shù)據(jù)結(jié)構(gòu)》，看到了靜態(tài)鏈表部分里面講C語(yǔ)言是利用數(shù)組模擬，覺(jué)得十分有趣。但是在JavaScript中，也可以用類似的方式去實(shí)現(xiàn)，定義一個(gè)數(shù)據(jù)域和一個(gè)結(jié)點(diǎn)域，然后實(shí)現(xiàn)鏈表的基礎(chǔ)操作。弱類型語(yǔ)言沒(méi)有指針，所以需要自己區(qū)實(shí)現(xiàn)。算法的樂(lè)趣就在于解決一些思路上的問(wèn)題，直擊問(wèn)題的本質(zhì)。
首先可以定義Node類，如下所示：

class Node {
    constructor(value) {
        this.data = value;
        this.next = null;
    }
}

然后實(shí)現(xiàn)StaticLinkedList類，先定義簡(jiǎn)單的append和display方法：

class StaticLinkedList {
    constructor() {
        this.head = null;
        this.length = 0;
    }
    append(value) {
        const newNode = new Node(value);
        this.length++;
        if (this.head === null) {
            this.head = newNode;
            return;
        }
        let current = this.head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }
    display() {
        console.log('the static linked list is:\r\n');
        let current = this.head;
        if (current === null) {
            console.log('empty!');
            return;
        }
        while (current !== null) {
            console.log(JSON.stringify(current));
            console.log(`its value is ${current.data}\r\n`);
            current = current.next;
        }
    }
}

其中append方法是在鏈表尾部添加新的Node對(duì)象，display方法可以打印出Node對(duì)象和它的數(shù)據(jù)。使用這個(gè)靜態(tài)鏈表類也很簡(jiǎn)單，比如添加4個(gè)結(jié)點(diǎn)到這個(gè)鏈表里面：

const staticLinkedList = new StaticLinkedList();
staticLinkedList.append(3);
staticLinkedList.append(7);
staticLinkedList.append(16);
staticLinkedList.append(24);

我們還應(yīng)該提供更加靈活添加結(jié)點(diǎn)的方法，比如我想在第三個(gè)結(jié)點(diǎn)位置插入一個(gè)新的結(jié)點(diǎn)，數(shù)值為11，那么現(xiàn)有的append方法就不適用了，需要定義一個(gè)新的插入結(jié)點(diǎn)的方法，代碼如下：

    /**
     * Method to insert an new element at the specific location
     *
     * @param {*} elementValue the value of the element that to be inserted
     * @param {*} index the position of the element, from 1 to maximum of the list
     * @returns true/false
     */
    insertAt(elementValue, index) {
        if (index < 1 || index > this.length + 1) {
            console.log('index is out of the range!');
            return false;
        }
        const newNode = new Node(elementValue);
        let startPos = 1;
        let current = this.head;
        while (startPos < index - 1) {
            current = current.next;
            startPos++;
        }
        newNode.next = current.next;
        current.next = newNode;
        this.length++;
        return true;
    }

這段代碼需要理解的是新結(jié)點(diǎn)如何添加到鏈表的那兩行代碼，首先是newNode.next = current.next,這行代碼是把新結(jié)點(diǎn)的next指向了原來(lái)插入前位置的結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)。然后current.next = nextNode，把新結(jié)點(diǎn)替換掉原來(lái)該位置的結(jié)點(diǎn)。

為了更好地理解，我畫(huà)了一張示意圖：

要注意的是step1和step2的順序不能顛倒，否則會(huì)導(dǎo)致代碼運(yùn)行錯(cuò)誤。

然后我們還需要定義一個(gè)移除指定位置結(jié)點(diǎn)的方法，如下所示：

removeAt(index) {
        if (index < 1 || index > this.length + 1) {
            console.log('index is out of the range!');
            return;
        }
        let current = this.head;
        let startPos = 1;
        let previous = null;
        while (startPos < index) {
            previous = current;
            current = current.next;
            startPos++;
        }
        previous.next = current.next;
        this.length--;
    }

我對(duì)previous.next = current.next也畫(huà)了一張示意圖，刪除原來(lái)結(jié)點(diǎn)，需要把它前面一個(gè)結(jié)點(diǎn)的next指向該結(jié)點(diǎn)的next。

總結(jié)：靜態(tài)鏈表的添加和移除略有不同，需要利用Nod

到此這篇關(guān)于使用JavaScript實(shí)現(xiàn)一個(gè)靜態(tài)鏈表的文章就介紹到這了,更多相關(guān)JavaScript靜態(tài)鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: