JavaScript的數(shù)據(jù)結(jié)構(gòu)與算法（四） —— 雙向鏈表

Youngdze 發(fā)布于2019-08-21 17:13 / 553人閱讀

摘要：鏈表鏈表存儲有序的元素集合，但不同于數(shù)組，鏈表中的元素在內(nèi)存中并不是連續(xù)放置的。鏈表又包括單向鏈表和雙向鏈表雙向鏈表雙向鏈表與單向鏈表很是相像。但在雙向鏈表中，還有指向上一個節(jié)點的鏈接，是雙向的。

鏈表

鏈表存儲有序的元素集合，但不同于數(shù)組，鏈表中的元素在內(nèi)存中并不是連續(xù)放置的。每個元素由一個存儲元素本事的節(jié)點和一個指向下一個元素的引用組成。相對于傳統(tǒng)的數(shù)組，鏈表的一個好處在于，添加或者刪除元素的時候不需要移動其他元素。
使用鏈表結(jié)構(gòu)可以克服數(shù)組需要預(yù)先知道數(shù)據(jù)大小的缺點(C語言的數(shù)組需要預(yù)先定義長度)，鏈表結(jié)構(gòu)可以充分利用計算機內(nèi)存空間，實現(xiàn)靈活的內(nèi)存動態(tài)管理。

數(shù)組和鏈表的一個不同在于數(shù)組可以直接訪問任何位置的元素，而想要訪問鏈表中的一個元素，需要從起點開始迭代列表。

鏈表又包括：單向鏈表和雙向鏈表；

雙向鏈表

雙向鏈表與單向鏈表很是相像。在單向鏈表中，只有指向下一個節(jié)點的鏈接。但在雙向鏈表中，還有指向上一個節(jié)點的鏈接，是雙向的。

讓我們來簡單實現(xiàn)一個雙向鏈表類，并包含如下功能：

append(element): 添加元素到鏈表尾部

insert(position,element): 向雙向鏈表中某個位置插入元素

removeAt(position): 移除雙向鏈表中某個位置的元素

getHead(): 獲取雙向鏈表的頭部

getTail(): 獲取雙向鏈表的尾部

isEmpty(): 檢查雙向鏈表是否為空，為空則返回true

size(): 返回雙向鏈表長度

代碼如下：

   function DoublyLinkedList() {
    /**
     * 雙向鏈表中節(jié)點的構(gòu)造函數(shù)
     * 
     * @param {any} element 要插入鏈表的元素
     */
    var Node = function (element) {
        this.element = element;
        this.next = null;
        this.prev = null;
    }

    // 雙向鏈表的長度
    var length = 0;
    // 雙向鏈表的頭結(jié)點，默認(rèn)為null
    var head = null;
    // 雙向鏈表的尾結(jié)點，默認(rèn)為null
    var tail = null;
    
    /**
     * 添加元素到雙向鏈表的尾部
     * 
     * @param {any} element 要插入的元素
     */
    this.append = function (element) {
        var node = new Node(element),
            current = head;

        if (head === null) {
            head = node
            tail = node
        } else {
            while (current.next) {
                current = current.next;
            }
            current.next = node;
            node.prev = current;
            tail = node;
        }
        length++;
        return true;
    }


    /**
     * 向雙向鏈表中某個位置插入元素
     * 
     * @param {any} position 要插入的位置
     * @param {any} element 要插入的元素
     * @returns 插入成功或失敗
     */
    this.insert = function (position, element) {
        var node = new Node(element),
            current = head,
            previous,
            index = 0;
        // 限制邊界
        if (position < 0 && position >= length) {
            return false;
        }

        if (position === 0) {
            // 在鏈表的頭部插入元素
            node.next = head
            head.prev = node
            head = node
        } else if (position === length) {
            // 在鏈表的尾部插入元素
            current = tail;
            current.next = node;
            node.prev = current;
            tail = node;
        } else {
            // 在鏈表的中間插入元素
            while (index++ < position) {
                previous = current
                current = current.next;
            }
            // 綁定前一個節(jié)點和插入節(jié)點的關(guān)系
            previous.next = node;
            node.prev = previous;
            // 綁定后一個節(jié)點和插入節(jié)點的關(guān)系
            node.next = current;
            current.prev = node;
        }
        length++;
        return true;
    }

    /**
     * 移除雙向鏈表中某個位置的元素
     * 
     * @param {any} position 要移除元素的位置
     * @returns 移除成功，返回移除的元素
     */
    this.removeAt = function (position) {
        var previous,
            current = head,
            index = 0;
         // 限制邊界
         if (position < 0 && position >= length) {
            return false;
        }

        if (position === 0) {
            // 移除鏈表的頭部
            head = current.next;
            head.prev = null;
        } else if(position === length - 1) {
             // 移除鏈表尾部的元素
             current = tail;
             tail = current.prev;
             tail.next = null;
        } else {
            // 移除鏈表中間的元素
            while (index++ < position) {
                previous = current
                current = current.next;
            }
            previous.next = current.next;
            current.next.prev = previous;
        }
        length--;
        return current.element;
    }

    this.getHead = function () {
        return head.element;
    }

    this.isEmpty = function () {
        return length === 0
    }

    this.getTail = function () {
        
        return tail.element;
    }

    this.size = function () {
        return length
    }
}

