用JavaScript擼一個靜態連結串列

最近重新開始翻起《大話資料結構》，看到了靜態連結串列部分裡面講C語言是利用陣列模擬，覺得十分有趣。但是在JavaScript中，也可以用類似的方式去實現，定義一個資料域和一個結點域，然後實現連結串列的基礎操作。弱型別語言沒有指標，所以需要自己區實現。演演算法的樂趣就在於解決一些思路上的問題，直擊問題的本質。
首先可以定義Node類，如下所示：

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

然後實現StaticLinkedList類，先定義簡單的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物件，display方法可以列印出Node物件和它的資料。使用這個靜態連結串列類也很簡單，比如新增4個結點到這個連結串列裡面：

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

我們還應該提供更加靈活新增結點的方法，比如我想在第三個結點位置插入一個新的結點，數值為11，那麼現有的append方法就不適用了，需要定義一個新的插入結點的方法，程式碼如下：

    /**
     * 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;
    }

這段程式碼需要理解的是新結點如何新增到連結串列的那兩行程式碼，首先是newNode.next = current.next,這行程式碼是把新結點的next指向了原來插入前位置的結點的下一個結點。然後current.next = nextNode，把新結點替換掉原來該位置的結點。

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

要注意的是step1和step2的順序不能顛倒，否則會導致程式碼執行錯誤。

然後我們還需要定義一個移除指定位置結點的方法，如下所示：

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--;
    }

我對previous.next = current.next也畫了一張示意圖，刪除原來結點，需要把它前面一個結點的next指向該結點的next。

總結：
靜態連結串列的新增和移除略有不同，需要利用Node中的next進行模擬指標操作，讓新的結點加入到連結串列，讓需要被刪除的結點直接從上一個結點的next指向到原有結點的next。