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

李濤發(fā)布于2019-08-21 17:14 / 1834人閱讀

摘要：鏈表鏈表存儲(chǔ)有序的元素集合，但不同于數(shù)組，鏈表中的元素在內(nèi)存中并不是連續(xù)放置的。相對(duì)于傳統(tǒng)的數(shù)組，鏈表的一個(gè)好處在于，添加或者刪除元素的時(shí)候不需要移動(dòng)其他元素。

鏈表

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

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

鏈表又包括：?jiǎn)蜗蜴湵?和雙向鏈表；

單向鏈表

鏈表中最簡(jiǎn)單的形式就是單向鏈表，鏈表中的節(jié)點(diǎn)都包含兩個(gè)部分，第一部分儲(chǔ)存著自身信息，第二部分則儲(chǔ)存有指向下一節(jié)點(diǎn)的指針。最后一個(gè)節(jié)點(diǎn)則指向NULL，如圖所示:

讓我們來(lái)簡(jiǎn)單實(shí)現(xiàn)一個(gè)單向鏈表類(lèi)，并包含如下功能：

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

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

indexOf(element): 尋找某個(gè)元素在單向鏈表中的位置

remove(element): 移除給定的元素

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

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

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

toString(): 將鏈表所有內(nèi)容以字符串輸出

size(): 返回單向鏈表長(zhǎng)度

代碼如下：

 function LinkedList() {
    /**
     * 單向鏈表節(jié)點(diǎn)的構(gòu)造函數(shù)
     * 
     * @param {any} element 要傳入鏈表的節(jié)點(diǎn)
     */
    var Node = function (element) {
        this.element = element;
        this.next = null;
    }
    // 單向鏈表的長(zhǎng)度
    var length = 0;
    // 單向鏈表的頭節(jié)點(diǎn)，初始化為null
    var head = null;


    /**
     * 添加元素到鏈表尾部
     * 
     * @param {any} element 要傳入鏈表的節(jié)點(diǎn)
     */
    this.append = function(element) {
        var node = new Node(element),
            current;

        if (head === null) {
            head = node
        } else {
            current = head;
            // 當(dāng)next為null時(shí),退出循環(huán)
            while (current.next) {
                current = current.next;
            }
            current.next = node;
        }
        length++;
    }

    /**
     * 向單向鏈表中某個(gè)位置插入元素
     * 
     * @param {any} position 位置
     * @param {any} element 要傳入鏈表的節(jié)點(diǎn)
     */
    this.insert = function (position, element) {
        var node = new Node(element),
            current = head,
            previous,
            index;
        // 驗(yàn)證邊界
        if (position < 0 || position >= length) {
            return false;
        }
        // 在鏈表頭部插入
        if (position === 0) {
            node.next = current；
            head = node；
        } else {
            // 在鏈表除頭部之外的地方插入（中間 or 末尾）
            while (index++ < position) {
                previous = current
                current = current.next
            }
            // 在前一個(gè)節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)中間插入
            node.next = current;
            previous.next = node;
        }
        length++;
        return true;
    }

    
    /**
     * 尋找某個(gè)元素在單向鏈表中的位置
     * 
     * @param {any} element 要尋找的節(jié)點(diǎn)
     * @returns {Number} 返回值>=0則代表找到相應(yīng)位置
     */
    this.indexOf = function (element) {
        var index = 0,
            current = head;

        while (current) {
            if (element === current.element) {
                return index
            }
            index++;
            current = current.next;
        }
        // 如果鏈表中不存該元素，返回-1
        return -1;
    }

    /**
     * 移除單向鏈表中某個(gè)位置的元素
     * 
     * @param {any} position 要移除的位置
     */
    this.removeAt = function (position) {
        var index = 0,
            previous,
            current = head;
        if (position < 0 || position >= length) {
            return null;
        }

        if (position === 0) {
            head = head.next;
        } else {
            while (index++ < position) {
                previous = current;
                current = current.next;
            }
            previous.next = current.next;
        }
        length--;
        return current.element;
    }

    /**
     * 移除給定的元素
     * 
     * @param {any} element 要移除的節(jié)點(diǎn)
     * @returns 
     */
    this.remove = function (element) {
        var index = this.indexOf(element);
        return this.removeAt(index)
    }

    /**
     * 獲取單向鏈表的頭部
     * 
     */
    this.getHead = function () {
        return head.element
    }

    /**
     * 檢查單向鏈表是否為空
     * 
     * @returns 為空則返回true
     */
    this.isEmpty = function () {
        return length === 0
    }
    
    /**
     * 返回單向鏈表長(zhǎng)度
     * 
     * @returns {Number}
     */
    this.size = function () {
        return length;
    }

    /**
     *  將鏈表所有內(nèi)容以字符串輸出
     * 
     * @returns {String}
     */
    this.toString = function () {
        var str = "",
            current = head;
        while(current) {
            str += current.element;
            current = current.next;
        }
        return str;
    }
}

云服務(wù)器 GPU云服務(wù)器單向鏈表的操作c語(yǔ)言單向鏈表詳解描述的數(shù)據(jù)結(jié)構(gòu)與算法鏈表算法

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

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

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

李濤

男|高級(jí)講師

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

TA的文章

SSL證書(shū)是一個(gè)域名一個(gè)證書(shū)嗎？多個(gè)域名能用一張SSL證書(shū)嗎？

閱讀 1194·2021-11-22 13:54
大連虛擬主機(jī)怎么選擇-如何選擇虛擬主機(jī)？

閱讀 2443·2021-09-22 15:36
CSS 入門(mén)

閱讀 2748·2019-08-30 15:54
微信公眾號(hào)開(kāi)發(fā)之坑（一）

閱讀 818·2019-08-30 15:53
HTML、CSS基礎(chǔ) {未完待續(xù)}

閱讀 3182·2019-08-30 15:53
前端每日實(shí)戰(zhàn)：19# 視頻演示如何用純 CSS 創(chuàng)作一種有削鐵如泥感覺(jué)的菜單導(dǎo)航特效

閱讀 525·2019-08-29 15:21
常用瀏覽器私有屬性小記

閱讀 2878·2019-08-28 18:28
重新認(rèn)識(shí)caniuse

閱讀 3029·2019-08-26 13:37

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

資訊專(zhuān)欄INFORMATION COLUMN

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

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

相關(guān)文章

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

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

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

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

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

發(fā)表評(píng)論

0條評(píng)論

李濤

男|高級(jí)講師

TA的文章

SSL證書(shū)是一個(gè)域名一個(gè)證書(shū)嗎？多個(gè)域名能用一張SSL證書(shū)嗎？

大連虛擬主機(jī)怎么選擇-如何選擇虛擬主機(jī)？

CSS 入門(mén)

微信公眾號(hào)開(kāi)發(fā)之坑（一）

HTML、CSS基礎(chǔ) {未完待續(xù)}

前端每日實(shí)戰(zhàn)：19# 視頻演示如何用純 CSS 創(chuàng)作一種有削鐵如泥感覺(jué)的菜單導(dǎo)航特效

常用瀏覽器私有屬性小記

重新認(rèn)識(shí)caniuse

最新活動(dòng)

資訊專(zhuān)欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

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

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

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