GPU云服務(wù)器云服務(wù)器雙向鏈表 java雙向鏈表描述的數(shù)據(jù)結(jié)構(gòu)與算法鏈表算法

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/89273.html

發(fā)表評論

登陸后可評論

0條評論

Youngdze

男|高級講師

我要關(guān)注我要私信

TA的文章

企業(yè)不再“迷信”低代碼

閱讀 1758·2021-11-24 10:18
易探云：雙11活動，香港/美國CN2;2核4G3M、4核8G5M云服務(wù)器推薦

閱讀 2277·2021-11-18 13:20
Hostodo：$12/年KVM-256MB/15GB/500GB/斯波坎(華盛頓州)

閱讀 2366·2021-08-23 09:46
重新認(rèn)識caniuse

閱讀 1022·2019-08-30 15:56
前端每日實戰(zhàn)：51# 視頻演示如何用純 CSS 創(chuàng)作一個雷達掃描動畫

閱讀 2865·2019-08-30 15:53
CSSModules

閱讀 776·2019-08-30 14:22
JS基礎(chǔ)入門篇（十五）—數(shù)組去重

閱讀 492·2019-08-29 15:34
常見BUG解決

閱讀 2561·2019-08-29 12:14

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

JavaScript的數(shù)據(jù)結(jié)構(gòu)與算法（四） —— 雙向鏈表

相關(guān)文章

**學(xué)習(xí)*JavaScript**數(shù)據(jù)結(jié)構(gòu)*與算法（二）：鏈表**

*javascript**數(shù)據(jù)結(jié)構(gòu)*與算法（一）單向鏈表與雙向鏈表

**《*Javascript**數(shù)據(jù)結(jié)構(gòu)*和算法》筆記-「鏈表」**

*Javascript**數(shù)據(jù)結(jié)構(gòu)*與算法（二）循環(huán)鏈表與有序鏈表

JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 線性表（數(shù)組、棧、隊列、鏈表）

發(fā)表評論

0條評論

Youngdze

男|高級講師

TA的文章

企業(yè)不再“迷信”低代碼

易探云：雙11活動，香港/美國CN2;2核4G3M、4核8G5M云服務(wù)器推薦

Hostodo：$12/年KVM-256MB/15GB/500GB/斯波坎(華盛頓州)

重新認(rèn)識caniuse

前端每日實戰(zhàn)：51# 視頻演示如何用純 CSS 創(chuàng)作一個雷達掃描動畫

CSSModules

JS基礎(chǔ)入門篇（十五）—數(shù)組去重

常見BUG解決

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

JavaScript的數(shù)據(jù)結(jié)構(gòu)與算法（四） —— 雙向鏈表

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！