JavaScript 中的計算機科學：雙向鍊錶

這個帖子已經過時了。閱讀更新後的帖子。

在我的上一篇文章中，我討論了在 JavaScript 中創建一個鍊錶。這種基本數據結構經常在計算機科學程序中用於教授指針的概念。下一步是研究雙向鍊錶。雙向鍊錶與單向鍊錶類似，只是它在節點之間具有雙向鏈接。而不是只有一個 next 每個節點上的指針，還有一個previous 指針，而不僅僅是跟踪列表的頭部，您還跟踪尾部（最後一個節點）。

節點之間的額外指針集允許更輕鬆的操作和遍歷，但增加了複雜性，因為有更多的指針需要管理。雙向鍊錶中的單個節點可以如下實現：

var firstNode = {
    data: 12,
    next: null,
    prev: null
};

next 和 prev 必須在每個節點上填寫指針。添加另一個節點需要設置兩個指針而不是一個：

var secondNode = {
    data: 99,
    prev: firstNode,    //set pointer #1
    next: null
};

firstNode.next = secondNode;    //set pointer #2

現在每個節點都有一個對另一個節點的引用，允許您按照 next 遍歷列表 或 prev .

與單鍊錶一樣，有很多指針操作最好封裝在自定義類型中。一個基本的雙向鍊錶類型如下：

function DoublyLinkedList() {
    this._length = 0;
    this._head = null;
    this._tail = null;
}

您會注意到其中兩個屬性與 LinkedList 完全相同 實現：_length 和 _head .唯一的補充是 _tail 屬性來跟踪列表中的最後一個節點。

添加到雙向鍊錶與添加到單鍊錶非常相似。主要區別在於跟踪 _tail 並使用它來添加新節點，而不是遍歷整個結構以找到插入下一個節點的正確位置：

DoublyLinkedList.prototype = {

    add: function (data){

        //create a new item object, place data in
        var node = {
                data: data,
                next: null,
                prev: null
            };

        //special case: no items in the list yet
        if (this._length == 0) {
            this._head = node;
            this._tail = node;
        } else {

            //attach to the tail node
            this._tail.next = node;
            node.prev = this._tail;
            this._tail = node;
        }        

        //don't forget to update the count
        this._length++;

    },

    //more methods here
};

當列表中沒有任何內容時，添加一個項目意味著同時設置 _head 和 _tail 等於同一個節點。在所有其他情況下，您只需使用 _tail 添加新節點。

從雙向鍊錶中刪除項目也與從單鍊錶中刪除有些不同。有兩種特殊情況：當要刪除的節點是第一個時，以及要刪除的節點是最後一個時。對於其他情況，算法與單鍊錶非常相似，遍歷鍊錶找到正確的要移除的項，然後調整指針：

DoublyLinkedList.prototype = {

    remove: function(index){

        //check for out-of-bounds values
        if (index > -1 && index < this._length){

            var current = this._head,
                i = 0;

            //special case: removing first item
            if (index === 0){
                this._head = current.next;

                /*
                 * If there's only one item in the list and you remove it,
                 * then this._head will be null. In that case, you should
                 * also set this._tail to be null to effectively destroy
                 * the list. Otherwise, set the previous pointer on the
                 * new this._head to be null.
                 */
                if (!this._head){
                    this._tail = null;
                } else {
                    this._head.prev = null;
                }

            //special case: removing last item
            } else if (index === this._length -1){
                current = this._tail;
                this._tail = current.prev;
                this._tail.next = null;
            } else {

                //find the right location
                while(i++ < index){
                    current = current.next;
                }

                //skip over the item to remove
                current.prev.next = current.next;
            }

            //decrement the length
            this._length--;

            //return the value
            return current.data;            

        } else {
            return null;
        }

    },    

    //more methods here
};

從雙向鍊錶中刪除項目最重要的部分是確保沒有指向被刪除節點的指針。

除這兩種方法外，其餘方法與LinkedList相同 從我之前的帖子中實現。這包括 item() , size() , 和 toArray() .您可以從我在 GitHub 上的 JavaScript 中的計算機科學項目下載完整的源代碼。