DIV CSS 佈局教程網

JavaScript 單向鏈表資料結構的完整實作
編輯:關於JavaScript     

用鏈表理解指標與節點

鏈表(Linked List)是資料結構中的經典入門題,它能幫助我們理解「節點」與「指標」的概念。與陣列不同,鏈表的元素在記憶體中不必連續,每個節點透過 next 指向下一個節點。下面以 JavaScript 打造一個具備新增、插入、刪除、查詢、排序與序列化能力的單向鏈表。

節點與鏈表建構子

function linkNode(_key, _value)
{
    /// <summary> 鏈表類的節點類 </summary>
    this.Key = _key;
    this.Value = _value;
    this.next = null;
}
function Link()
{
    /// <summary> 創建一個鏈表類 </summary>
    this.root = new linkNode(null, null); // root 永遠是個空節點
    this.end = this.root;
}

核心方法

每個方法都透過原型掛載到 Link 上,涵蓋了鏈表操作最常見的需求:

Link.prototype =
{
    count: 0,

    // 根據 key 的值來獲取 value 值
    value: function (_key) {
        var i = this.root;
        while (Boolean(i = i.next)) {
            if (i.Key == _key) return i.Value;
        }
    },

    // 往鏈表的尾部中加入一個節點
    add: function (_key, _value) {
        var i = this.root;
        while (Boolean(i = i.next)) {
            if (i.Key == _key) return i.Value = _value;
        }
        var node = new linkNode(_key, _value);
        if (this.count == 0) this.root.next = node;
        else this.end.next = node;
        this.end = node;
        this.count++;
        return _value;
    },

    // 從鏈表類的某節點之後插入新節點 node
    insert: function (_key, node) {
        var i = this.root;
        while (Boolean(i = i.next)) {
            if (i.Key == _key) {
                var tmp = i.next;
                i.next = node;
                node.next = tmp;
                break;
            }
        }
    },

    // 從某節點之前插入新節點 node
    insertBefore: function (_key, node) {
        var i = this.root;
        while (Boolean(i = i.next)) {
            if (i.next.Key == _key) {
                var tmp = i.next;
                i.next = node;
                node.next = tmp;
                break;
            }
        }
    },

    // 從鏈表類中移除一個 key
    remove: function (_key) {
        var i = this.root;
        do {
            if (i.next.Key == _key) {
                if (i.next.next == null) this.end = i;
                i.next = i.next.next;
                this.count--;
                return;
            }
        } while (Boolean(i = i.next))
    },

    // 檢查鏈表中是否存在一個 key
    exists: function (_key) {
        var i = this.root;
        while (Boolean(i = i.next))
        if (i.Key == _key) return true;
        return false;
    },

    // 清空鏈表
    removeAll: function () {
        this.root = new linkNode(null, null);
        this.end = this.root;
        this.count = 0;
    },

    // 對鏈表進行排序(氣泡排序思維)
    sort: function (fn) {
        if (fn != null) {
            var i = this.root;
            while (Boolean(i = i.next)) {
                var j = this.root;
                while (Boolean(j = j.next)) {
                    if (j.next != null) {
                        if (fn.call(this, j)) {
                            var Key = j.Key;
                            var Value = j.Value;
                            j.Key = j.next.Key;
                            j.Value = j.next.Value;
                            j.next.Key = Key;
                            j.next.Value = Value;
                        }
                    }
                }
                this.end = i;
            }
        }
    }
};

設計重點

這個實作用了一個空的 root 節點作為起點(哨兵節點),使得插入與刪除時不必特別判斷頭部,邏輯更一致。另外還提供了 getJSON、getArrayJSON 等序列化方法,可把整個鏈表結構轉成 JSON 字串。若需要完整版本,可再加上這兩個方法。透過這份程式碼,能清楚看到鏈表「靠指標串起節點」的核心精神。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved